|
PCDVD數位科技討論區
(https://www.pcdvd.com.tw/index.php)
- 七嘴八舌異言堂
(https://www.pcdvd.com.tw/forumdisplay.php?f=12)
- - Problem of the Week (請大家來解答)
(https://www.pcdvd.com.tw/showthread.php?t=898360)
|
|---|
Problem of the Week (請大家來解答)
Suppose f is a fuction from positive integers to positive integers satisfying f(1)=1, f(2n)=f(n), and f(2n+1)=f(2n)+1, for all positive integers n.
Find the maximum of f(n) when n is greater than or equal to 1 and less than or equal to 1994. 這是印在HP印表紙的包裝袋上的問題 答案是多少??? |
由 f(1)=1, f(2n)=f(n), and f(2n+1)=f(2n)+1 可以知道
把所有的正整數除了1以外,都分為兩類 一種是 2 的倍數,如2,4,6,8,10,12,.... 一種是 2 的倍數+1,如3,5,7,9,11,13... 第一種代入函數會得到1,1.1.1.1.1... 第二種f(2n+1) = f(2n)+1 = f(n)+1,因此會得到2,2,2,2,2,2,2... 由此可知,這是一種合成函數迴圈 用Excel跑了一下最大值 1993 997 499 250 125 63 32 16 8 4 2 1 1994 997 499 250 125 63 32 16 8 4 2 1 最大值應該都是1 這函數不論多大的整數丟進去,都會透過有限次數的迴圈退化到1 9999999 5000000 2500000 1250000 625000 312500 156250 78125 39063 19532 9766 4883 2442 1221 611 306 153 77 39 20 10 5 3 2 1 還是會收斂到1 小小意見XD 錯了還請指教 |
引用:
f(1)=1 f(2)=f(2*1)=f(1)=1 f(3)=f(2*1+1)+1=f(2)+1=2 f(4)=f(2*2)=f(2)=1 f(5)=f(2*2+1)+1=f(2)+1=2 f(6)=f(2*3)=f(1)=2 f(7)=f(2*3+1)+1=f(3)+1=3 ...... 所以應該是遞增函數，f(1994)應該是最大值 改寫成 f(2n)=f(n) f(2n+1)=f(n)+1 f(1994)=f(2*997)= f(2*498+1)=f(498)+1= f(249)+1=f(2*124+1)+1= f(124)+1=f(124)+1+1 f(31)+2=f(15)+3= f(7)+4= f(3)+5 可看出規則如下 if n/2=0 then f(n)=f(n/2) if n/2=1 then f(n)=f(n/2)+1 沒算錯的話答案應該是7 |
上面寫太亂了，時間到來不及改
f(2n)=f(n) f(2n+1)=f(n)+1 令2n=x f(x)=f(x/2) f(x+1)=f(x/2)+1 |
試著觀察這題目，可以發現f(n)就是在計算n用二進位表示時，數位中所有1的總和。
所以我們要算的是，小於或等於1994的數當中，用二進位表示後，哪個數有最多1，這數的1有多少個。1023的二進位有10個1，所以10就是答案(因為二進位的11111111111已經大於1994，所以最多有10個1)。 |
我比較沒有那個耐性……
代碼:
f = zeros(1,1994); f(1) = 1; for n = 2 : 1994 x = n; if rem(x,2) == 0 x = x / 2; f(n) = f(x); else x = x-1; f(n) = f(x)+1; end end max(f) 答案是10，不愧是專業的五樓 :D :D :D |
受教了Orz1
雖然還是沒能一眼看出其與二進位之間的關係~ |
假如沒講真的看不出來有這個關係:ase
我也來出個問題： HP印表紙出這題目要幹嘛? Orz :jolin: |
引用:
我的問題也是這個丫.. :think: |
| 所有的時間均為GMT +8。 現在的時間是04:24 PM. |
vBulletin Version 3.0.1
powered_by_vbulletin 2025。