怎样理解ugly number II# JobHunting - 待字闺中
u*2
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了吧。
----------------------------------------
我们知道丑陋数序列可以拆分为下面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了吧。