第n个丑数 [英] nth ugly number

查看:191
本文介绍了第n个丑数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

号,其唯一的首要因素是2,3或5被称为难看号码。

Numbers whose only prime factors are 2, 3 or 5 are called ugly numbers.

例如:

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

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

1可以被认为是2 ^ 0

1 can be considered as 2^0.

我正在寻找第n个丑数。请注意,这些数字是非常稀疏分布为n变大。

I am working on finding nth ugly number. Note that these numbers are extremely sparsely distributed as n gets large.

我写了一个计算,如果给定的数字是丑,不是一个简单的程序。对于n> 500 - 它成为超慢。我试着用记忆化 - 观察:ugly_number * 2,ugly_number * 3,ugly_number * 5都是丑陋的。即使它是缓慢的。我试着用日志的一些性质 - 因为这将减少这个问题从乘法加法 - 但是,没有多少运气呢。想到跟大家分享这一点。任何有趣的想法?

I wrote a trivial program that computes if a given number is ugly or not. For n > 500 - it became super slow. I tried using memoization - observation: ugly_number * 2, ugly_number * 3, ugly_number * 5 are all ugly. Even with that it is slow. I tried using some properties of log - since that will reduce this problem from multiplication to addition - but, not much luck yet. Thought of sharing this with you all. Any interesting ideas?

使用类似的概念,以筛埃拉托色尼的(感谢匿名)

Using a concept similar to "Sieve of Eratosthenes" (thanks 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个丑陋的数量。

i is the nth ugly number.

即使这是pretty的慢。我试图寻找第1500号难看。

Even this is pretty slow. I am trying to find 1500th ugly number.

推荐答案

在Java中的一个简单快速的解决方案。用途方法描述的匿名。
在这里, TreeSet的只是能够在它返回的最小元素的容器。 (没有重复存储。)

A simple fast solution in Java. Uses approach described by Anon..
Here TreeSet is just a container capable of returning smallest element in it. (No duplicates stored.)

    int n = 20;
    SortedSet<Long> next = new TreeSet<Long>();
    next.add((long) 1);

    long cur = 0;
    for (int i = 0; i < n; ++i) {
        cur = next.first();
        System.out.println("number " + (i + 1) + ":   " + cur);

        next.add(cur * 2);
        next.add(cur * 3);
        next.add(cur * 5);
        next.remove(cur);
    }

由于第1000个丑数为5120万,将它们存储在布尔[] 不是一个真正的选择。

Since 1000th ugly number is 51200000, storing them in bool[] isn't really an option.

修改
作为上下班(调试愚蠢休眠)消遣,这里是完全线性的解决方案。由于 marcog 的想法!

edit
As a recreation from work (debugging stupid Hibernate), here's completely linear solution. Thanks to marcog for idea!

    int n = 1000;

    int last2 = 0;
    int last3 = 0;
    int last5 = 0;

    long[] result = new long[n];
    result[0] = 1;
    for (int i = 1; i < n; ++i) {
        long prev = result[i - 1];

        while (result[last2] * 2 <= prev) {
            ++last2;
        }
        while (result[last3] * 3 <= prev) {
            ++last3;
        }
        while (result[last5] * 5 <= prev) {
            ++last5;
        }

        long candidate1 = result[last2] * 2;
        long candidate2 = result[last3] * 3;
        long candidate3 = result[last5] * 5;

        result[i] = Math.min(candidate1, Math.min(candidate2, candidate3));
    }

    System.out.println(result[n - 1]);

这个想法是,计算 A [1] ,我们可以使用 A [J] * 2 的一些 J&LT;我。但是,我们还需要确保1) A [J] * 2 - ; A [1 - 1]。 2)Ĵ是最小的
然后, A [1] = MIN(A [J] * 2,[K] * 3,[T] * 5)

The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that 1) a[j]*2 > a[i - 1] and 2) j is smallest possible.
Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5).

这篇关于第n个丑数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆