一个特殊反序数列的实现

gxqcn

给定一个正整数$n$，令$v=n$，进行如下步骤： 1、若$v$为偶数，则$v=v/2$； 2、若$v$为奇数，则$v=(v+1)/2$； 经过有限次上述步骤（即$v=|__(v+1)/2__|$），该$v$逐渐减小，直到等于$1$时停止操作。 比如：如果$n=100$，则$v$依次可取到：100、50、25、13、7、4、2、1 反向后的序列为：1→2→4→7→13→25→50→100 现在的问题是：不用数组记录，如何巧妙得到上述反向序列？ 比如说上面的例子，已知$n=100$，在得到$v=4$时，如何直接确定出其后续数是$v=7$，然后是$13$、$25$、。。。 最好是通过简单的二进制运算实现。

northwolves

$v="ceiling"(n/2^(("int"(log(n,2))-"int"(log(v,2)))))$

northwolves

n=100 二进制7位 v=4 二进制3位 v=n/2^(7-3)=6.25 向上取整7

gxqcn

3# northwolves 可是7的二进制仍为3位啊，怎么得到下一个后续数13的呢？

〇〇

3# northwolves 可是7的二进制仍为3位啊，怎么得到下一个后续数13的呢？ gxqcn 发表于 2010-3-9 14:24

这种算法没有意义 就像以前用异或代替temp交换变量

qianyb

3# northwolves 可是7的二进制仍为3位啊，怎么得到下一个后续数13的呢？ gxqcn 发表于 2010-3-9 14:24

northwolves 的意思是 100/2^6=1.5=2 100/2^5=3.1=4 100/2^4=6.2=7 100/2^3=12.5=13 100/2^2=25 100/2^1=50

qianyb

如果是129,northwolves 的公式能算出来吗

liangbch

(1 << 7)=128 >=100 (2 << 6)=128 >=100 (4 << 5)=128 >=100 (7 << 4)=112 >=100 (13 << 3)=108 >=100 (25 << 2)=100 >=100 (50 << 1)=100 >=100 (100 << 0)=100 >=100 已知 n，例子中n=100 初始值： e= log2(n) 向上取整， $v_0=1$ 迭代 e--; $V_{i} = V_{i-1} ** 2 - 1$ if ( ($v_i < < e$)

gxqcn

8# liangbch 这个算法很好，估计就是问题的解决思路了。

gxqcn

6# qianyb 估计 northwolves 的本意也是这样的吧。 这倒也是一种比较好的方法。