$txt['colorize_color'] = 'Color';$txt['HPlocation'] = 'Project Honey Pot (all regions)'; // MOD Quick PM $txt['quick_pm'] = 'Quick PM'; $txt['change_quick_pm'] = 'Change to Quick PM'; $txt['change_quick_reply'] = 'Change to Quick Reply'; $txt['send_message'] = 'Send message'; $txt['quick_pm_desc'] = 'With Quick-PM you can write a personal message when viewing a topic without loading a new page. You can still use bulletin board code and smileys as you would in a normal personal message.'; $txt['display_quick_pm'] = 'Enable Quick PM (requires enable Quick Reply)'; // MOD Auto Merge Double Post $txt['permissionname_doublePost'] = 'Allow to do Double Post'; $txt['permissionhelp_doublePost'] = 'By Enabling this will allow them to double post.'; $txt['AutoMergePost_div'] = 'Add text when merging the post'; $txt['AutoMergePost_div_sub'] = 'You can use BBC and $date variable'; $txt['AutoMergePost_time'] = 'Time after which it will allow the bump the topic'; $txt['AutoMergePost_time_sub'] = 'Time 0 to disable the MOD and 9999 for never allow bump'; // Aeva Media extra strings $txt['aeva_gallery'] = isset($txt['aeva_gallery']) ? $txt['aeva_gallery'] : 'Media'; $txt['aeva_home'] = 'Home'; $txt['aeva_unseen'] = 'Unseen'; $txt['aeva_profile_sum'] = 'Summary'; $txt['aeva_view_items'] = 'View items'; $txt['aeva_view_coms'] = 'View comments'; $txt['aeva_view_votes'] = 'View votes'; $txt['aeva_gotolink'] = 'Details'; $txt['aeva_zoom'] = 'Zoom'; $txt['permissiongroup_aeva'] = 'Aeva Media'; $txt['permissiongroup_simple_aeva'] = 'Aeva Media'; $txt['permissionname_aeva_access'] = 'Access Gallery'; $txt['permissionname_aeva_moderate'] = 'Moderate Gallery'; $txt['permissionname_aeva_manage'] = 'Administrate Gallery'; $txt['permissionname_aeva_access_unseen'] = 'Access unseen area'; $txt['permissionname_aeva_search'] = 'Search in Gallery'; $txt['permissionname_aeva_add_user_album'] = 'Add Albums'; $txt['permissionname_aeva_add_playlists'] = 'Add User Playlists'; $txt['permissionname_aeva_auto_approve_albums'] = 'Auto-approve Albums'; $txt['permissionname_aeva_moderate_own_albums'] = 'Moderate own Albums'; $txt['permissionname_aeva_viewprofile'] = 'View anyone\'s Gallery profile'; $txt['cannot_aeva_viewprofile'] = 'You cannot view Gallery profiles'; // End Aeva Media strings $txt['display_facebook_like'] = 'Display Facebook Like icon?'; $txt['display_facebook_like_desc'] = 'Enabling this will Display the Facebook Like Icon within posts.'; $txt['display_facebook_like_all'] = 'Display Facebook Like icon in all posts?'; $txt['display_facebook_like_all_desc'] = 'Enabling this will Display the Facebook Like Icon within all posts. Note Display Facebook Like Icon has to be enabled'; BÀI TOÁN THÁP HÀ NỘI - TOWER OF HANOI
Ashui.com/Forum ashui
07/12/2019, 19:36  
27277 bài viết trong 10831 chủ đề bởi 205210 thành viên
Xem các bài viết mới trên diễn đàn.
Xin chào ! Bạn là khách. Vui lòng đăng nhập hoặc đăng ký.

Đăng nhập với tên truy cập, mật khẩu và thời gian tự động thoát
VNArchitects.com
Chủ đề quan tâm: Để đăng kư thành viên, xin vui ḷng liên hệ: admin@ashui.com
 
   Trang chủ   Lịch sự kiện Thành viên Tìm kiếm Trợ giúp Đăng nhập Đăng ký  
Trang: [1]   Chuyển xuống
  In ấn  
Tác giả Chủ đề: BÀI TOÁN THÁP HÀ NỘI - TOWER OF HANOI  (Đọc 8184 lần)
0 thành viên và 1 khách đang xem chủ đề này.
canlong
Ashui-U
*


Gián tuyến Gián tuyến

Bài: 96


Xem hồ sơ
« vào: 11/12/2008, 11:59 »

BÀI TOÁN THÁP HÀ NỘI - TOWER OF HANOI


Có thể c̣n ít người Việt Nam biết Tháp Hà Nội, nhưng rất nhiều thanh niên sinh viên trên toàn thế giới lại biết đến nó. Đó là v́, Tháp Hà Nội là tên một bài toán rất nổi tiếng trong Chương tŕnh khoa học tính toán (Computing Science) dành cho sinh viên những năm đầu tại các trường đại học ở nhiều nơi trên thế giới.

Tương truyền rằng ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời, Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư. Bài toán của Hoàng đế là: cho n cái đĩa (ngài không nói chính xác là bao nhiêu) và ba cái trục: A là trục nguồn, B là trục đích, và C là trục trung chuyển. Những cái đĩa có kích cỡ khác nhau và có lỗ ở giữa để có thể lồng vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên, những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục B, với điều kiện chuyển từng cái một và luôn phải đảm bảo quy định "nhỏ trên lớn dưới", biết rằng trục C được phép sử dụng làm trục trung chuyển?

V́ địa vị quân sư được coi là vinh hiển nên có rất nhiều người dự thi. Từ vị học giả đến bác nông phu, họ đua nhau tŕnh lên Hoàng đế lời giải của ḿnh. Nhiều lời giải dài tới hàng ngh́n bước, và nhiều lời giải có chữ "chuyển sang bước tiếp theo" (go to). Nhưng hoàng đế thấy mệt mỏi v́ những lời giải đó, nên cuối cùng hạ chiếu: "Ta không hiểu những lời giải này. Phải có một cách giải nào khác dễ hiểu và nhanh chóng hơn". May mắn thay, cuối cùng đă có một cách giải như thế.
Thật vậy, ngay sau khi chiếu vua ban ra, một vị cao tăng trông bề ngoài giống như một kỳ nhân hạ sơn tới xin yết kiến hoàng đế. Vị cao tăng nói: "Thưa Bệ hạ, bài toán đố đó dễ quá, hầu như nó tự giải cho nó". Quan trùm cấm vệ đứng hầu ngay bên cạnh vua quắc mắt nh́n gă kỳ nhân, muốn quẳng gă ra ngoài, nhưng Hoàng đế vẫn kiên nhẫn tiếp tục lắng nghe. "Nếu chỉ có 1 đĩa, th́...; nếu có nhiều hơn 1 đĩa (n>1), th́...", cứ thế vị cao tăng b́nh tĩnh giảng giải. Im lặng được một lát, cuối cùng Hoàng đế sốt ruột gắt: "Được, thế cao tăng có nói rơ cho ta lời giải hay không cơ chứ?". Thay v́ giải thích tiếp, gă kỳ nhân mỉm cười thâm thúy rồi biến mất, bởi v́ hoàng đế tuy giỏi giang nhưng rơ ràng là chưa hiểu ư nghĩa của phép truy hồi (recursion). Nhưng các bạn sinh viên ngày nay th́ có thể thấy cách giải của vị cao tăng là hoàn toàn đúng.

Toàn bộ đoạn chữ nghiêng ở trên được trích nguyên văn từ cuốn sách giáo khoa dành cho sinh viên ngành thuật toán và lập tŕnh - "giải toán nâng cao và cấu trúc dữ liệu" (intermediate problem solving and data structures) do Paul Henman và Robert Veroff, hai giáo sư Đại học New Mexico, cùng biên soạn với Frank Carrano, giáo sư Đại học Rhode Island (Mỹ).

Bạn nào chưa từng biết Tháp Hà Nội th́ cũng nên "thử sức" một chút xem sao, v́ đây là một tṛ chơi rất thú vị. Bạn có thể bắt đầu bằng bài toán 3 đĩa, rồi nâng lên 4 đĩa. Với 4 đĩa chắc bạn bắt đầu thấy rắc rối. Nâng tiếp lên 5 và cao hơn nữa, chẳng hạn n = 1 triệu, bài toán sẽ rắc rối đến mức không ai đủ kiên tŕ và đủ th́ giờ để thử từng đĩa một. Vậy mà vị cao tăng dám nói là dễ quá! Xin tiết lộ, ấy là v́ vị đó đă sử dụng phép truy hồi - một quy tắc toán học cho phép xác định số hạng thứ n từ số hạng đứng trước nó, tức số hạng thứ n-1. Cái giỏi của vị cao tăng là ông t́m ra một quy tắc chung, tức một thuật toán chung cho tất cả các bước chuyển đĩa.

Vậy thay v́ mô tả toàn bộ quá tŕnh chuyển đĩa từng cái một như những thí sinh trước đó đă làm, vị cao tăng chỉ mô tả một quy tắc chung. Cứ làm theo quy tắc đó, lặp đi lặp lại chẳng cần suy nghĩ ǵ, rồi cuối cùng tự nhiên sẽ tới đích. V́ thế vị cao tăng nói rằng bài toán này "tự nó giải nó".

Trong khoa học tính toán ngày nay, phép truy hồi là thuật toán cơ bản để lập tŕnh. Ưu điểm của phương pháp truy hồi là ở chỗ nó dùng một công thức nhất định để diễn tả những phép tính lặp đi lặp lại bất chấp số lần lặp lại là bao nhiêu. Nếu số lần lặp lại lên đến con số hàng triệu hàng tỷ th́ con người không đủ sức và thời gian để làm, nhưng máy tính th́ có thể giải quyết trong chớp mắt. Điểm mạnh của computer là ở chỗ nó không hề biết e ngại và mệt mỏi trước những công việc lặp đi lặp lại lên đến hàng triệu hàng tỷ lần. Và v́ thế, việc cộng tác giữa computer với con người là mô h́nh lư tưởng của lao động trí óc trong cuộc sống hiện đại.

Về mặt lịch sử, Tháp Hà Nội được E. Lucas phát hiện từ năm 1883, nhưng măi đến gần đây người ta mới nhận ra ư nghĩa hiện đại của nó. Hiện vẫn chưa rơ v́ sao Lucas lại gọi chồng đĩa trong bài toán là Tháp Hà Nội, mà không gọi là Tháp Bắc Kinh, hay Tháp Tokyo.

Tháp Hà Nội đă mở tung cánh cửa cho tương lai khi nhiều nghiên cứu lấy Tháp Hà Nội làm điểm xuất phát đă đạt được thành tựu mới:

(1) Nâng câu hỏi của Tháp Hà Nội lên một mức cao hơn, sao cho số lần chuyển đĩa là nhỏ nhất. Các nhà toán học đă phát hiện ra rằng Tháp Hà Nội có cùng bản chất với bài toán t́m Đường Hamilton (Hamilton Path) trên một h́nh giả phương cấp n (n-Hypercube), một bài toán cũng rất nổi tiếng.

(2) Nhà toán học D.G. Poole đă sáng tạo ra Lược Đồ Hà Nội - một tam giác có các đỉnh tương ứng với các cách sắp xếp đĩa trong Tháp Hà Nội, từ đó t́m ra những liên hệ lư thú giữa Tam giác Pascal với Lược đồ Hà Nội. Liên hệ này đă được công bố trong một công tŕnh mang một cái tên đầy liên tưởng: Pascal biết Hà Nội (Pascal knows Hanoi).

Hiện nay, tại một số đại học ở Australia, uy tín của sinh viên Việt Nam trong lĩnh vực lập tŕnh được đánh giá ngang với sinh viên Ấn Độ - một cường quốc lập tŕnh của thế giới, làm cho Tháp Hà Nội vốn đă nổi tiếng lại càng nổi tiếng hơn.

(Theo Tia Sáng, VNExpess)
Sưu tầm

--------------------------------------------------------------------------------------

Cách giải Bài toán:

Bài toán có 2 chiều, chiều nghịch dùng để phân tích bài toán và dùng để lập tŕnh, chiều thuận để thực hiện trên mô h́nh. Ở đây nguyên lí thực hiện (tức là cách hiểu bài toán) nằm ở chiều nghịch, c̣n cách thực hiện nằm ở chiều thuận. Chiều nghịch dùng cho dân lập tŕnh và chiều thuận dành cho dân toán.
Chiều nghịch th́ dân lập tŕnh hay gọi là bài toán đệ qui. Bài toán này có ví dụ đơn giản như sau: giaithừa(n)=giaithừa(n-1)*n. Muốn tính giai thừa của n th́ đơn giản, lấy n nhân với giai thừa của (n-1). C̣n giai thừa của (n-1) th́ tính sao? Đơn giản, cứ lấy (n-1) nhân với giai thừa của (n-2) …

- Chiều nghịch (nguyên lí): Muốn đưa n khối tṛn từ cột A (cột nguồn) sang cột C (cột đích) thông qua cột B (cột trung gian) th́ chỉ cần đưa (n-1) khối tṛn từ A qua B, rồi đưa 1 khối tṛn từ A qua C và cuối cùng là đưa (n-1) khối tṛn từ B qua C. Đă làm xong bài toán!!!
C̣n (n-1) khối tṛn từ A sang B th́ làm sao mà đưa? Đơn giản, khi đó xem A là cột nguồn, B là cột đích và C là cột trung gian. Việc tiến hành tương tự, đưa (n-2) khối từ cột nguồn qua cột trung gian, 1 khối từ cột nguồn sang cột đích và cuối cùng là (n-2) khối từ cột trung gian sang cột đích. C̣n về source code th́ sao, xin xem phần sau cùng v́ nếu viết ở đây sẽ có thể gây rối một vài bạn đọc không được học về lập tŕnh.

- Chiều thuận: Nói đơn giản để hiệu th́ như chiều nghịch đă nói. C̣n thực hiện (chiều thuận) th́ làm sao? Khối tṛn đầu tiên từ cột nguồn A th́ chuyển vào đâu? Cột trung gian B hay cột đích C?
Với khối tṛn đầu tiên th́ chuyển về cột đích (với n là số lẻ) và cột trung gian (với n là số chẳn). Xếp được 1 khối tṛn (khối nhỏ nhất) theo đúng yêu cầu th́ tiếp theo là xếp 2 khối tṛn theo đúng yêu cầu (2 khối nhỏ nhất và nhỏ nh́). Cứ xếp 2 khối đó vào cột c̣n lại so với lần đầu tiên và làm tiếp vớ 3, 4, … khối tṛn. Điều vừa nói được diễn đạt như sau:
Với n lẻ: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….
• 1 khối nhỏ nhất qua C (cột đích)
• 2 khối nhỏ nhất qua B (cột trung gian)
• 3 khối nhỏ nhất qua C (cột đích)
• 4 khối nhỏ nhất qua B (cột trung gian)
• Tiếp tục như trên
Với n chẳn: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….
• 1 khối nhỏ nhất qua B (cột trung gian)
• 2 khối nhỏ nhất qua C (cột đích)
• 3 khối nhỏ nhất qua B (cột trung gian)
• 4 khối nhỏ nhất qua C (cột đích)
• Tiếp tục như trên
Phát triển của cách làm trên: Muốn chuyển n khối tṛn từ cột nguồn sang cột đích th́ làm như sau (ở đây ta phải hiểu rơ cột nguồn không nhất thiết là cột A, cột đích là C hay cột trung gian là B mà phải hiểu tổng quát, có thể cột nguồn là B chẳng hạn (trong phép chuyển (n-1) cột từ cột B sang cột C như trong cách làm ở phần nghịch)):
Với n lẻ: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….
• 1 khối nhỏ nhất qua cột đích
• 2 khối nhỏ nhất qua cột trung gian
• 3 khối nhỏ nhất qua cột đích
• 4 khối nhỏ nhất qua cột trung gian
• Tiếp tục như trên
Với n chẳn: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….
• 1 khối nhỏ nhất qua cột trung gian
• 2 khối nhỏ nhất qua cột đích
• 3 khối nhỏ nhất qua cột trung gian
• 4 khối nhỏ nhất qua cột đích
• Tiếp tục như trên
- Như vậy th́ số lần chuyển cho bài toán là bao nhiêu? Với bài toán tháp Hà Nội chuyển n khối tṛn từ cột nguồn A sang cột đích C thông qua cột trung gian B th́ cần có 2^0 + 2^1 + 2^2 + … + 2^n lần chuyển.


* logo.jpg (445.19 KB, 3003x661 - xem 774 lần.)

* Landmark.jpg (41.4 KB, 250x350 - xem 928 lần.)
« Sửa chữa bởi: 11/12/2008, 12:01 bởi canlong » Địa chỉ IP đã được lưu lại
Trang: [1]   Chuyển lên
  In ấn  
 
Chuyển tới:  

Liên hệ Ban quản trị diễn đàn: ASEAN TIMES ONLINE
+84 9 8888 7890 | E-mail: admin@ashui.com
URLs: vnarchitects.ashui.com, vnarchitects.com
© 2008 VNArchitects | Ashui® Corporation
Hỗ trợ bởi MySQL Hỗ trợ bởi PHP Valid XHTML 1.0! Valid CSS!
Powered by SMF 1.1.4 | SMF © 2005, Simple Machines LLC