【杭电-oj】-1865-1sting（大数斐波那契数列）

发布时间：2021-01-24 03:33 所属栏目：[大数据] 来源：网络整理

导读：1sting Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5021????Accepted Submission(s): 1864 Problem Description You will be given a string which only contains ‘1’; You can merge

1sting

Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5021????Accepted Submission(s): 1864

Problem Description You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’,or leave the ‘1’ there. Surly,you may get many different results. For example,given 1111,you can get 1111,121,112,211,22. Now,your work is to find the total number of result you can get.
?
Input The first line is a number n refers to the number of test cases. Then n lines follows,each line has a string made up of ‘1’ . The maximum length of the sequence is 200.
?
Output The output contain n lines,each line output the number of result you can get .
?
Sample Input

?
Sample Output

?
Author z.jt ?
这道题也是斐波那契数列，只是需要用字符串把1的个数转换为n而已。

#include<cstdio>
#include<cstring>
int main()
{
	int t,l,k;
	char a[201];
	int f[1001][211]={0};			//全部初始化为0 
	f[1][1]=1;
	f[2][1]=2;
	for(int i=3;i<=1000;i++)
	{
		for(int j=1;j<=210;j++)			//二维数组，i表示第几个数，j表示这个数的第几位，
		{								// 然后对j进行类似大数相加的运算 
			f[i][j]+=f[i-1][j]+f[i-2][j];
			if(f[i][j]>9)
			{
				f[i][j]-=10;
				f[i][j+1]++;	
			}	
		}	
	}	
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",a);
		l=strlen(a);
		k=100;
		for( ;f[l][k]==0;k--);			//开始全部初始化为零，直到遇到一个f[n][k]!=0,此时跳出循环，开始输出 
		for( ;k>=1;k--)					//这种倒着输出不同于之前的倒着输出，此时不用考虑是否进位，只要不超出范围即可 
			printf("%d",f[l][k]);
		printf("\n");
	}
	return 0;
}

【免责声明】本站内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。