• Virtual Judge
• ZeroJudge

題意

• 輸入十進位的數字，輸出對應的費氏進位表示法
• 需要注意的有：
  1. 第一行輸入一數字 N 代表測資數
  2. 每筆測資 ＜ 100000000
  3. 費氏進位表示法
     • 先知道什麼是費氏數列
     • 跟其他進位制的概念差不多，下排的右到左代表費氏數列第幾項，上排的 1 or 0 代表有無這項
       | |17 = | 1 | 0 | 0 | 1 | 0 | 1 |
       |:------------:|:---:|:---:|:---:|:---:|:---:|:---:|
       | 13 + 3 + 1 = | 13 | 8 | 5 | 3 | 2 | 1 |
     • 因為可能有多種可能，所以限定不能使用連續的項
       • e.g. 17 = 1 + 3 + 5 + 8 = 11101
  4. 輸出格式
     • DEC_BASE = FIB_BASE (fib)

解法

• 先用建表法存好費氏數列，因為測資的範圍，可以開 40 格就夠 (因為 [40] = 102334155 超過範圍)

  int Fibonacci[40] = {0, 1};
  int i;
  
  for(i = 2; i < 40; i++){
      Fibonacci[i] = Fibonacci[i - 1] + Fibonacci[i - 2];
  }
  

• 先讀一整數 N 再用 while 迴圈重複讀入測資並計算，因為我的 code 之後會動到輸入的測資，所以先把輸出格式印出來

  int N;
  
  scanf("%d", &N);
  
  while(N--){
  
      int num;
  
      scanf("%d", &num);
      printf("%d = ", num);
      ...
  }
  

• 因為有不能連續項的限制，所以從後面的項開始找，至於為什麼就留給大家思考囉～一樣可以代數字進去想想，可以思考一下費氏數列的特性；用 flag 布林變數的小技巧來控制遇到有 1 才開始輸出

  bool flag = false;
  
  for(i = 39; i >= 2; i--){
      if(num >= Fibonacci[i]){
          num = num - Fibonacci[i];
          flag = true;
          printf("1");
      }
      else if(flag){
          printf("0");
      }
  }
  
  printf(" (fib)\n");
  

• C code

  #include<stdio.h>
  #include<stdbool.h>
  
  int main(){
  
      int N;
      int Fibonacci[40] = {0, 1};
      int i;
  
      for(i = 2; i < 40; i++){
          Fibonacci[i] = Fibonacci[i - 1] + Fibonacci[i - 2];
      }
  
      scanf("%d", &N);
  
      while(N--){
  
          int num;
          bool flag = false;
  
          scanf("%d", &num);
          printf("%d = ", num);
  
          for(i = 39; i >= 2; i--){
              if(num >= Fibonacci[i]){
                  num = num - Fibonacci[i];
                  flag = true;
                  printf("1");
              }
              else if(flag){
                  printf("0");
              }
          }
  
          printf(" (fib)\n");
      }
  
      return 0;
  }