首页 > 代码库 > Poj 3982 序列

Poj 3982 序列

1.Link:

http://poj.org/problem?id=3982

2.Content:

序列
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7057 Accepted: 3182

Description

数列A满足An = An-1 + An-2 + An-3, n >= 3 

编写程序,给定A0, A1 和 A2, 计算A99

Input

输入包含多行数据 

每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767) 
数据以EOF结束

Output

对于输入的每一行输出A99的值

Sample Input

1 1 1

Sample Output

69087442470169316923566147

Source

3.Method:

套用大数相加模板

http://www.cnblogs.com/mobileliker/p/3512632.html

4.Code:

 1 #include <iostream> 2 #include <string> 3  4 using namespace std; 5  6 const int Num = 100; 7  8 string sum(string s1,string s2) 9 {10     if(s1.length()<s2.length())11     {12         string temp=s1;13         s1=s2;14         s2=temp;15     }16     int i,j;17     for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)18     {19         s1[i]=char(s1[i]+(j>=0?s2[j]-0:0));   //注意细节20         if(s1[i]-0>=10)21         {22             s1[i]=char((s1[i]-0)%10+0);23             if(i) s1[i-1]++;24             else s1=1+s1;25         }26     }27     return s1;28 }29 30 int main()31 {32     //freopen("D://input.txt","r",stdin);33 34     int i;35 36     string str0,str1,str2,str3;37 38     while(cin >> str0 >> str1 >> str2)39     {40         //cout << str0 << endl;41         //cout << str1 << endl;42         //cout << str2 << endl;43 44         i = Num - 3;45         while(i--)46         {47             str3 = sum(str0,str1);48             str3 = sum(str3,str2);49             str0 = str1;50             str1 = str2;51             str2 = str3;52         }53 54         cout << str3 << endl;55 56     }57 58     return 0;59 }

 

5.Reference:

Poj 3982 序列