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

Công thức truy hồi chia để trị<br /> <br /> Công thức truy hồi chia để trị1 (đang sửa)<br /> Trần Vĩnh Đức<br /> HUST<br /> <br /> Ngày 7 tháng 8 năm 2013<br /> <br /> 1<br /> <br /> Tham khảo: Mathematics for CS, MIT<br /> <br /> ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> .<br /> <br /> . . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> .<br /> <br /> Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013<br /> <br /> 1 / 22<br /> <br /> Công thức truy hồi chia để trị<br /> <br /> Bài toán tháp Hà Nội<br /> ..<br /> <br /> .<br /> <br /> Hình : Nguồn: wikipedia<br /> <br /> ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> .<br /> <br /> . . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> .<br /> <br /> Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013<br /> <br /> 2 / 22<br /> <br /> Có 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?<br /> <br /> Công thức truy hồi chia để trị<br /> <br /> .. ịnh nghĩa Đ T . n := số lần chuyển ít nhất cho n đĩa. T1 = 1 T2 = 3 T3 ≤ 7.<br /> <br /> ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> .<br /> <br /> . . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> .<br /> <br /> Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013<br /> <br /> 3 / 22<br /> <br /> Công thức truy hồiThe Towers of Hanoi 10.1. chia để trị<br /> <br /> ..<br /> <br /> 285<br /> <br /> .<br /> <br /> 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.<br /> .. . .. . .. . . . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> . ..<br /> <br /> .<br /> <br /> Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013<br /> <br /> 4 / 22<br /> <br />