Day 0xB UVa948 Fibonaccimal Base

• 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;
  }