#35819: 不遞迴解(cpp/py)
kerochen391@gmail.com
(KeroChen)
學校
:
高雄市立高雄高級中學
編號 : 216669
來源 : [114.35.195.36]
最後登入時間 ：
2024-11-20 20:44:29
e357. 遞迴函數練習
| From: [59.127.54.216] |
發表日期
:
2023-06-18 15:50
以2進位運算
x是偶數時f(x) = f(x/2)
相當於可以把結尾的0都刪掉
如果忽略掉後方的0會發現奇數時x+1跟x-1中必有一者的位數只比x少一位
另一個會跟之前重複
如下(省略結尾0)
把增加的位數整理可以得到
| 1 | 11 | 101 | 1001 | 10011 |
| 1 | 1 | 1 | 1 | 3 |
換個更大的數字、只看當前位數、將上下兩排錯位
| x | (1) | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | (1) | |
| Δf(x) | 1 | 1 | 1 | 2 | 2 | 5 | 7 | 12 | 12 | 12 | 43 |
f(0d11001011101) = 1+1+1+2+2+5+7+12+12+12+43 = 98
首尾兩位一定是1且可以忽略
發現x不變，Δf(x)也不變；
否則Δf(x)是除了上一位外先前所有Δf(x)總和
另外，在二進位下將數字倒過來(1001101->1011001)對f(x)沒有影響
-----------------------------------------------------------------------------------------------------
https://drive.google.com/drive/folders/1lP26fHG4XY2ja_sNr8UXdPhJp1mj5n6Z?usp=sharing
*限制存取權
#35862: Re: 不遞迴解(cpp/py)
kerochen391@gmail.com
(KeroChen)
學校
:
高雄市立高雄高級中學
編號 : 216669
來源 : [114.35.195.36]
最後登入時間 ：
2024-11-20 20:44:29
e357. 遞迴函數練習
| From: [223.138.83.135] |
發表日期
:
2023-06-20 08:57
會重複的原因:
100...001 = 101 -> 100
011...111 = 011 -> 100
因此少不只一位的情況下，Δf(x)跟中間的1/0數量無關
並且只有一位時，Δf(x)會等於前兩位的f(x)
ZeroJudge Forum