這一題要先拿出紙筆,研究一下f(x)的規律,找到規律後,其實不難。
找到這個規律之後,就可以開始逆向拆解了。
我先創造一個列表reverse_steps=[]
,記錄拆解的步驟。
創造一個while True:
循環。
reverse_steps=[]
裡面insert(0,"/2")
。reverse_steps=[]
裡面insert(0,"-1")
。接下來,會得到一個列表,類似這樣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)
|