怎样理解ugly number II - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

怎样理解ugly number II

怎样理解ugly number II# JobHunting - 待字闺中

u*22017-09-04 07:09

1 楼

这是我看到的解释：
----------------------------------------
我们知道丑陋数序列可以拆分为下面3个子列表：
(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …
仔细观察上述三个列表，我们可以发现每个子列表都是一个丑陋数分别乘以2,3,5，而
要求的丑陋数就是从已经生成的序列中取出来的，我们每次都从三个列表中取出当前最
小的那个加入序列，
----------------------------------------
第1个序列都是从1到n 乘 2
第2个序列都是从1到n 乘 3
第3个序列都是从1到n 乘 5
但问题是，这并不对，如果这样：
(1) 1×2, 2×2, 3×2, 4×2, 5×2, 6x2, 7x2 …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, 6x3, 7x3…
(3) 1×5, 2×5, 3×5, 4×5, 5×5, 6x5, 7x5…
7x2,7x3,7x5肯定不是ugly number了吧。

a*a2017-09-04 07:09

2 楼

”而要求的丑陋数就是从已经生成的序列中取出来的“，那个7不在已经生成的序列里
面。
比如已经生成的序列是a=[1]
然后用三个数字代表2、3、5的index，那么p2 = 0, p3 = 0, p5 = 0;
然后算出来min(a[p2]*2, a[p3] * 3, a[p5] * 5),就是选出来的下一个数字，这个地
方是2，
a = [1,2], p2 = 1, p3 = 0, p5 = 0
a = [1,2,3], p2 = 1, p3 = 1, p5 = 0
a = [1,2,3,4], p2 = 2, p3 = 1, p5 = 0
a = [1,2,3,4,5], p2 = 2, p3 = 1, p5 = 1 // a[p2] * 2 == a[p3] * 3
a = [1,2,3,4,5,6], p2 = 3, p3 = 2, p5 = 1
a = [1,2,3,4,5,6,8], p2 = 4, p3 = 2, p5 = 1

z*n2017-09-04 07:09

3 楼

这3个表自己总结的还是有人教你的？有人教的话可以找他退款了。
你的从已经生成的序列里挑数网上放，不是1,2,3,4。。。7

【在 u*******2 的大作中提到】

: 这是我看到的解释：
: ----------------------------------------
: 我们知道丑陋数序列可以拆分为下面3个子列表：
: (1) 1×2, 2×2, 3×2, 4×2, 5×2, …
: (2) 1×3, 2×3, 3×3, 4×3, 5×3, …
: (3) 1×5, 2×5, 3×5, 4×5, 5×5, …
: 仔细观察上述三个列表，我们可以发现每个子列表都是一个丑陋数分别乘以2,3,5，而
: 要求的丑陋数就是从已经生成的序列中取出来的，我们每次都从三个列表中取出当前最
: 小的那个加入序列，
: ----------------------------------------

u*u2017-09-04 07:09

4 楼

我网上给你找了个我看得懂的
construct next number using 2,3,5
从1 开始,下一个数可能是1x2, 1x3, 1x5然后我们确定 1x2最小，为下一个数。然后
从1,2开始，下一个数可能是现有的数乘以2,3,5, 所以candidates: 1x2, 2x2,
1x3,2x3, 1x5, 2x5 但是1x2已经用过了，所以是1x3
然后
从1,2,3开始candidates:1x2,2x2,3x2, 1x3,2x3,3x3, 1x5,2x5,3x5但是我们发现1x2,
1x3又用过了所以的有变量记录用过的数
for 2: 1x2,
for 3: 1x3,
都乘以过了第一个数, 所以 i2++， i3++ 下次要乘以第二个数。。。。。

j*g2017-09-04 07:09

5 楼

简答如下
递归时，已知[1,2,3,4,...Xn_1,] 求Xn
下个数一定是已知[1,2,3,4,...N-1,]中某个数 * 2/3/5中一个
而这个被乘数一定是最近一次被 2/3/5 乘的数递归后的下个数，否则可以证反
所以保持
a. 递归得到的[1,2,3,4,5,...]数列
b. 最近一次被 2/3/5 乘的数的序号
以便加速获得递归得到的[1,2,3,4,5,...Xn_1]数列下个数Xn