?
漢諾塔(又稱河內塔)問題是源于印度一個古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，
作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
漢羅塔問題背景介紹
漢諾塔問題，是心理學實驗研究常用的任務之一，該問題的主要材料包括三根高度相同的柱子和一些大小及顏色不同的圓盤，三根柱子分別為起始柱A、輔助柱B及目標柱C，
相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲，該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤，游戲的目標：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好，操作規則：每次只能移動一個盤子，并且在移動程序中三根桿上都始終保持大盤在下，小盤在上，操作程序中盤子可以置于A、B、C任一桿上，（摘自百度百科）
?
從上面的資料我們可以提取出一個問題：
Hanoi（漢諾）塔問題，古代有一個梵塔，塔內有3個座A,B,C，開始時A座上有64個盤子，盤子大小不等，大的在下，小的在上，有一個先知想把這64個盤子從A座移到C座，但規定每次只允許移動一個盤，且在移動程序中在3個座上都始終保持大盤在下，小盤在上，在移動程序中可以利用B座，你能幫這位先知實作他的想法嗎？要求編程式輸出移動盤子的步驟，
解題思路:
這位先知會這樣想: 假如有另外一位先知能有辦法將上面63個盤子從A座移到B座，那么，問題就解決了，此時先知只須這樣做:
① 聯系他的好朋友第2個先知將63個盤子從A座移到B座；
② 自己將1個盤子（最底下的、最大的盤子）從A座移到C座；
③ 再讓第2個先知將63個盤子從B座移到C座，
第2個先知又想: 如果有人能將62個盤子從一個座移到另一座，我就能將63個盤子從A座移到B座，他是這樣做的:
① 聯系他的好朋友第3個先知將62個盤子從A座移到C座；
② 自己將1個盤子從A座移到B座；
③ 再讓第3個先知將62個盤子從C座移到B座，
……
以此類推
為了便于理解，我們將盤子數量降低到3個，所以首先分析將A座上3個盤子移到C座上的程序：
① 將A座上2個盤子移到B座上（借助C座），
② 將A座上1個盤子移到C座上，
③ 將B座上2個盤子移到C座上（借助A座），
其中第②步可以直接實作，第①步又可用遞回方法分解為:
- 將A座上1個盤子從A座移到C座；
- 將A座上1個盤子從A座移到B座；
- 將C座上1個盤子從C座移到B座，
第③步可以分解為:
- 將B座上1個盤子從B座移到A座上；
- 將B座上1個盤子從B座移到C座上；
- 將A座上1個盤子從A座移到C座上，
將以上綜合起來，可得到移動3個盤子的步驟為:
A→C，A→B，C→B，A→C，B→A，B→C，A→C，
共經歷7步，由此可推出: 移動n個盤子要經歷(2n-1)步，
由上面的分析可知: 將n個盤子從A座移到C座可以分解為以下3個步驟:
① 將A座上n－1個盤借助C座先移到B座上；
② 把A座上剩下的一個盤移到C座上；
③ 將n－1個盤從B座借助于A座移到C座上，
可以把上面3個步驟分成兩類操作:
① 將n－1個盤從一個座移到另一個座上（n＞1），這就是先知讓他的朋友第2個先知做的作業，它是一個遞回的程序，即先知將任務層層下放，直到第64個先知為止，——hanoi函式
② 將1個盤子從一個座上移到另一座上，這是先知自己做的作業，——move函式
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
/*Hanoi（漢諾）塔問題，古代有一個梵塔，塔內有3個座A,B,C，
開始時A座上有64個盤子，盤子大小不等，大的在下，小的在上，
有一個先知想把這64個盤子從A座移到C座，但規定每次只允許移動一個盤,
且在移動程序中在3個座上都始終保持大盤在下，小盤在上，
在移動程序中可以利用B座，你能幫這位先知實作他的想法嗎？
要求編程式輸出移動盤子的步驟，*/
void hanoi(int n, char a, char b, char c);定義hanoi函式
//將n個盤從a座借助b座,移到c座
void move(char x, char y);
int main()
{
int lay = 0;
scanf("%d", &lay);
hanoi(lay, 'A', 'B', 'C');//輸入盤子個數
//最終輸出移動方案
return 0;
}
void move(char x, char y)
{
printf("%c->%c\n", x, y);
}
void hanoi(int n, char a, char b, char c)
{
if (n == 1)
move(a, c);
else
{
hanoi(n - 1, a, c, b);//借c將a移動至b
move(a, c);
hanoi(n - 1, b, a, c);//借a將b移動至c
}
}
根據這個代碼讓我們來運行一下我們舉過移動三個圓盤的例子，
一共7步，與我們舉例得出的結果一致，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290530.html
標籤：其他
上一篇：scratch加法出題機 電子學會圖形化編程scratch等級考試三級真題和答案決議2021-3
下一篇：超級有用：針對python初學者，并根據最近做的機器人專案，淺談機器視覺模型在實際專案的思路和框架（ancacode，tensrflow-gpu，opencv-dnn，andriod）