首页 > 代码库 > hdu1058 Humble Numbers（丑数）

hdu1058 Humble Numbers（丑数）

2024-07-10 21:46:39   215人阅读

       丑数：只包含一定的质因子的数称丑数，例如包含2,3,5.我们就把2，3，4，5，6，8，9，10，12，15.......。但我们通常把1称作为第一个丑数。

 
解题思路：我们现在做的这道题，就是以2,3,5,7为质因子，要我们求第n个丑数（以1为第一个丑数），可以采用DP的思想来解决。我们先以array[1]=1为基础，在它乘以质因子取得最小的数为有序数组的第二个，然后依次类推。写出状态转移方程：array[n] = Min(array[n2]*2, array[n3]*3, array[n5]*5, array[n7]*7);这就是这道题的解题思路吧。
 
贴上代码：
 
 
#include <stdio.h>int Min(int num1, int num2, int num3, int num4)   //求出4个数中的最小的一个{    int min1, min2;    min1 = num1 > num2 ? num2 : num1;    min2 = num3 > num4 ? num4 : num3;    return (min1 > min2 ? min2 : min1);}void Ugly(int array[])      //将各个丑数求出按照顺序{    array[1] = 1;    int mark;    int n, n2 = 1, n3 = 1, n5 = 1, n7 = 1;    for(n = 2; n<=5842; n++)    {        mark = Min(array[n2]*2, array[n3]*3, array[n5]*5, array[n7]*7);    //状态转移方程        array[n] = mark;        if(mark%2 == 0)     //若是质因子的倍数，则加1            n2++;        if(mark%3 == 0)            n3++;        if(mark%5 == 0)            n5++;        if(mark%7 == 0)            n7++;    }}void Output(int array[], int n)     //输出格式的控制{    if(n%10 ==1 && n%100 != 11)        printf("The %dst humble number is %d.\n", n, array[n]);    else if(n%10 ==2 && n%100 != 12)        printf("The %dnd humble number is %d.\n", n, array[n]);    else if(n%10 == 3 && n%100 != 13)        printf("The %drd humble number is %d.\n", n, array[n]);    else        printf("The %dth humble number is %d.\n", n, array[n]);}int main(){    int n;    int array[6000];    Ugly(array);    while(scanf("%d", &n) != EOF && n != 0)    {        Output(array, n);    }    return 0;}

 


联系
我们