|
||
|
*停權中*
加入日期: Aug 2006
文章: 347
|
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印表紙的包裝袋上的問題 答案是多少??? |
|||||||
2010-06-28, 07:30 PM
#1
|
|
|
Major Member
 加入日期: Aug 2006
文章: 207
|
由 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 錯了還請指教 此文章於 2010-06-28 08:45 PM 被 =TIM= 編輯. |
||
|
2010-06-28, 08:41 PM
#2
|
|
|
Basic Member
加入日期: Jun 2008
文章: 29
|
引用:
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 此文章於 2010-06-28 09:23 PM 被 gsmspro 編輯. |
|
|
2010-06-28, 09:14 PM
#3
|
|
|
Basic Member
加入日期: Jun 2008
文章: 29
|
上面寫太亂了，時間到來不及改
f(2n)=f(n) f(2n+1)=f(n)+1 令2n=x f(x)=f(x/2) f(x+1)=f(x/2)+1 |
|
2010-06-28, 09:37 PM
#4
|
|
|
Regular Member
 加入日期: Dec 2006
文章: 50
|
試著觀察這題目，可以發現f(n)就是在計算n用二進位表示時，數位中所有1的總和。
所以我們要算的是，小於或等於1994的數當中，用二進位表示後，哪個數有最多1，這數的1有多少個。1023的二進位有10個1，所以10就是答案(因為二進位的11111111111已經大於1994，所以最多有10個1)。 此文章於 2010-06-28 09:45 PM 被 meagal2006 編輯. |
|
2010-06-28, 09:43 PM
#5
|
|
|
Advance Member
  加入日期: Mar 2010 您的住址: 三界火宅
文章: 396
|
我比較沒有那個耐性……
代碼:
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，不愧是專業的五樓  |
|
2010-06-29, 12:01 AM
#6
|
|
|
Major Member
加入日期: Aug 2006
文章: 207
|
受教了Orz1
雖然還是沒能一眼看出其與二進位之間的關係~ |
|
2010-06-29, 12:26 AM
#7
|
|
|
Basic Member
加入日期: Jun 2008
文章: 29
|
假如沒講真的看不出來有這個關係
 我也來出個問題： HP印表紙出這題目要幹嘛? Orz  |
|
2010-06-29, 02:00 AM
#8
|
|
|
Major Member
加入日期: Jan 2002 您的住址: 台北新莊
文章: 226
|
引用:
我的問題也是這個丫.. 
__________________
我曾經有過那麼一張沙發，  但是那時候我的腿一點也不酸， 所以我走了。 等我腿酸時，再回頭，  那張沙發已經被別人搬走了............    ∼德國詩人 呂克特 |
|
|
2010-06-29, 06:38 AM
#9
|
|
