斐波那契字符串

斐波那契字符串

时间限制: 1 Sec   内存限制: 128 MB 提交: 21   解决: 6 [ 提交][ 状态][ 讨论版]

题目描述

相信大家对斐波那契数列都非常熟悉，现在我们对斐波那契数列做一个变形，我们定义：str[n] = str[n-1] + str[n-2](n > 1)。例如：如果str[0] = "ab"; str[1] = "bc";那么得到的结果是str[2]="abbc", str[3]="bcabbc" , str[4]="abbcbcabbc" …………;

输入

多组测试数据，每组测试数据包括两个字符串和一个整数K(0<=K<=50)，字符串都是小写，且长度小于30。

输出

对于每一个测试数据，要求你求出第K个斐波那契数列字符串的字母的个数。

样例输入

ab bc 3

样例输出

a:1 b:3 c:2 d:0 e:0 f:0 g:0 h:0 i:0 j:0 k:0 l:0 m:0 n:0 o:0 p:0 q:0 r:0 s:0 t:0 u:0 v:0 w:0 x:0 y:0 z:0

抽象出来一个模型就是斐波那契数列，可以先把字符串的斐波那契转化为数字型的，因为把字符串累加到最后内存超限，数字还会更节省空间。数字类型要用double或long long int类型的不然也会超限。

#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int main() { char str[30],str1[30]; int k,i,j; double a[26],b[26],t; while(cin>>str>>str1>>k) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); int len,len1; len=strlen(str); len1=strlen(str1); for(i=0;i<len;i++) a[str[i]-'a']++;//把字母个数存在整型数组里，转化为斐波那契数列 for(i=0;i<len1;i++) b[str1[i]-'a']++;//同理 for(i=2;i<=k;i++)//第i个斐波那契数列字符串 for(j=0;j<26;j++)//26个字母 { t=a[j]+b[j]; a[j]=b[j]; b[j]=t; } for(i=0;i<26;i++) printf("%c:%.0lf\n",'a'+i,b[i]); } return 0; }