hdu5686大数斐波那契

Problem Description

度熊面前有一个全是由1构成的字符串，被称为全1序列。你可以合并任意相邻的两个1，从而形成一个新的序列。对于给定的一个全1序列，请计算根据以上方法，可以构成多少种不同的序列。

Input

这里包括多组测试数据，每组测试数据包含一个正整数

Output

对于每组测试数据，输出一个整数，代表由题目中所给定的全1序列所能形成的新序列的数量。

Sample Input

1 3 5

Sample Output

1 3 8

Hint

如果序列是：(111)。可以构造出如下三个新序列：(111), (21), (12)。

Source

2016"百度之星" - 资格赛（Astar Round1）

看样例就知道是斐波那契数列，但是数据范围是1-200，早就超出long long 的范围，所以要用字符串模拟大数加法来写，应该只要过了hdu1002都能写出来。

代码:

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 string a[201];
 5 string add(string x,string y)
 6 {
 7     int n=x.length();
 8     int m=y.length();
 9     if(m>n)//为了方便，令y为短的那个数
10     {
11         swap(x,y);
12         swap(n,m);
13     }
14     string ans;
15     int t=0,c=0,d=n-1;
16     for(int i=m-1;i>=0;i--)//对齐最短的，从尾部相加
17     {
18         int s=x[d--]-'0'+y[i]-'0'+c,flag=0;//c用于进位，flag标记是否要进位
19         if(s>9)
20         {
21             s=s-10;
22             flag=1;//标记要进位
23         }
24         ans+=s+'0';//赋给新串
25         if(flag)//需要进位则下一位+1
26         c=1;
27         else
28         c=0;
29     }
30     for(int i=d;i>=0;i--)//将长的剩下的赋给新串
31     {
32         int s=x[i]+c-'0',flag=0;
33         if(s>9)
34         {
35             s=s-10;
36             flag=1;
37         }
38         ans+=s+'0';
39         if(flag)
40         c=1;
41         else
42         c=0;
43     }
44     if(c)//最后还剩一位没进
45     {
46         ans+=1+'0';
47     }
48     string f;
49     for(int i=ans.length()-1;i>=0;i--)//将字符串翻转
50     f+=ans[i];
51     return f;
52 }
53 int main()
54 {
55     a[0]="1";
56     a[1]="1";
57     for(int i=2;i<=200;i++)//打表
58     a[i]=add(a[i-1],a[i-2]);
59     int n;
60     while(cin>>n)
61     {
62         cout<<a[n]<<endl;
63     }
64     return 0;
65 }