請問各位大大 如何使用遞迴寫出費氏數列運算加法的次數呢 例: int fib(n){ if (n==0 || n==1) return n; else return fib(n-1) fib(n-2); } 如上,如果n為4,如何去計算總共執行了幾次加法呢? ps:需用遞迴之方法

landochu你好 你可以設個全域變數來計算次數,或是在呼叫fib的時候加的計算次數的指標 希望這對你有幫助

引言: 請問各位大大 如何使用遞迴寫出費氏數列運算加法的次數呢 例: int fib(n){ if (n==0 || n==1) return n; else return fib(n-1) fib(n-2); } 如上,如果n為4,如何去計算總共執行了幾次加法呢? ps:需用遞迴之方法

landochu你好： 直接用你的程式加 class="code"> ~~ int cnt=0; ~~ int fib(int n) { if (n==0 || n==1) return n; else { cnt ; return fib(n-1) fib(n-2); } } 硬要獨立寫一個recursive程式也行： int AddCnt(int n) { if (n==0 || n==1) return 0; else return 1 AddCnt(n-1) AddCnt(n-2); } 注意這裏參數n都是表示項數哦!

加個全域變數應該行的通    但..return 1+AddCnt(n-1)+AddCnt(n-2); 如果使用這個方法 會不會導致1加上AddCnt(n-1)+AddCnt(n-2)的值,而不只是單純的加1而以呢

引言:

引言: 請問各位大大 如何使用遞迴寫出費氏數列運算加法的次數呢 例: int fib(n){ if (n==0 || n==1) return n; else return fib(n-1) fib(n-2); } 如上,如果n為4,如何去計算總共執行了幾次加法呢? ps:需用遞迴之方法

landochu你好： 直接用你的程式加 class="code"> ~~ int cnt=0; ~~ int fib(int n) { if (n==0 || n==1) return n; else { cnt ; return fib(n-1) fib(n-2); } } 硬要獨立寫一個recursive程式也行： int AddCnt(int n) { if (n==0 || n==1) return 0; else return 1 AddCnt(n-1) AddCnt(n-2); } 注意這裏參數n都是表示項數哦! < face="Verdana, Arial, Helvetica">

引言: 加個全域變數應該行的通 但..return 1 AddCnt(n-1) AddCnt(n-2); 如果使用這個方法 會不會導致1加上AddCnt(n-1) AddCnt(n-2)的值,而不只是單純的加1而以呢

landochu你好： 加 >!

你應該是在最底層來算次數 例如f(4)=f(3)＋f(2)         =f(2)＋f(1)＋f(2)         =f(1)＋f(0)＋1＋f(1)＋f(0) =1＋1＋1＋1＋1 =5 這是費是數列演算法中計算次數的方法

引言: 你應該是在最底層來算次數 例如f(4)=f(3)＋f(2) =f(2)＋f(1)＋f(2) =f(1)＋f(0)＋1＋f(1)＋f(0) =1＋1＋1＋1＋1 =5 這是費是數列演算法中計算次數的方法

hdilwy你好： 不太瞭解你說的意思是在講什麼! 總之，以你提供的原程式為準的話： < class="code"> int fib (int n) { if (n==0 || n==1) return n; else return fib(n-1) fib(n-2); } 你要非常注意到，在 fib (int n) 中，n為項數值，所以例如說求某一項的值是這樣的： 第0項 = fib(0) = 0 第1項 = fib(1) = 1 第2項 = fib(2) = 1 第3項 = fib(3) = 2 . . . 依此類推 所以說假你要求第4項的值的話，就這樣： f(4) = f(3) f(2) = f(2) f(1) f(1) f(0) = f(1) f(0) f(1) f(1) f(0) = 1 0 1 1 0 = 3 所以你說f(4)=5是不對的! 另外以上述來說呢，共用了4次的加法，因為我們必需要拆解到這一步驟才能停止： f(4) = f(1) f(0) f(1) f(1) f(0) 所以共用了4次的加法，因為總共有4個〝 〞號出現，不再多也不能少! 我的範例程式結果應該是對的(測過)，也應該相當直覺的! 求 〝某一項的值是多少〞 和求 〝算某一項的值時共用了幾次加法〞是完全不相干的! 最後只要用遞迴解題的話，基本上都是會拆解到最底層的，這是遞迴的精神，只是使用 者比較感覺不到! All! 發表人 -