作法 : 遞洄 數學 費氏數列

在此感謝BLEED大 無私的分享
0
1
0+1=01
1+01=101
01+101=01101
...類推
用回朔的方式去找

當我們要找某個位置的時候  回朔回去找來源

/**********************************************************/

#include<stdlib.h>
#include<stdio.h>
unsigned long long F[101];
void back (int N,int M)
{
   if(N==1) printf("0\n");
   else if(N==2)printf("1\n");
   else
       {
          if(M>F[N-2]) back(N-1,M-F[N-2]); 
          else back(N-2,M);
       }
}
main()
{
 
  int a,b,N,M,t;
  F[1]=1,F[2]=1;
  for(a=3;a<100;a++)
     F[a]=F[a-1]+F[a-2];
   while(scanf("%d",&t)==1)
       while(t--)
           {
              scanf("%d %d",&N,&M);
              for(a=1;a<100;a++)
                 if(M<=F[a]) break;
              if(a>N) {printf("-1\n");continue;}
              else
                 back(N,M);
           }
   return 0;
}