iT邦幫忙

2021 iThome 鐵人賽

DAY 11
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 11

Day 0xB UVa948 Fibonaccimal Base

題意

  • 輸入十進位的數字,輸出對應的費氏進位表示法
  • 需要注意的有:
    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;
    }
    

上一篇
Day 0xA UVa490 Rotating Sentences
下一篇
Day 0xC UVa10170 The Hotel with Infinite Rooms
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言