这么一个简单的浮沉数列，就是写不出通项公式，盼高手

波浪

bardo 先生：
    据高管说，津乾论坛的恶意程序已经被清楚了。不知是否如此，请赐教。
     :em08:  :em09:  :em11:  :em12:

Bardo

太好了，回家看看

bardo

这个贴子很久了,至今未能得到答案.
问题进一步公布: 在我们所用的互联网通信中,发送数据是通过0与1来进行发送的,
但有时,我们需要知道,发送一个数,实际总需要以多少个1.
因为,0是用停顿来表示的, 所以, 所有的数都是二进制的.
但苦于没有计算公式, 只能用查表的方法加速度.
上面的数列,就是奇数数列的二进制位中有多少个1得出的结果数列.
假如有一简单算法, 使得速度加快,那么,现在的网络, 可以节省大约10%至30%效率.
当然,不要小看这一丁点的改进,这一改进对于很大的数据量收发,将会有很大的效果.
问题再简化写出来:
那就是,一个数转换成二进制以后, 写出来统计一下, 有几个1?
人工数数是可以的, 有没有公式呢?

康托尔对角线

研究这个有多大意义吗？

梅飞

我晚上失眠，花了几个小时帮楼主想出了通项公式： a(n) =1+ +p((p((4p(n/16)-3)/4)-1)/2)+ +p((4p(n/16)-4p((4p(n/16)-3)/4))/2)+ +p((p((n-16b(n/16))/4)-1)/2)+ +p((n+3-16b(n/16)-4p((n-16b(n/16))/4))/2) 其中，p(x)是向上取整函数，b(x)是向下取整函数，例p(1.25)=2，p(1.75)=2，p(1)=1，b(1.75)=1，b(1.25)=1，b(2)=2。 如果只考虑前16项，即n<=16时，那么，公式变简单： a(n)=1+p((p(n/4)-1)/2)+p((n+3-4p(n/4))/2)

梅飞

再查找了一下错误，该是： a(n) =1+ +p((p((4p(n/16)-3)/4)-1)/2)+ +p((4p(n/16)-4p((4p(n/16)-3)/4))/2)+ +p((p((n-16b((n-1)/16))/4)-1)/2)+ +p((n+3-16b((n-1)/16)-4p((n-16b((n-1)/16))/4))/2) 而n<=16时，公式依旧： a(n)=1+p((p(n/4)-1)/2)+p((n+3-4p(n/4))/2)

bardo

谢谢了,不过,好象算出结果还是不对

梅飞

哪里算的不对？举个例。

梅飞

[这个贴子最后由梅飞在 2009/10/04 02:40pm 第 2 次编辑] 可采用递推公式，能节省计算时间： 当n<=16， a(n)=1+p((p(n/4)-1)/2)+p((n+3-4p(n/4))/2)； 当n>16， a(n) =a(4p(n/16)-3)+ +p((p((n-16b(n/16))/4)-1)/2)+ +p((n-16b(n/16)+3-4p((n-16b(n/16))/4))/2)。

梅飞

还可以当n<=16时查表，而其它的时候只需对表格数据略作修改。