資料結構 習題 1-5

這章主要是用函數遞迴的概念

1.
輸入多項式之各項係數、最高次方、代入之x值，
用Horner法運算函數值，做法比直接硬爆來的好，
在打這篇時，
原檔早就被第二題蓋掉了......
有錯誤請指正~

2.
輸入一數n並產生所有可能的真值排列
這是參考程式1.12所想出來的方法(不然我真不知道怎麼輸出......)

6.
階乘的運算，輸入一數n輸出n的階乘
遞迴法：
疊代法：
基本上這題算是基本中的基本......

7.
費氏數列
其實不用我多說......「費事」數列：
偷懶點兒，註解部分是遞迴法。

8.
輸入n,m計算出「n取m」之值：
沒什麼好說的。

9.
輸入n列出二項式係數(x+y)^n：
改變8.之函數C(n,m)成疊代

10.
Ackermann函數試做：
疊代我真的不知道該怎麼寫只好查wiki......
結果當m超過3時整個爆掉，
這台1.6GHz的NB要算到何年何月啊？
所以公式只寫到m=1~3。

12.
輸入一整數n判斷是否為完全數
結果還是要各用一次mod和除法，
這樣複雜度到底是？

13.
證明以下敘述會結束：
提示為x=(2*i+1)*2^k-1用歸納法
很容易知道只要x是偶數，就結束。 先將k=1
x=2*(2*i+1)-1
f=f(f(6*(2*i+1)-3+1))
=f(f(6*(2*i+1)-2))
=f(3*(2*i+1)-1)
=f(6*i+2)
=3*i+1
此敘述會結束
假設x=(2*i+1)*2^k-1敘述會結束
則x=(2*i+1)*2^(k+1)-1時
f=f(f(3*(2*i+1)*2^(k+1)-3+1))
=f(f(6*(2*i+1)*2^k-2))
=f(3*(2*i+1)*2^k-1)
讓m=3*i+1
f(3*(2*i+1)*2^k-1)
=f((2*m+1)*2^k-1)
=3*m+1
會結束
所以對所以正整數x，此敘述會結束。

14.
列出所有超集(powerset)：
此題「超級」難......
到網上搜尋了一下才恍然大悟！
15.
河內塔
很不直觀的寫法：