周末一题: "'酒筹'之后, 大家做做看"(续)

无疆行者

上周有一"周末一题: '酒筹'之后, 大家做做看", 里面说到"数学, 很美妙, 一首无声的诗歌".

有时一个看着简单的公式, 背后隐藏的竟然是如此美妙的韵律.

今年是2009年, 下面的一道题也涉及到2009, 不太难, 更直观, 感兴趣的做做看-但不要让2009误导啊:)

Let f: N->N be a function satisfiying the following for all positive integers n:

f(1) = 1
f(2n) = f(n)
f(2n+1) = f(2n) + 1

Find the maximum of f(n) when 1<=n<=2009

hanxin

上周有一"周末一题: '酒筹'之后, 大家做做看", 里面说到"数学, 很美妙, 一首无声的诗歌".

有时一个看着简单的公式, 背后隐藏的竟然是如此美妙的韵律.

今年是2009年, 下面的一道题也涉及到2009, 不太难, 更直观, 感 ...
无疆行者 发表于 2009-4-3 05:12 PM

f(1023) = 10

这次的规律比较好看出来。

炉匠

f(1023) = 10

这次的规律比较好看出来。
hanxin 发表于 2009-4-4 08:42 AM

真厉害。我是看了你的答案才明白。问一下我是否真明白，你是根据二－十进制的规律推的？

hanxin

真厉害。我是看了你的答案才明白。问一下我是否真明白，你是根据二－十进制的规律推的？
炉匠 发表于 2009-4-4 02:18 PM

谢谢炉匠夸奖。。。 test test

hanxin

test 成功啦。接这写。。。

我开始并没想到 2-10 进制。我是先把 function 换了一下：

f(n)  =  f(n/2)  if n is even
f(n)  =  f(n-1) + 1 if n is odd

从这里看出，只有在odd number才有可能升值。这样我就集中看 odd number 。

从最开始，

f(3) = 2, so f(6) = f(3) = 2, then we get f(7) = 3 (this is the first possible increase from 2)
then
f(7) = f(14) = 3， we get the next increase f(15) = 4, ... and so on
finally
f(1023) = 10

结论是，新的升值总是在 ((2^n) - 1)。 不知道说对了没有。

炉匠

test 成功啦。接这写。。。

我开始并没想到 2-10 进制。我是先把 function 换了一下：

f(n)  =  f(n/2)  if n is even
f(n)  =  f(n-1) + 1 if n is odd

从这里看出，只有在odd number才有可能升值。这样我就集中 ...
hanxin 发表于 2009-4-4 11:14 AM

还是你厉害。我是工科猪头，想着象逻辑电路十位寄存器。

hanxin

还是你厉害。我是工科猪头，想着象逻辑电路十位寄存器。
炉匠 发表于 2009-4-4 06:13 PM

嘻嘻，我也是工科猪头。

出题的老师还没来。也可能我答得不对呢。

无疆行者

f(1023) = 10

这次的规律比较好看出来。
hanxin 发表于 2009-4-4 08:42 AM

Bingo

无疆行者

还是你厉害。我是工科猪头，想着象逻辑电路十位寄存器。
炉匠 发表于 2009-4-4 02:13 PM

炉匠想的也不错啦: 基本上相当于一个Logical left shift one bit when even, and also inject 1 when odd. 结果是记其中二进制1的个数:)

无疆行者

这线可以close了, 关线...

Have a good weekend!

炉匠

我把题寄给一个小兄弟，他把公式稍微变了一下，得到全部解。1023,1535,1791,1919,1983。牛啊。

无疆行者

我把题寄给一个小兄弟，他把公式稍微变了一下，得到全部解。1023,1535,1791,1919,1983。牛啊。
炉匠 发表于 2009-4-7 01:49 AM

呵呵, 本来这题只要求"Find the maximum of f(n) ", 所以10就可以了:

1023,1535,1791,1919,1983在二进制下分别是:

011-1111-1111
101-1111-1111
110-1111-1111
111-0111-1111
111-1011-1111

它们的 f都是十进制的10, 即1的个数(n小于2048)-下面的移位还有几个超过了2009(本客故意设置的今年).

0011/1100, 看着跟平仄一样

hanxin

呵呵, 本来这题只要求"Find the maximum of f(n) ", 所以10就可以了:

1023,1535,1791,1919,1983在二进制下分别是:

011-1111-1111
101-1111-1111
110-1111-1111
111-0111-1111
111-1011-1111

它们的 f都是十进 ...
无疆行者 发表于 2009-4-7 06:52 AM

原来是这样！我笨，只看到一个解。

望关东老师，多多出题（容易的就行 ）。

无疆行者

13# hanxin

本来这题只要得出10就行了-但知道题后面的"物理意义"(呵呵, 权且用这个词儿), 也是本客的初衷.

这两个"周末一题"最后都能和001100挂上钩, 既是本客的偏爱, 也是对"平仄""方砖"的调侃
P.S., 本客把任何"老师"或"诗人"的说法视为冒犯