IngeniousHax, on 02 August 2012  02:26 PM, said:
Try O(2^n)
Posted 19 August 2012  09:07 PM
#include <iostream.h> void main() { int n; double a=1, b=1, c; cout << "Please enter the number of terms: "; cin >> n; if (n==1) { cout << "1"; } else if(n==2) { cout << "1\t1"; } else { cout << "1\t1\t"; for (int i=3; i<=n; i++) { c=a+b; cout << c << "\t"; a=b; b=c; } } }
This post has been edited by jimblumberg: 19 August 2012  09:19 PM
Reason for edit:: Added spoiler tags
Posted 20 August 2012  04:14 AM
IngeniousHax, on 02 August 2012  09:26 PM, said:
#include<iostream> #include<vector> using namespace std; vector<unsigned> memo; unsigned fib(int); int main() { for(int i = 0; i < 20; i++) memo.push_back(0); for(int i = 0; i < 20; i++) cout << fib(i) << " "; cout << endl; return 0; } unsigned fib(int n) { if(n == 0  n == 1) return n; return memo[n] ? memo[n] : (memo[n] = fib(n1)+fib(n2)); }
This post has been edited by mostyfriedman: 20 August 2012  05:01 AM
Posted 25 September 2012  11:32 AM
#include <iostream> using namespace std; int n = 0; int x = 1; int main() { while(x < 2000000000) { if(n < 1000000000) { n = x+n; // No DAMN idea how this works, x = nx; // But it somehow does! cout << n << endl; } } }
This post has been edited by lukeme99: 25 September 2012  12:01 PM
Posted 25 September 2012  12:46 PM
Quote
int x=0; //f(n), currently f(0) int y=1; //f(n1), currently f(1)? . . //Loops . . //right now, x has f(n) and y has f(n1) x = y+x; // calculates f(n+1) from f(n1)+f(n) and stores result in x. We no longer have f(n) //x currently has f(n+1), y has f(n1) y = xy; // calculates f(n) from f(n+1) and f(n1) //ready for the next iteration of finding f(x+2) since x has f(n+1) and y has f(n)
x y 0 1 1 0 1 1 2 1 3 2 5 3 8 5
Posted 26 September 2012  10:07 AM
mojo666, on 25 September 2012  08:46 PM, said:
Quote
int x=0; //f(n), currently f(0) int y=1; //f(n1), currently f(1)? . . //Loops . . //right now, x has f(n) and y has f(n1) x = y+x; // calculates f(n+1) from f(n1)+f(n) and stores result in x. We no longer have f(n) //x currently has f(n+1), y has f(n1) y = xy; // calculates f(n) from f(n+1) and f(n1) //ready for the next iteration of finding f(x+2) since x has f(n+1) and y has f(n)
x y 0 1 1 0 1 1 2 1 3 2 5 3 8 5
Posted 27 September 2012  03:39 PM
#include <iostream> #include <vector> template<int N> struct meta_fib { enum { val = meta_fib<N1>::val + meta_fib<N2>::val }; static void add(std::vector<int> &vec) { meta_fib<N1>::add(vec); vec.push_back(val); } }; template<> struct meta_fib<0> { enum { val = 0 }; static void add(std::vector<int> &vec) { vec.push_back(val); } }; template<> struct meta_fib<1> { enum { val = 1 }; static void add(std::vector<int> &vec) { meta_fib<0>::add(vec); vec.push_back(val); } }; int fib(int n, std::vector<int> &fib_table) { return fib_table[n]; } int main() { static std::vector<int> ft; meta_fib<45>::add(ft); for(int i=0; i<=45; i++) std::cout<<"F("<<i<<") = "<<fib(i, ft)<<std::endl; std::cin.ignore(); std::cin.get(); return 0; }
This post has been edited by jjl: 27 September 2012  03:43 PM
Posted 01 October 2012  09:37 PM
#include "stdafx.h" #include <map> using namespace std; map<int, long> fibonacci; long Fib(int i) { if (i < 1) return 0; if (i == 1) return 1; if (fibonacci.find(i) == fibonacci.end()) { fibonacci[i] = Fib(i  1) + Fib(i  2); } return fibonacci[i]; } int main(int argc, char* argv[]) { for (int i=0; i <= 45; i++) printf("%4i => %i\n", i, Fib(i)); return 0; }
Query failed: unknown local index 'forums_search_posts_main' in search request.
