aiaiask.com©

开花即结果 提问即答案

Java算法:丑数
原始问题:

Java算法:丑数

丑数是指只包含因子2、3和5的正整数。根据定义,1是第一个丑数。我们可以通过以下步骤来生成丑数序列:

  1. 创建一个数组ugly[],用于存储生成的丑数。
  2. 初始化ugly[0]为1,表示第一个丑数。
  3. 创建三个指针p2、p3和p5,分别指向ugly[]中下一个将乘以2、3和5的丑数。
  4. 初始化p2、p3和p5为0。
  5. 从ugly[1]开始,通过以下步骤生成丑数序列:

    • 计算下一个丑数,即ugly[i] = min(ugly[p2] 2, ugly[p3] 3, ugly[p5] * 5)。
    • 如果ugly[i]等于ugly[p2] * 2,则增加p2。
    • 如果ugly[i]等于ugly[p3] * 3,则增加p3。
    • 如果ugly[i]等于ugly[p5] * 5,则增加p5。
  6. 重复步骤5,直到生成所需数量的丑数。

下面是用Java实现丑数生成的示例代码:

public class UglyNumber {
    public static int getUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;

        for (int i = 1; i < n; i++) {
            int nextUgly = Math.min(ugly[p2] * 2, Math.min(ugly[p3] * 3, ugly[p5] * 5));
            ugly[i] = nextUgly;

            if (nextUgly == ugly[p2] * 2) {
                p2++;
            }
            if (nextUgly == ugly[p3] * 3) {
                p3++;
            }
            if (nextUgly == ugly[p5] * 5) {
                p5++;
            }
        }

        return ugly[n - 1];
    }

    public static void main(String[] args) {
        int n = 10;
        int uglyNumber = getUglyNumber(n);
        System.out.println("第 " + n + " 个丑数是:" + uglyNumber);
    }
}

以上代码将生成第10个丑数,并输出结果。你可以根据需要修改变量n的值来生成不同位置的丑数。

Java算法:丑数
https://www.aiaiask.com/ask/44268.html
AI / 模型Siliconflow
时间 / DATEAugust 10, 2023, 1:59 PM
语言zh-CN
IP / 区域美国