Thuật toán tháp hà nội

THÁP HÀ NỘITrò đùa trí tuệ của An namTrò đùa được đem đến từ Bắc KìBởi gs N. CLAUS (của SIAM)Trường cao đẳng Quan Li-Sou-Stian!

Trò chơi này được kiếm tìm thấy, lần đầu, vào cuốn sách được minh họa quan thoại FER-FER-TAM-TAM, đang rất được xuất bản, trong tương lai gần, bởi cơ quan chính phủ Trung Hoa. Tháp hà nội thủ đô có những đĩa, nhỏ dần, có số lượng thay đổi, mà chúng tôi làm bởi gỗ, tất cả lỗ ngơi nghỉ giữa. Ở Nhật Bản, Trung Quốc, cùng ở Bắc Kì, chúng được gia công bằng sứ.Trò nghịch có mục đích là tháo bỏ các đĩa, với đặt vào cột mặt cạnh, theo các quy tắc tuyệt nhất định.

Bạn đang xem: Thuật toán tháp hà nội

Vui và ngã ích, dễ học và đơn giản trong thành phố, quanh đó nông thôn, bên trên chuyến du lịch, nó được tạo thành để mang đến kiến thức khoa học, giống mọi trò đùa kỳ thú và mới mẻ của gs N. CLAUS (của SIAM).

Theo một thần thoại Ấn Độ, những người Brahmin đã tiếp nối nhau vào một thời gian dài để biến hóa Đền Bernares, dịch rời 64 đĩa vàng của tòa án nhân dân tháp Brahma, trạm kim cương từ Golconde. Khi công việc hoàn thành, thành tựu và Brahmin sẽ đổ, với lúc sẽ là thời điểm chấm dứt của vũ trụ!

——————–

PARIS, BẮC KINH, Ý ĐÔ và SÀI GÒNTrong các hiệu sách và tiệm bán hàng mới lạ1883

Bản quyền sẽ giữ

Đó là tờ giới thiệu thứ nhất do Pháp sản xuất reviews về trò nghịch Tháp Hà Nội, trò chơi được dựa vào bài toán thuộc tên. Xung quanh bài toán này là những thứ thú vị khác mà họ sẽ nói về sau đây.

I – Nội dung bài bác toán

Trong một ngôi đền rồng thiêng liêng có bố chiếc cọc bằng kim cương, được chôn chặt, thẳng đứng. Ông trời sẽ xếp 64 chiếc đĩa kim cương có những đường kính không giống nhau và tất cả lỗ sinh hoạt giữa vào một chiếc cọc theo trang bị tự to lớn trước nhỏ tuổi sau (vì vậy mới mang tên là tháp). Làm nắm nào gửi từng mẫu một tổng thể 64 chiếc đĩa đó sang loại cọc đồ vật ba trải qua chiếc cọc sản phẩm hai với đk trong thừa tình gửi ở cả cha cọc, những đĩa khổng lồ không lúc nào được ở trên những đĩa nhỏ dại hơn chúng, và tần số chuyển là bao nhiêu?

Tổng quát tháo hơn, ta có:

Cho trước bố chiếc cọc chôn thẳng đứng. Trên một cọc đang xếp n (n = 1, 2…) đĩa có đường kính khác nhau chiếu thẳng qua lỗ thủng nghỉ ngơi giữa. Đĩa khổng lồ nằm dưới, đĩa nhỏ hơn nằm trên. Vấn đề đặt ra là làm chũm nào để đưa từng cái một toàn cục số đĩa đó sang chiếc cọc lắp thêm ba trải qua chiếc cọc sản phẩm công nghệ hai với yêu ước trong quá trình chuyển, nghỉ ngơi cả tía cọc luôn có trơ tráo tự đĩa to lớn nằm bên dưới đĩa bé nằm trên.

II – giải thuật cho vấn đề tổng quát

Chúng ta sẽ bắt đầu phân tích những trường hợp dễ dàng để tìm phía giải.

Xem thêm: Sinh Nhật Mạng Viettel: Nhận Thẻ Cào Viettel Miễn Phí 10K, 20K, 50K

Với

Với giải thuật cho trường vừa lòng
*
.

Điểm tầm thường của hai cách chơi trên là ta đều bắt buộc chuyển được toàn bộ (n-1) đĩa nhỏ tuổi qua cột vật dụng hai, gửi đĩa to duy nhất qua cột thứ tía rồi chuyển (n-1) đĩa trường đoản cú cột sản phẩm hai lịch sự cột trang bị ba. Trò nghịch sẽ kết thúc!

Nếu hotline

*
là số cách để dịch rời n đĩa qua cột ta đề nghị thì:

Bước 1: chuyển
*
đĩa nhỏ nhiều hơn từ cột
*
sang trọng cột
*
. Chúng ta có
*
cách di chuyển.

Bước 2: đưa đĩa to duy nhất từ cột (1) sang trọng cột (3). Họ có 1 cách di chuyển.

Bước 3: chuyển

*
đĩa từ cột (2) sang trọng cột (3). Chúng ta có
*
cách di chuyển.

Vậy, số bước để dịch chuyển n đĩa từ bỏ cột (1) quý phái cột (3) chính là

*

và ta thuận tiện rút ra phương pháp tổng quát:

*

Với

*
, ta có việc Tháp tp. Hà nội và chu kỳ chuyển thành công là
*
, chính xác là phải rộng năm tỉ nạm kỉ (!) bắt đầu chuyển xong.

III – lịch trình C++ cho việc Tháp Hà Nội

#include #include using namespace std;void cach_chuyen(int x, int y, int z, int n) if(n==0)return;cach_chuyen(x,z,y,n-1);cout >n; cach_chuyen(1,2,3,n); return 0;Bạn đọc ước ao thử sức với trò chơi thú vị này hoàn toàn có thể chơi trực tuyến tại địa chỉ https://www.mathsisfun.com/games/towerofhanoi-flash.html