gxqcn 发表于 2010-3-9 11:27:11

一个特殊反序数列的实现

给定一个正整数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 发表于 2010-3-9 14:11:45

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

northwolves 发表于 2010-3-9 14:13:36

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

gxqcn 发表于 2010-3-9 14:24:57

3# northwolves

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

〇〇 发表于 2010-3-9 16:09:54

3# northwolves

可是7的二进制仍为3位啊，怎么得到下一个后续数13的呢？
gxqcn 发表于 2010-3-9 14:24 http://bbs.emath.ac.cn/images/common/back.gif
这种算法没有意义
就像以前用异或代替temp交换变量

qianyb 发表于 2010-3-9 16:17:46

3# northwolves

可是7的二进制仍为3位啊，怎么得到下一个后续数13的呢？
gxqcn 发表于 2010-3-9 14:24 http://bbs.emath.ac.cn/images/common/back.gif
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 发表于 2010-3-9 16:21:01

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

liangbch 发表于 2010-3-9 16:22:30

(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 发表于 2010-3-9 16:36:09

8# liangbch

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

gxqcn 发表于 2010-3-9 16:58:58

6# qianyb

估计 northwolves 的本意也是这样的吧。
这倒也是一种比较好的方法。
页: [1] 2
查看完整版本: 一个特殊反序数列的实现