摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 遞洄 數學 費氏數列

在此感謝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;
}