相关疑难解决方法(0)

我的一个朋友正在面试一份工作.其中一个面试问题让我思考,只想得到一些反馈.

有2个非负整数:i和j.给定以下等式,找到(最优)解决方案以对输出进行排序的方式迭代i和j.

2^i * 5^j

所以前几轮看起来像这样:

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25

尽我所能,我看不到一个模式.你的意见？

只有素数因子为2,3或5的数字称为丑陋数字.

例:

1,2,3,4,5,6,8,9,10,12,15 ......

1可以被认为是2 ^ 0.

我正在努力寻找第n个难看的数字.请注意,当n变大时,这些数字非常稀疏地分布.

我写了一个简单的程序来计算给定数字是否丑陋.对于n> 500 - 它变得超级慢.我尝试使用memoization - 观察:ugly_number*2,ugly_number*3,ugly_number*5都很难看.即便如此,它也很慢.我尝试使用log的一些属性 - 因为这会将这个问题从乘法减少到另外 - 但是,运气不大.想与大家分享这个.任何有趣的想法？

使用类似于"Eratosthenes的筛子"的概念(感谢Anon)

    for (int i(2), uglyCount(0); ; i++) {
            if (i % 2 == 0)
                    continue;
            if (i % 3 == 0)
                    continue;
            if (i % 5 == 0)
                    continue;
            uglyCount++;
            if (uglyCount == n - 1)
                    break;
    }

我是第n个难看的数字.

即便这样也很慢.我想找到第1500个难看的数字.

在表达中

2 ^x*3 ^y*5 ^z

的x,y并且z可以采取非负整数值(> = 0).

因此该函数将生成一系列数字 1,2,3,4,5,6,8,9,10,12,15,16....

• 我有一个强力解决方案.
• 我基本上会在从1开始的循环中迭代,并且在每次迭代中我会发现当前的数字因子是否仅来自2,3或5的集合.

我想要的是一个优雅的算法.

这是一个面试问题.

可能的重复:
第n个丑陋的数字
找到表达式的第K个最小数(2 ^ x)*(3 ^ y)*(5 ^ z)

我想知道如何以快速和优雅的方式解决这个问题:

我们定义"丑陋"的每个数字n可以用以下形式写出:2 ^ x*3 ^ y*5 ^ z ;,其中x,y和z是自然数.找到第1500个丑陋的数字.

例如,第一个"丑陋"的数字是:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

我试图用暴力解决这个问题,这样:

import itertools as it

def is_ugly(n):
    '''Return `True` if *n* is an ugly number.'''

    if n == 1:
        return True
    while not n % 2:
        n //= 2
    while not n % 3:
        n //= 3
    while not n % 5:
        n //= 5
    return n …

是否有一种有效的算法来按升序排列数n的因子而不进行排序？"有效"我的意思是:

1. 该算法通过从n的素数幂分解开始,避免了对除数的强力搜索.

2. 算法的运行时复杂度为O(d log 2 d)或更好,其中d是n的除数.

3. 算法的空间复杂度为O(d).

4. 该算法避免了排序操作.也就是说,这些因素是按顺序生成的,而不是按顺序生成并随后排序.尽管使用简单的递归方法进行枚举然后排序是O(d log 2 d),但是对于排序中涉及的所有存储器访问来说,存在非常难看的成本.

一个简单的例子是n = 360 =2³×3²×5,其中d = 24个因子:{1,2,3,4,5,6,8,9,10,12,15,18,20,24, 30,36,40,45,60,72,90,120,180,360}.

一个更严重的例子是n = 278282512406132373381723386382308832000 =2⁸×3⁴×5³×7²×11²×13²×17×19×23×29×31×37×41×43×47×53×59×61×67×71×73 ×79,其中d = 318504960因子(显然这里列出太多了!).顺便提一下,这个数字具有最大数量的因子,最多可达2 ^ 128.

我可以发誓几周前我看到了这种算法的描述,带有示例代码,但现在我似乎无法在任何地方找到它.它使用了一些魔术技巧,在每个素数因子的输出列表中维护一个祖先索引列表.(更新:我使用汉明数字混淆因子生成,其运算方式类似.)

更新

我最终在运行时使用O(d)的解决方案,具有极低的内存开销,可以就地创建O(d)输出,并且比我所知的任何其他方法都要快得多.我已经发布了这个解决方案作为答案,使用C源代码.它是另一个贡献者Will Ness在Haskell中提供的一个优化算法的优化简化版本.我选择了Will的答案作为公认的答案,因为它提供了一个非常优雅的解决方案,符合最初规定的所有要求.

常数是均匀分配60的幂的数字.例如,60 ² = 3600 = 48×75,因此48和75都是60的幂的除数.因此,它们也是常规数.

这是四舍五入到下一个幂的延伸.

我有一个整数值N,它可能包含大的素因子,我想把它四舍五入到只由小素因子组成的数字(2,3和5)

例子:

• f(18) == 18 == 21 * 32
• f(19) == 20 == 22 * 51
• f(257) == 270 == 21 * 33 * 51

找到满足此要求的最小数字的有效方法是什么？

涉及的值可能很大,所以我想避免枚举从1开始的所有常规数字或维护所有可能值的数组.

免责声明:关于它有很多问题,但我没有找到任何需要恒定记忆的问题.

汉明数是一个数字2^i*3^j*5^k,其中i,j,k是自然数.

是否有可能在O(N)时间和O(1)(常数)存储器中产生第N个汉明数？在生成下我的意思是完全生成器,即你只能输出结果而不读取先前生成的数字(在这种情况下,内存将不是常量).但是你可以保存一些常数.

我看到只有具有常量内存的最佳算法并不比O(N log N)好,例如,基于优先级队列.但有没有数学证明在O(N)时间内构造算法是不可能的？

(这很令人兴奋!)我知道,主题是众所周知的.最先进的(在Haskell以及其他语言中)有效生成汉明数字的无限增加序列,没有重复和没有遗漏,长期以来一直是如此(AFAIK - 并且它等同于原始Edsger Dijkstra的代码)太):

hamm :: [Integer]
hamm = 1 : map (2*) hamm `union` map (3*) hamm `union` map (5*) hamm
  where
    union a@(x:xs) b@(y:ys) = case compare x y of
        LT -> x : union  xs  b
        EQ -> x : union  xs  ys
        GT -> y : union  a   ys

我问的问题是,你能找到让它在任何重要方面更有效的方法吗？它仍然是最先进的技术还是实际上可以通过两次更快的速度和更好的经验增长启动来改善这一点？

如果您的答案是肯定的,请显示代码,并与上述相比,讨论其速度和经验增长顺序(它的运行速度约为~ n^1.05 .. n^1.10前几十万个数字).此外,如果它存在,这个有效的算法是否可以扩展到生成一系列具有任何给定素数的平滑数？

我正在尝试生成可以用表格表示的所有倍数的列表，其中 a、b 和 c 是整数。我尝试了以下方法，

[ a * b * c | a <- map (2^) [0..], b <- map (3^) [0..], c <- map (5^) [0..] ] 

但它只列出了 5 的幂，而从未列出 2 或 3。

编辑：抱歉，看来我没有足够澄清这个问题。我想要的是一个有序的无限列表，虽然我可以对有限列表进行排序，但我觉得好像可能有一个更有效的解决方案。