hdu 1058 Humble Numbers

( humble 不是谦虚的、卑微的意思么。。。为什么大家都说

 Humble Numbers 是丑数?)

题意：

输出第n个丑数。 Humble Number就是质因子只有2、3、5、7的数。

思路：

由于这个数总是2、3、5、7的倍数，所以每个数都可以分解成有限个2 3 5 7 的乘积，

dp方程为 dp[i]=f[i]=min(min(dp[p2]*2,dp[p3]*3),min(dp[p5]*5,f[p7]*7))

找到比f[i-1]大且最小的数。

由于新找到的数可能可以由多个dp[pi]*i(i=2、3、5、7）得到。为了避免找到的数出现重复，

要用四个if语句而不是if。。。else if。。。else if。。。else。。

输出的时候由于

11、12、13是以1、2、3结尾但是英语中仍然是th结尾的，所以要单独考虑后缀。

而20以后所有以1、2、3结尾的都同1、2、3的后缀一样为st、nd、rd。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int dp[5900];

void init()
{
    int p2,p3,p5,p7;
    dp[1]=1;
    p2=p3=p5=p7=1;
    for(int i=2;i<=5842;i++)
    {
        dp[i]=min(min(2*dp[p2],3*dp[p3]),min(5*dp[p5],7*dp[p7]));
        if(dp[i]==dp[p2]*2) p2++;
        if(dp[i]==dp[p3]*3) p3++;
        if(dp[i]==dp[p5]*5) p5++;
        if(dp[i]==dp[p7]*7) p7++;
    }
}

int main()
{
    init();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        if(n%100>=10 && n%100<=20)
            printf("The %dth humble number is %d.\n",n,dp[n]);
        else
        {
            if(n%10==1)
                printf("The %dst humble number is %d.\n",n,dp[n]);
            else if(n%10==2)
                printf("The %dnd humble number is %d.\n",n,dp[n]);
            else if(n%10==3)
                printf("The %drd humble number is %d.\n",n,dp[n]);
            else
                printf("The %dth humble number is %d.\n",n,dp[n]);
        }
    }
    return 0;
}

hdu 1058 Humble Numbers

原文：http://blog.csdn.net/u012841845/article/details/18603969