#51425: Python解題思路


abc1231334 (tl32m)

學校 : 長庚大學
編號 : 314314
來源 : [118.170.35.103]
最後登入時間 :
2025-08-19 00:53:50

這一題要先拿出紙筆,研究一下f(x)的規律,找到規律後,其實不難。

  1. 當a > b,也就是f(x) > 1 的時候,x是偶數。
  2. 當a < b,也就是f(x) < 1 的時候,x是奇數。
  3. 當a = b,有就是f(x) = 1,此時x = 1。

找到這個規律之後,就可以開始逆向拆解了。
我先創造一個列表reverse_steps=[],記錄拆解的步驟。
創造一個while True:循環。

  1. 假設f(x)>1時,f(x) -1 = f(x/2)。把分子減去分母,也就是分數減一,然後再reverse_steps=[]裡面insert(0,"/2")
  2. 假設f(x)<1時,1/f(x) = f(x-1)。把分子分母交換,然後再reverse_steps=[]裡面insert(0,"-1")
  3. 假設a = b,break。

接下來,會得到一個列表,類似這樣reverse_steps=['/2', '-1', '/2', '-1', '/2', '/2', '-1', '/2', '-1', '/2', '/2']
從右到左,就是拆解x的過程。所以要找到x,就從左到右操作,初始值是a = 1,遇到"/2",就*= 2,遇到"-1",就+= 1
算出來就是答案囉,上面那個list,算出來就是236,也就是f(236) = 30/11。

完整程式碼。

from sys import stdin

lines = stdin.readlines()

for line in lines:
    frac = list(map(int,line.split())) # frac[0]是分子,frac[1]是分母
    reverse_steps = [] #紀錄拆解的步驟


    while True:
        if frac[0] > frac[1]: # f(x) > 0,表示x是偶數
            frac[0] -= frac[1] # f(x) - 1 = f(x/2)
            reverse_steps.insert(0,"/2")
        elif frac[0] < frac[1]: # f(x) < 0,表示x是奇數
            frac.reverse() # 1/f(x) = f(x-1)
            reverse_steps.insert(0,"-1")
        else: # 分母分子相等,表示x=1。f(1) = 1。
            break

    ans = 1
    for i in reverse_steps:
        if i=="/2":
            ans *= 2
        else:
            ans += 1

    print(ans)