1樓：116貝貝愛
^^^^解：令f(1)=c
f(2)=2c+2
f(4)=2(2c+2)+4 = 4c+8
f(8) = 2(4c+8)+8 = 8c+24
f(16) = 2(8c+24)+16 = 16c+64
f(2^k) = c*2^k + p(k)
考慮p(k)
p(0) = 0
p(1) = 2 *p(0) + 2
p(2) = 2*p(1)+4
p(n-2) = 2*p(n-3)+2^(n-2)
p(n-1) = 2*p(n-2)+2^(n-1)p(n)
= 2* p(n-1) + 2^n = 2*2*p(n-2)+2*2^(n-1)+2^n
= 4p(n-2)+2*2^n
= 4*2p(n-3)+4*2^(n-2)+2*2^n
歸納得到p(n) = 2^kp(n-k)+k*2^n = 2^np(n-n)+n*2^n =n*2^n
所以p(n-1) = (n-1)2^(n-1)
2*p(n-1)+2^n = 2*(n-1)*2^(n-1) + 2^n=p(n) 得到驗證
帶回f(2^k)得到f(2^k) = c*2^k+k*2^k，對於任意常數c成立
性質：1、 子問題須與原始問題為同樣的事，且更為簡單。
2、不能無限制地呼叫本身，須有個出口，化簡為非遞迴狀況處理。
3、由一種（或多種）簡單的基本情況定義的一類物件或方法，並規定其他所有情況都能被還原為其基本情況。
4、遞迴演算法解題相對常用的演算法如普通迴圈等，執行效率較低。因此，應該儘量避免使用遞迴，除非沒有更好的演算法或者某種特定情況，遞迴更為適合的時候。在遞迴呼叫的過程當中系統為每一層的返回點、區域性量等開闢了棧來儲存。
遞迴次數過多容易造成棧溢位等。
2樓：不思議
記n = 2^k, f(n) = f(2^k) = h(k),
那麼有h(k) = 2*h(k-1) + c*2^k
記 // sigama就是求和號，這裡打不出來，只好這樣寫
// sigama[k=0,無窮]分別是求和號的下標和上標
g(x) = sigama[k=0,無窮] h(k)*x^k
2x*g(x) = sigama[k=0,無窮] 2*h(k)*x^(k+1)
g(x)-2*x*g(x) = (1-2x)*g(x)
= h(0) + sigama[k=0,無窮] (h(k+1) - 2*h(k))*x^(k+1)
= h(0) + c * sigama[k=0,無窮] 2^(k+1)*x^(k+1)
= h(0) + c * sigama[k=0,無窮] (2*x)^(k+1)
= h(0) + c * (2*x/(1-2*x))
故g(x) = h(0)/(1-2*x) + c * (2*x/(1-2*x)^2)
= h(0)/(1-2*x) + c * (1/(1-2*x)^2 - 1/(1-2*x))
= (h(0) - c) * 1/(1-2*x) + c * 1/(1-2*x)^2
= (h(0) - c) * sigama[k=0,無窮] (2*x)^k
+ c * sigama[k=0,無窮] (k+1)(2*x)^k
// 為了方便計算設f(1) = h(0) = 0, f(2) = h(1) = 2*c
// 其實不這樣設也可以的，計算過程與下面類似
= (- c) * sigama[k=0,無窮] (2*x)^k
+ c * sigama[k=0,無窮] (k+1)(2*x)^k
= c * sigama[k=0,無窮] k * (2*x)^k
= sigama[k=0,無窮] c * k * (2*x)^k
= sigama[k=0,無窮] h(k)*x^k
所以h(k) = c * k * 2^k,
而n = 2^k
則f(n) = h(k) = c * k * 2^k = c * n * log2 n;
// log2 n 表示以2為底的對數
f(n) = o(n * log2 n)
Excel中如何用方程式函式作圖
您可以試試以下操作 1.選擇兩列 一列 a 作為x，一列 b 作為y，如果y x平方 2，可以將第一版列從1.14,在第二列輸權 入 a1 a1 2 回車，然後往下填充，知道第14行。2.在空白地方插入圖表，選擇型別為折線圖，子圖為第一個圖，下一步輸入a b兩列，完成即可。希望對您解決問題能有所幫助...
用C語言或C 遞迴函式生成Catalan三角形的數
include define n 20 void fun int arr n int r,int c,int n else if c 0 else if r c else int main return 0 c 程式設計計算卡特蘭數的 用無符號64位計算 最高可以計算33個卡特蘭數 如果還需要更大 ...
如何用matlab求解時滯偏微分方程組
這是matlab中dde23的例抄 子,通過這個例襲子,應該能看懂dde23個引數的作用.直接複製後邊的 就可以輸出圖形.ddex1 example 1 for dde23.this is a example of wille and baker that illustrates the strai...