Fibnacci string 
Problem description
The Fibnacci string is as follows:
S1=b
S2=a
Sk=Sk-1Sk-2 k>2
We are given a string, is there a Fibnacci string?

Input
The input will consist of a series of string, one string per line, followed by a line containing only the char ‘0’ that signals the end of the input file and need not to be processed.
You may assume that the length of each string is no more than 1,000,000.

Output
For each string you should output the ‘true’ if the string is a Fibnacci string, or ‘false’ if the string is not a Fibnacci string and with one line of output for each line in input.
 
Sample Input
abaab
abaababa
abaababaababa
0

Sample Output
true
true
false
 
//友情提示，请注意 a, b my code as followed :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char gstr[1000010],str[1000010];
int  gm[34];
void Init(){
 int t,i,j;
 for(i=2,gm[0]=gm[1]=1; gm[i-1]<1000000;i++)
  gm[i]=gm[i-1]+gm[i-2];
 for(gstr[0]='a',gstr[1]='b',t=2,i=2; i<1000000; t++)
  for(j=0; j<gm[t-1] && i<1000000;j++,i++)
   gstr[i]=gstr[j];
}
int myCmp(const int *a,const int *b){
 if(*a > *b)
  return 1;
 else if(*a < *b)
  return -1;
 return 0;
}
int main(){
 int  *p,a;
 char c;
 Init();
 while(1){
  scanf("%s",str);
  if(!strcmp(str,"0"))
   break;
  a=strlen(str);
  if(a==1){
   if(str[0]=='b' || str[0]=='a')
    printf("true\n");
   else
    printf("false\n");
   continue;
  }
  p=bsearch(&a,gm,30,sizeof(int),myCmp);
  if(!p){
   printf("false\n");
   continue;
  }
  c=gstr[*p];
  gstr[*p]='\0';
  if(!strcmp(str,gstr))
   printf("true\n");
  else
   printf("false\n");
  gstr[*p]=c;
 }
 return 0;
}

评论