c語言怎么循環加數組實現漢諾塔

蝸牛 互聯網技術資訊 2022-01-31 114 0

今天小編給大家分享一下c語言怎么循環加數組實現漢諾塔的相關知識點,內容詳細,邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。

簡介

漢諾塔問題是學數據結構與算法的時候會遇到的問題,相信來看本文的讀者應該都對漢諾塔問題有基本的了解,理論上所有的遞歸都可以改成循環,常規的做法是借助堆棧,但是我一想好像用循環加數組也可以實現,于是就有了本文,實現聲明,本文最后出來的算法效率不高的,比直接用遞歸實現還要差很多,追求算法效率的同學就不用看這個了。
題目:假設有3個柱子,分別為A、B、C,A柱子上有數量為n個的空心圓盤,從上到下序號分別為1...n,要求把A柱子中的n個圓盤移動到C柱中,且序號大的盤子必須在在需要小的圓盤下方。
思路:如果只有1個圓盤需要移動,則直接從A柱移動到C柱,如果有n個圓盤(n>1)需要移動,則需要先把n-1個圓盤從A柱移動到B柱,再把第n個圓盤從A柱移動到C柱,最后把原來的n-1個圓盤從B柱移動到C柱。

例如:

將1個圓盤從A柱移動到C柱只需要1個步驟:

1. 把圓盤1從A移動到C

將2個圓盤從A柱移動到C柱需要3個步驟:

1. 把圓盤1從A移動到B
2. 把圓盤2從A移動到C
3. 把圓盤1從B移動到C

將3個圓盤從A柱移動到C柱需要7個步驟:

1. 把圓盤1從A移動到C
2. 把圓盤2從A移動到B
3. 把圓盤1從C移動到B
4. 把圓盤3從A移動到C
5. 把圓盤1從B移動到A
6. 把圓盤2從B移動到C
7. 把圓盤1從A移動到C

遞歸的漢諾塔解法(c語言)

可以看出下面的遞歸算法的時間復雜度為O(2^n),因為存在有調用2^n-2次遞歸調用和1次原生printf;而空間復雜度為O(n),因為運行時棧中最多會同時保存n個函數的調用信息。

#include?<stdio.h>
#include?<stdlib.h>
#include?<math.h>

void?towers(int?n,?char?from,?char?to,?char?aux);
int?main()?{
????towers(3,?'A',?'C',?'B');
????return?0;
}

void?showMove?(int?order,?char?from,?char?to)?{
????printf("move?disk?%d?from?%c?to?%c\n",?order,?from,?to);
}

void?towers(int?n,?char?from,?char?to,?char?aux)?{
????if?(n==1)?{
????????showMove(n,?from,?to);
????????return;
????}
????towers(n-1,?from,?aux,?to);
????????showMove(n,?from,?to);
????towers(n-1,?aux,?to,?from);
}

解釋一下代碼中參數的含義,void towers(int n, char from, char to, char aux)的意思是把n個圓盤從from柱子移動到to柱子,中間可以借用aux柱子。

分析一下上面的遞歸執行過程:

我們已經知道把1個圓盤從from移動到to的步驟是showMove(1, from, to);

而把2個圓盤從from移動到to的步驟是,先照著移動1個圓盤的操作,把前面1個圓盤從from移動到aux,再把第2個圓盤從from移動到to,最后按照移動1個圓盤的操作,把剛才的1個圓盤從aux移動到to。

同理,把3個圓盤從from移動到to的步驟是,先照著移動2個圓盤的操作,把前面2個圓盤從from移動到aux,再把第3個圓盤從from移動到to,最后按照移動2個圓盤的操作,把剛才的2個圓盤從aux移動到to。

所以,把n個圓盤的操作從from移動到to的步驟是,先照著移動n-1個圓盤的操作,把前面n-1個圓盤從from移動到aux,再把第n個圓盤從from移動到to,最后按照移動n-1個圓盤的操作,把剛才的n-1個圓盤從aux移動到to。

因此,我們可以記錄移動1個圓盤的步驟,來得到移動2個圓盤的步驟,通過移動2個圓盤的步驟來得到移動3個圓盤的步驟,...最后得到移動n個圓盤的步驟。經過分析可以知道移動n個圓盤一共會有2^n-1個步驟

循環實現漢諾塔問題(c語言)

為了代碼更加易懂,這里寫了注釋,修改了部分變量命名,統一用數組保存步驟集合,最后才輸出。
可以看出這個算法的時間復雜度還是O(2^n),一共會執行2^(n+1)-1次setMoveAction語句和2^n-1次,printf語句,比起直接用遞歸還要復雜一些,而空間復雜度也是O(2^n),屬于沒什么用的算法,就是隨便寫寫。

#include?<stdio.h>
#include?<stdlib.h>
#include?<math.h>

void?towers(int?n,?char?from,?char?to,?char?aux);
int?main()
{
????towers(3,?'A',?'C',?'B');
????return?0;
}

void?showMove(int?order,?char?from,?char?to)
{
????printf("move?disk?%d?from?%c?to?%c\n",?order,?from,?to);
}

typedef?struct
{
????int?order;
????char?from;
????char?to;
}?MoveAction;

void?setMoveAction(MoveAction?*p,?int?order,?char?from,?char?to)
{
????p->order?=?order;
????p->from?=?from;
????p->to?=?to;
}

char?compare_map(char?c,?char?left,?char?right)?{
????if?(c?==?left)?{
????????return?right;
????}?else?if?(c?==?right)?{
????????return?left;
????}
????return?c;
}

void?towers(int?n,?char?from,?char?to,?char?aux)
{
????MoveAction?*actions,?action;
????int?i,?k,?size;
????char?f,?t;

????actions?=?(MoveAction?*)calloc(pow(2,?n?-?1)?-?1,?sizeof(MoveAction));
????setMoveAction(&actions[0],?1,?from,?to);
????size?=?1;

????for?(i?=?2;?i?<=?n;?i++)
????{
????????//本次循環會將把i個盤子從from移動到to的步驟記錄到actions數組中
????????//?設size是把i-1個盤子從from移動到to的步驟數,
????????//?則本次循環中集合{actions[x]?|?0?<=?x?<=?size?-1?}就是size是把i-1個盤子從from移動到aux的步驟集合,
????????//而action[size]是把第i個盤子從from移到to,
????????//而集合{actions[x]?|?size?+?1?<=?x?<=?2*size?}就應該是把i-1個盤存從aux移動到to的步驟集合

????????//?倒序,先求解集合{actions[x]?|?size?+?1?<=?x?<=?2*size?}
????????for?(k?=?0;?k?<?size;?k++)
????????{
????????????action?=?actions[k];
????????????f?=?compare_map(action.from,?from,?aux);
????????????t?=?compare_map(action.to,?from,?aux);
????????????setMoveAction(&actions[k?+?size?+?1],?action.order,?f,?t);
????????}
????????//?求解action[size]
????????setMoveAction(&actions[size],?i,?from,?to);
????????//?求解集合{actions[x]?|?0?<=?x?<=?size?-1?}
????????for?(k?=?0;?k?<?size;?k++)
????????{
????????????action?=?actions[k];
????????????f?=?compare_map(action.from,?to,?aux);
????????????t?=?compare_map(action.to,?to,?aux);
????????????setMoveAction(&actions[k],?action.order,?f,?t);
????????}
????????size?=?size?*?2?+?1;
????}

????for?(i?=?0;?i?<?size;?i++)
????{
????????showMove(actions[i].order,?actions[i].from,?actions[i].to);
????}
}

以上就是“c語言怎么循環加數組實現漢諾塔”這篇文章的所有內容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學習更多的知識,請關注蝸牛博客行業資訊頻道。

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:niceseo99@gmail.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

評論

日本韩欧美一级A片在线观看