題目來源

UVA 00948

題意

1. 輸入一整數，要換成費式進位(等等說明)
2. 整數範圍100,000,000，因此當費式數列在第40項就已經足夠，因為 fib 40 = 102,334,155 已經超過

3. 費式進位法

   • 費式數列定義

   • 費式進位法跟其他進位法相似 1 代表存在該項，0代表沒有存在該項，以題目給的17做舉例 17 = 13 + 3 +1

     13	8	5	3	2	1	1
     1	0	0	1	0	1	0

   • 為了避免產生多解的情況 (eg. 17 = 8 + 5 + 3 + 1 (111010))，因此加了限制: 不得使用連續的項

思路

1. 前處理

   為了獲取費式數列以便處理，因此我們可以開一個fib[40]的陣列儲存 (開到40的原因是因為題目最多輸入範圍是100,000,000)，因此開到項數為39即可(前面fib[0]=0，不考慮)

   1
   2
   3
   4
    int fib[44]={0,1};
    for (int i=2;i<44;i++){
        fib[i]=fib[i-1]+fib[i-2];
    }
   

2. 輸入

   題目開頭會輸入n，代表輸入n組測資

   1
   2
   3
   4
   5
   6
    int n;
    cin>>n;
    while(n--){
        int num;
        cin>>num;
    }
   

3. 資料處理(轉成費式進位法)

   • 題目有說不得使用連續的項，因此我們要從後面(fib(39))開始，因為費式數列定義的關係(公視推導在最下面)
   • flag的用意是為了知道什麼時候開始才是我該輸出0，以免產生開頭為零的尷尬局面

   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
    int flag=0
    for (int i=43;i>1;i--){
      if (fib[i]<=num){
        flag=1;
        num-=fib[i];
        cout<<1;
      }
      else if (flag==1){
        cout<<0;
      }
    }
   

4. 輸出

   參照題目輸出要求我們的程式碼要改成

   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
    while(n--){
        int num,flag=0;
        cin>>num;
        cout<<num<<" = ";
        for (int i=43;i>1;i--){
            if (fib[i]<=num){
                flag=1;
                num-=fib[i];
                cout<<1;
              }
              else if (flag==1){
                cout<<0;
              }
         }
         cout<<" (fib)\n";
    }
   

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

using namespace std;
int main() {
  int fib[44]={0,1};
  for (int i=2;i<44;i++){
    fib[i]=fib[i-1]+fib[i-2];
  }
  int n;
  cin>>n;
  while(n--){
    int num,flag=0;
    cin>>num;
    cout<<num<<" = ";
    for (int i=43;i>1;i--){
      if (fib[i]<=num){
        flag=1;
        num-=fib[i];
        cout<<1;
      }
      else if (flag==1){
        cout<<0;
      }
    }
    cout<<" (fib)\n";
  }
}

附錄 - 從後面加的公式證明

共減 又 因此

從這邊我們可以知道如果從後面減絕對不會發生連續的問題，因為

• Previous
  Snakify
• Next
  [題解] UVA - 10041 - Vito's Family