PCDVD數位科技討論區 - 瀏覽單個文章 - 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(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