回分類題庫
g019: F.費波那星
關鍵字: NPSC 2006 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 52 Times / 41 Users | Submit : 149 Times / 47 Users | Accepted rate : 87%
題目加入時間 : 2011-12-13 09:33

Content: 简体中文

星際旅行的普及化最大的影響其實不是旅行!就如同哥倫布發現新大陸後人們第一個想要做的事絕不是去美洲渡假一樣,殖民和貿易才是最優先想到的。既然商務交流這麼重要,當然得未雨綢繆、事先準備必要的工具囉。

會計制度、貨幣、語言、習俗等種種可能有不同(應該說完全不同)的制度、系統都在研究的範圍內。但是很少人會想到一個很基本的貿易問題:數字系統。雖然現在地球上用的都是十進制,但是瑪雅人當時用的卻是二十和六十進制的混合體,古埃及用的也不是十進制。如果瑪雅人活在現代,在交易時就要做適當的換算。幸好不同進制間的換算不算困難,就算是七進制、十五進制要和十進制互相換算都相當容易。

但是事情恐怕沒那麼簡單:為什麼數字系統一定是某種進制呢?那些夢想著星際貿易的人恐怕沒想到還有別的可能性,但是數學家——總是超前別人一百年的天才們——已經幫他們想好了。

這次的主角出現得更早:西元十二世紀出生的費波那契在一千年前找到的數列就是一種可能的數字系統!費波那契數列(費氏數列)長得像這樣: 1, 1, 2, 3, 5, 8, 13 …… 每一項是前兩項相加,因此 1 和 1 生出下一項 2,1 和 2 生出下一項 3。在表示一個數字的時候,從第二個 1 開始往後挑出一些數,使他們的和為要表示的數。例如想要表示 7 可以挑 2 和 5,想表示 19 則挑 1, 5 和 13。但是這樣表示法並不唯一: 19 也可以挑 1, 2, 3 和 13。因此還要加上一個限制:不能挑連續兩個數,因此 1, 2, 3, 13 是不合法的。如此一來可以保証每個數字都有唯一一種挑法,構成一種特別的數字系統——費波那契進制。

學家們已經用一連串的證明完成了理論,現在要請你幫忙實際寫一個計算機出來了。因為會計制度用了移項的技巧,從頭到尾只要用整數加法就可以了,因此你的計算機也需要兩的數的相加。

Input:

輸入檔中有許多組輸入,每組輸入占兩行,表示要相加的兩個數。兩個數字都大於零,讀到第一個數字為零表示檔案結束。費波那契進制表示成一連串的零和一。第一個數字表示費氏數列的第一項 1 有沒有被選中,一表示有、零表示沒有。第二個數則表示費氏數列的第二項,以此類推。輸入的每個數字最多一千位(一千個零或一),最後一個數字一定是一。

Output:

對每組輸入輸出一個費波那契進制的數,為輸入的兩個數的和。格式與輸入相同。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
0101
10101
0

Sample Output :

100101

Hint :

(0101)fib = 2 + 5 = 7,(10101)fib = 1 + 3 + 8 = 12,(100101)fib = 1 + 5 + 13 = 19。

Author :

NPSC 2006 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum