hdu 1005

題目大意：中文題，可以直接在OJ上看

解題思路:本題如果直接遞歸的話很有可能會OVER STACK。

1)本題的關鍵是找到循環節,即(arr[i] == 1 && arr[i - 1] == 1)

2)

又是一道給出了運算公式的數學凡是沒有優化的話，超時超內存等等是避免不了的了。這題很顯然是一個找規律的題目，也就是該題的求解中是存在循環節的。對於公式 f[n] = A * f[n-1] + B * f[n-2]; 後者只有7 * 7 = 49 種可能，為什麼這麼說，因為對於f[n-1] 或者 f[n-2] 的取值只有 0,1,2,3,4,5,6 這7個數，A，B又是固定的，所以就只有49種可能值了。由該關系式得知每一項只與前兩項發生關系，所以當連續的兩項在前面出現過循環節出現了，注意循環節並不一定會是開始的 1，1 。 又因為一組測試數據中f[n]只有49中可能的答案，最壞的情況是所有的情況都遇到了，那麼那也會在50次運算中產生循環節。找到循環節後，就可以輕松解決了。

代碼如下：

[cpp
//Problem:hdu1005  
 
#include <iostream>  
using namespace std; 
 
int arr[10000];  
  
int main() 
{ 
    int A,B,n; 
    //freopen("E:\\in.txt","r",stdin);  
    arr[1] = arr[2] = 1; 
    while(cin>>A>>B>>n, A || B || n) 
    { 
        int i; 
        for(i=3; i<10000 ;i++) 
        { 
            arr[i] = (A*arr[i-1] + B*arr[i-2]) % 7; 
             
            //如果有兩個連著 =1，則後面的全部和前面相同，即出現了周期  
            //這時就沒必要再進行下去了，跳出循環, i-2為周期   
            if(arr[i] == 1 && arr[i-1] == 1)             
                break; 
        } 
        n = n % (i-2); 
         
        // 把n對周期求模，當n = i-2時, n=0,此時本來應該取arr[i-2]的，所以把arr[0]=arr[i-2]   
        //也可以這樣：  
        //if(n==0)   n=i-2;   
                    
        arr[0] = arr[i-2]; 
         
        cout << arr[n] << endl; 
    } 
    return 0; 
} 

//Problem:hdu1005

#include <iostream>
using namespace std;

int arr[10000];
 
int main()
{
 int A,B,n;
 //freopen("E:\\in.txt","r",stdin);
 arr[1] = arr[2] = 1;
 while(cin>>A>>B>>n, A || B || n)
 {
  int i;
  for(i=3; i<10000 ;i++)
  {
   arr[i] = (A*arr[i-1] + B*arr[i-2]) % 7;
   
   //如果有兩個連著 =1，則後面的全部和前面相同，即出現了周期
   //這時就沒必要再進行下去了，跳出循環, i-2為周期
   if(arr[i] == 1 && arr[i-1] == 1)   
    break;
  }
  n = n % (i-2);
  
  // 把n對周期求模，當n = i-2時, n=0,此時本來應該取arr[i-2]的，所以把arr[0]=arr[i-2]
  //也可以這樣：
  //if(n==0)  n=i-2;
            
  arr[0] = arr[i-2];
  
  cout << arr[n] << endl;
 }
 return 0;
}

2)也可以如下:

[cpp] 
/*
 * 1005_1.cpp
 *
 *  Created on: 2013年8月10日
 *      Author: Administrator
 */ 
 
 
#include <iostream>  
int A,B; 
int f(int n){ 
    if( n == 1 || n == 2){ 
        return 1; 
    } 
    return (A*f(n-1)+B*f(n-2))%7; 
} 
int main(){ 
 
    int n; 
    while(scanf("%d%d%d",&A,&B,&n)!=EOF,A||B||n){ 
        int a = f(n%49); 
        printf("%d\n",a); 
    } 
} 

/*
 * 1005_1.cpp
 *
 *  Created on: 2013年8月10日
 *      Author: Administrator
 */

#include <iostream>
int A,B;
int f(int n){
 if( n == 1 || n == 2){
  return 1;
 }
 return (A*f(n-1)+B*f(n-2))%7;
}
int main(){

 int n;
 while(scanf("%d%d%d",&A,&B,&n)!=EOF,A||B||n){
  int a = f(n%49);
  printf("%d\n",a);
 }
}