hdoj1005找规律

[c++]代码库

#include<iostream>
using namespace std;

int main(){
//如果仅仅用递归或递推都会超时
//关键：循环周期最大为49
	int a, b, c;
	int f1, f2, f3;
	int f4[51];
	f4[0] = f4[1] = 1;
	int index_i, index_j;
	for(cin>>a>>b>>c; a || b || c; cin>>a>>b>>c){
		f1 = 1;
		f2 = 1;
		for(int i = 2; i < 51; i++){//递推求解f（n）
			f3 = (a * f2 + b * f1) % 7;			
			int flag = 0;
			for(int j = 2; j < i; j++){//到数组中查找是否已有f（k）== f3;				
   				if(f4[j] == f3 && f4[j - 1] == f2 && f4[j - 2] == f1){
					index_i = i + 1;
					index_j = j + 1;					
					flag = 1;
					break;
				}
			}
			//cout<<"case f"<<i + 1<<" "<<f1<<" "<<f2<<" "<<f3<<" "<<endl;
			f1 = f2;
			f2 = f3;
			if(flag == 0){
				f4[i] = f3;
			}else{
				break;
			}
		}
		int temp;
		temp = (c - index_j) % (index_i - index_j);
		//cout<<index_j<<" "<<index_i<<endl;
		if(c > index_i - index_j){
			cout<<f4[index_j + temp - 1]<<endl;
		}else{
			cout<<f4[c - 1]<<endl;
		}
	}
	return 0;
}