1 2 3 4 5 6 7 | F0 = 0 F1 = 1 Fn = F(n-2) + F(n-1) if n >1 or F1 = 1 F2 = 1 Fn = F(n-2) + F(n-1) if n >2 |
1 2 3 4 5 6 | Fib(n): if n in range [0,1] return n else return Fib(n-2) + Fib(n-1) end if |
1 2 3 | T(n) = T(n-1) + T(n-2)+ Theta(1) >= 2 T(n-2) = Theta(2<sup>n/2</sup>) |
1 | long long fib_r(int n)<br>{<br> return n <= 1 ? n : fib_r(n-1) + fib_r(n-2) ; <br>} |
1 2 3 4 5 6 7 8 9 10 11 12 | Mem = { } //Data structure storing computed values Fib(n): if n in Mem //Return existing value from Memory return Mem[n] //Early exit when handling known values end if if n if n in range [0,1] //Base step of the recursion fib ? n else //Recursive steps fib ? Fib(n-2) + Fib(n-1) end if Mem[n] ? fib //Memorize new value return fib //Return the new computed value |
1 2 3 4 5 6 7 8 9 10 | Fib(n): Mem = {} //the memory for k in range [0,1,…,n] //traverse bottom-up if k in range [0,1] //compute each term Mem[k] ? k //starting with indices 0 and 1 else: Mem[k] ? Mem[k-1] + Mem[k-2] //Retrieve known values end if end for return Mem[n] |
1 2 3 4 5 6 7 8 9 10 11 12 | long long fib_d(int n) { int k; long long memory[n]; for ( k = 0 ; k <= n ; ++k ) { if ( k <= 1 ) memory[k] = k; else memory[k] = memory[k-1] + memory[k-2]; } return memory[n]; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | long long fib_i(int n) { int k; long long e0 = 0, e1 = 1, res = 0; for ( k = 0 ; k <= n ; ++k ) { //iterate from 0 to n if ( k <= 1 ) res = k; //base case for F0 and F1 else { res = e0 + e1; //res is the sum of 2 previous terms e0 = e1; //update the 2 previous terms e1 = res; // -------- ditto -------- } } return res; //return Fn } |
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) | Powered by Discuz! 7.0.0 |