回分類題庫
h024: D.分「樹」
關鍵字: NPSC 2006 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 27 Times / 25 Users | Submit : 34 Times / 27 Users | Accepted rate : 93%
題目加入時間 : 2011-11-10 10:34

Content: 简体中文

十九世紀的時候,Moriz Stern (1858) 與 Achille Brocot (1860) 發明了「一棵樹」。據說,經由一些簡單的規則而產生的這一棵樹上,可以包含零以上所有的有理數。這棵樹看起來大致像這樣:

你觀察出規則了嗎?

首先,他們在第一列放兩個「分數」(也許有些人會認為有的不能算是分數,但我們在這裡先把它們當作是分數來看待),第一個是 0/1,代表 0;第二個是 1/0,代表無窮大。接著他們一列一列地產生這棵樹,當他們要產生第 k+1 列的時候,就先把前 k 列所有的分數按照大小排成一列(假設有 n 個),在這些數之間會有 n-1 個間隔,那麼第 k+1 列就準備產生 n-1 個數,其值的分子恰好是左右兩個數的分子的和、分母是左右兩個數的分母的和。

例如,第四列的第二個分數是2/3,而它的2就是左邊1/2的1和右邊1/1的分子1相加的結果;而2/3的3,則是1/2的2加上1/1的分母1而得。

隨便跟你說我要某列的某個數,你能不能算出來呢?

Input:

輸入檔中有許多組輸入,每組輸入佔一行,包含了兩個用空白隔開的整數,依序代表要求的那個數所在的列號與它是在該列的第幾個(列號與第幾個都是從 1 開始數的)。你可以假設列號不會超過 30。最後以兩個零“0 0”為檔案結束,不須處理這組輸入。

Output:

對每一組輸入輸出一行,其中包含所要求的那個數。格式是分子、斜線、分母,中間不要有空白。

Sample Input:help

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

Sample Output :

1/3
2/3
3/2
3/1

Hint :

Author :

NPSC 2006 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum