母牛数量算法

pupilzeng

1. 
   
2. #include <iostream>;
   
3. #include <vector>;
   
4. #include <cstdlib>;
   
5. using namespace std;
   
6. 
   
7. int
   
8. main(int argc, char** argv)
   
9. {
   
10.         if(argc != 2)
    
11.         {
    
12.                 exit(1);
    
13.         }
    
14.         int year = atoi(argv[1]);
    
15.         vector<long long>; count(year, 1);
    
16.         for ( int i = 2; i < year; i ++)
    
17.                 count[i + 1] = count[i] + count[i - 2];
    
18.         cout << "In the " << year <<"th year, there are(is) "
    
19.              << count[year - 1] << " cows\n";
    
20. }
    

复制代码

关键就在那个for循环。
就是f(n) = f(n - 1) + f(n - 3) 的实现。[/code]

pupilzeng

1. 
   
2. #include <deque>;
   
3. #include <cstdlib>;
   
4. #include <iostream>;
   
5. using namespace std;
   
6. 
   
7. int
   
8. main(int argc, char** argv)
   
9. {
   
10.         if(argc != 2)
    
11.         {
    
12.                 cout << "just accept 1 parameter\n";
    
13.                 exit(1);
    
14.         }
    
15.         int year = atoi(argv[1]);
    
16.         deque<long long>; count(4, 1);
    
17.         count.pop_back();
    
18.         for ( int i = 2; i < year; i ++)
    
19.         {
    
20.                 count.push_back(count[0] + count[2]);
    
21.                 count.pop_front();
    
22.         }
    
23.         cout << "In the " << year <<"th year, there are(is) "
    
24.              << count[1] << " cows\n";
    
25. }
    

复制代码

同样是n级别的时间复杂度，但是空间复杂度变为1，deque的空间只有4.
不知道这个在时间上跟上一个有什么区别，不过估计也很难反映出来测试到117时就溢出了。