一个特殊反序数列的实现

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$)  <n )
     $v_i$++;

gxqcn

8# liangbch

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

gxqcn

6# qianyb

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