首页 > 代码库 > 1sting
1sting
///题解 ： 找规律，大菲波数
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
311111111
Sample Output
128
1 #include <stdio.h> 2 #include<iostream> 3 #include<cstring> 4 #define N 1001 5 using namespace std; 6 char a[N][N]; 7 int main() 8 { 9 memset(a,‘0‘,sizeof(a)); 10 a[1][0]=‘1‘;11 a[2][0]=‘2‘;12 int i,j,d=1;13 for(i=3;i<N;i++)//i控制行数 14 {15 d++; //控制列数 16 int c=0,s; //c为进位指数的初值 17 for(j=0;j<=d;j++) //j控制列数的循环18 {19 s=a[i-1][j]-‘0‘+a[i-2][j]-‘0‘+c;20 c=s/10; //满十进位21 a[i][j]=s%10+‘0‘; //满十的话，将舍位22 }23 24 }25 int t;26 char s[1000];27 scanf("%d",&t);28 while(t--)29 {30 scanf("%s",s);31 int n=strlen(s);32 int k=N-1;33 while(k--)34 {35 if(a[n][k]!=‘0‘) break; //反向搜索第一个不为‘0’的字符36 }37 for(i=k;i>=0;i--) //从后往前输出38 printf("%c",a[n][i]);39 printf("\n");40 }41 return 0;42 }
1sting
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。