Bài giảng Công thức truy hồi chia để trị - Trần Vĩnh Đức

Bài giảng Công thức truy hồi chia để trị do Trần Vĩnh Đức biên soạn trình bày về bài toán Tháp Hà Nội, chứng minh bài toán bằng công thức truy hồi chia để trị. Tham khảo nội dung bài giảng để hiểu rõ hơn về các nội dung trên.
Nội dung trích xuất từ tài liệu:
Bài giảng Công thức truy hồi chia để trị - Trần Vĩnh ĐứcCông thức truy hồi chia để trịCông thức truy hồi chia để trị1 (đang sửa)Trần Vĩnh ĐứcHUSTNgày 7 tháng 8 năm 20131Tham khảo: Mathematics for CS, MIT... ... .... . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ...Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 20131 / 22Công thức truy hồi chia để trịBài toán tháp Hà Nội...Hình : Nguồn: wikipedia... ... .... . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ...Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 20132 / 22Có 3 cái cọc và trên một chiếc cọc đặt n cái đĩa với đường kính giảm dần. Cần ít nhất bao nhiêu lần di chuyển để chuyển hết cả n đĩa sang cọc bên cạnh sao cho • mỗi lần chỉ di chuyển một đĩa • mỗi đĩa có thể dịch chuyển từ một cọc này sang một cọc khác bất kỳ, nhưng không được để một chiếc đĩa lớn lên trên một chiếc đĩa khác có đường kính nhỏ hơn?Công thức truy hồi chia để trị.. ịnh nghĩa Đ T . n := số lần chuyển ít nhất cho n đĩa. T1 = 1 T2 = 3 T3 ≤ 7.... ... .... . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ...Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 20133 / 22Công thức truy hồiThe Towers of Hanoi 10.1. chia để trị..285.Figure 10.2 The 7-step solution to the Towers of Hanoi problem when there are Hình : Lời giải gồm 7 bước khi bài toán với 3 đĩa n D 3 disks... . .. . .. . . . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ...Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 20134 / 22