题目分析

题意简述

丑数是指质因数仅为 $2$、$3$ 或 $5$ 的数，按照惯例，$1$ 也被视为丑数。给定一个正整数 $n$（$n \leq 1500$），需要找出并输出第 $n$ 个丑数。当输入的 $n$ 为 $0$ 时，程序结束。

输入

输入包含多组数据，每组数据为一个正整数 $n$（$n \leq 1500$），当输入 $n = 0$ 时，输入结束。

输出

对于每组非零的 $n$，输出第 $n$ 个丑数。

解题思路

动态规划思想

可以采用动态规划的方法来生成丑数序列。由于丑数只能由已有的丑数乘以 $2$、$3$ 或 $5$ 得到，我们可以维护三个指针 $num2$、$num3$ 和 $num5$，分别表示乘以 $2$、$3$ 和 $5$ 能得到下一个丑数的当前丑数的位置。

状态转移

• 初始化第一个丑数 $biao[1] = 1$。
• 对于第 $i$ 个丑数，它是 $biao[num2] \times 2$、$biao[num3] \times 3$ 和 $biao[num5] \times 5$ 中的最小值。
• 若 $biao[i]$ 等于 $biao[num2] \times 2$，则将 $num2$ 指针向后移动一位；若等于 $biao[num3] \times 3$，则将 $num3$ 指针向后移动一位；若等于 $biao[num5] \times 5$，则将 $num5$ 指针向后移动一位。

代码实现

//POJ1338
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 1510
 
using namespace std;
 
int biao[MAXN + 5];
 
void makeprime()
{
    biao[1] = 1;
    int num2 = 1, num3 = 1, num5 = 1;
    for(int i = 2;i <= 1510; i ++)
    {
        biao[i] = min(biao[num2] * 2, min(biao[num3] * 3, biao[num5] * 5));
        if(biao[i] == biao[num2] * 2) num2 ++;
        if(biao[i] == biao[num3] * 3) num3 ++;
        if(biao[i] == biao[num5] * 5) num5 ++;
    }
}
 
int main()
{
    makeprime();
 
    int n;
    while(scanf("%d", &n) != EOF, n)
    {
        printf("%d\n", biao[n]);
    }
    return 0;
}

代码说明

1. 全局数组：biao[MAXN + 5] 用于存储丑数序列，其中 biao[i] 表示第 $i$ 个丑数。
2. makeprime 函数：
   • 初始化 biao[1] = 1，因为 $1$ 是第一个丑数。
   • 初始化三个指针 $num2$、$num3$ 和 $num5$ 都为 $1$。
   • 通过循环从第 $2$ 个丑数开始生成，每次取 $biao[num2] \times 2$、$biao[num3] \times 3$ 和 $biao[num5] \times 5$ 中的最小值作为第 $i$ 个丑数。
   • 根据生成的丑数更新相应的指针。
3. main 函数：
   • 调用 makeprime 函数生成丑数序列。
   • 使用 while 循环读取输入的 $n$，当 $n$ 不为 $0$ 时，输出 biao[n]，即第 $n$ 个丑数。

通过以上步骤，我们可以高效地生成丑数序列并输出指定位置的丑数。