UVa 948 題解 — C++

此筆記為UVa 948的題目詳解，包含解題思路、C++範例程式碼。

Fibonaccimal Base (ZeroJudge a134.)

題目

有名的費氏數列是以 0 和 1 開始，然後把最後的兩個數字相加以得到下一項。例如數列的第三項為 1 (1=1+0)，第四項為 2 (2=1+1)，第五項為 3 (3=2+1)，等等。

i 0 1 2 3 4 5 6 7 8 9
Fib(i) 0 1 1 2 3 5 8 13 21 34

這個數列很重要且出現在我們生活及大自然的許多事物上。其中，你知道所有的正整數都可以用費氏數列中的不重覆的數字集合的和來代表嗎？例如：13 可以是集合 {13}, {5,8} 或{2,3,8} 的和，而 17 則可用 {1,3,13} 或 {1,3,5,8}來表示。即然每個數都有這個特性 (你要自己證證看嗎？) 這個數列可以用作表示數字的「底」。但如前所示，有些數字有多種表示法，這該怎麼辦呢？簡單，因為費氏數列中任兩個連續項的和就是下一項，所以只要加上一個限制：不得使用連續的項，那麼每個數字都有一個唯一的表示法。

有了這個認知後我們可以建立一個很酷的方式來表示任意正整數。我們一連串的 0 與 1來表示。例如：17 = 1 + 3 + 13 (記住不可以使用費氏數列中連續的項)，以 0 來表示沒有用到的項，以 1 來表示有用到的項，由右至左排列。因此 17 = 100101. 詳情參閱圖 2。在這個表示法中，最左邊的那一位數一定是 1，不可以是 0。根據我們的限制，這種表示法中不可以出現相鄰的 1。我們這種表示法為「費氏進位」並以下列方式表示 17 = 100101 (fib).

17 = 1 0 0 1 0 1
13+3+1 = 13 8 5 3 2 1

問題
給你一組十進位的數字，你的任務是將它們以費氏進位輸出。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

由於這題限制每一個輸入的正整數 a 必 < 100000000，因此只需要計算到費氏數列第 40 項（第41項為 102334155）。

從大到小找起，當 a - f[i] >= 0 且前項 = 0（題目規定不能使用連續的項）則使用該項數字，並修正

$a=a-f[i]$，直到 i = 2（i = 1、2 同為 1 且 i = 0 為 0，可忽略 i < 2 的兩項數字）即完成輸出。

範例程式碼

#include <iostream>
using namespace std;

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int n, s, a;
	int f[40]={0,1};
	
	for (i=2;i<40;i++)
		f[i] = f[i-1] + f[i-2];
	
	cin >> n;
		
	for (i=0;i<n;i++) {
		cin >> a;
		
		cout << a << " = ";
		
		int check = 0, base[41]={};
		
		for (j=39;j>=2;j--) {
			if (a - f[j] >= 0) {
				check = 1;
				
				if (base[j+1] != 1) {
					base[j] = 1;
					a = a - f[j];
				}
			}
			
			if (check == 1)
				cout << base[j];
		}
		
		cout << " (fib)" << endl;
	}

	return 0;
}

運行結果

AC (4ms, 328KB)

tags: CPE 1星

查看更多資訊請至：https://www.tseng-school.com/