优客文库提供全面的范文格式和文档模板,包括申请书、合同、借据、证明、求职信等,助力您快速撰写专业文档。

Java算法:丑数

来自 美国 的网友 时间: 热度:°C 加入收藏 我要投稿 点赞()
丑数是指只包含因子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实现丑数生成的示例代码:

```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的值来生成不同位置的丑数。
221381
领取福利

微信扫码领取福利

微信扫码分享