iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
自我挑戰組

大二萌新的學習紀錄系列 第 29

Day 29 : C語言 - 河內塔的程式遞迴執行順序為何?

如標題,這篇想用「圖解」去解釋河內塔的「程式遞迴執行順序」為何
因為當初C有一項作業,叫我們用程式去寫出河內塔的執行結果

但我實在是不會寫,於是去網路上查,雖然是查到該怎麼撰寫了,但它的遞迴執行順序實在是很不直覺,單用想的會想破頭
最後我是用小畫家一個一個畫出順序才想通它,所以想和各位分享一下


首先,要先說說河內塔是什麼
有三個半徑不一樣的環,「由大到小」依序往上堆疊,你要將A柱子的三個環移動到C柱子,且大環不能疊在小環上

它的初始樣子如下圖所示:
https://ithelp.ithome.com.tw/upload/images/20211013/201410888tUOKhPGfV.png


現在你要用程式將它們的執行次數和順序依序列印出來,n值代表有幾個環:

void example_1(int n, char A, char B, char C) {
	if(n==1) {
		printf("盤子從%c移到%c\n", A, C);
	} else {
		example_1(n-1, A, C, B);
		printf("盤子從%c移到%c\n", A, C);
		example_1(n-1, B, A, C);
	}
}
int main() {
	int n;
	printf("請輸入n:");
	scanf("%d", &n);
	example_1(n, 'A', 'B', 'C');
	return 0;
}

結果如下圖所示:
https://ithelp.ithome.com.tw/upload/images/20211013/20141088AwuAXAh0gt.png


它的執行順序如果畫樹狀圖是長這樣,「最前面的數字」是n值,「剩下的」分別為example_1這個函數所接收到的char A, Char B, Char C的順序
「藍色字」是它會進if還是else,「綠色字」是它的印出順序結果
https://ithelp.ithome.com.tw/upload/images/20211013/20141088BB4u6KiUkM.png

那為什麼順序2、4、6會分別寫在那呢?因為你執行完第一個example_1函數,會跳回「原本的else」繼續執行,而下一個執行的是printf,最後才是第二個example_1函數

else {
	example_1(n-1, A, C, B);
	printf("盤子從%c移到%c\n", A, C);
	example_1(n-1, B, A, C);
}

所以它的整體執行順序如下圖所示:
https://ithelp.ithome.com.tw/upload/images/20211013/201410882zLeb5NhPN.png


那我們現在來看它「實際移動」的圖,看它是如何從柱子A移到柱子C的:

順序1:
https://ithelp.ithome.com.tw/upload/images/20211013/20141088hiUxQ7jGgD.png

順序2:
https://ithelp.ithome.com.tw/upload/images/20211013/20141088bJL07eIuyv.png

順序3:
https://ithelp.ithome.com.tw/upload/images/20211013/20141088B866h8OWZ3.png

順序4:
https://ithelp.ithome.com.tw/upload/images/20211013/20141088FKLaXjJfzh.png

順序5:
https://ithelp.ithome.com.tw/upload/images/20211013/201410889r2RWUl9qX.png

順序6:
https://ithelp.ithome.com.tw/upload/images/20211013/20141088gSYptYiebz.png

順序7:
這樣就移動成功囉!總共移動的次數為7次
https://ithelp.ithome.com.tw/upload/images/20211013/20141088p1sSA3aetQ.png


以上就是今天的介紹

希望大家看完能對河內塔的程式遞迴執行順序更加了解!


參考資料:
https://lakesd6531.pixnet.net/blog/post/332283123


上一篇
Day 28 : C語言 - 如何解決用scanf連續輸入時,程式會自動斷行的問題?
下一篇
Day 30 : 媽!我完賽了!
系列文
大二萌新的學習紀錄30

尚未有邦友留言

立即登入留言