1058humblenumbers.txt

动态规划类练习,丑数的特点

#include "stdio.h"
#include "string.h"
#include<stdlib.h>
#define N 5843 

int min(int a,int b,int c,int d)
{
    int x=a>b?b:a;
    int y=c>d?d:c;
    int min=y>x?x:y;
    return min;
}


int main()
{
	int a,b,c,d,i,n;
    int f[N];
    a=1;b=1;c=1;d=1;
    f[1]=1;
    for(i=2;i<=N;i++)
    {
        f[i]=min(f[a]*2,f[b]*3,f[c]*5,f[d]*7);
        if(f[i]==f[a]*2)a++;
        if(f[i]==f[b]*3)b++;
        if(f[i]==f[c]*5)c++;
        if(f[i]==f[d]*7)d++;
    }

	while(scanf("%d",&n),n!=0)
	{
		if(n%100==11||n%100==12||n%100==13 ) //n是11、12、13特殊处理
			printf("The %dth humble number is %d.\n",n,f[n]);
		else if(n%10==1)
			printf("The %dst humble number is %d.\n",n,f[n]);
		else if(n%10==2)
			printf("The %dnd humble number is %d.\n",n,f[n]);
		else if(n%10==3)
			printf("The %drd humble number is %d.\n",n,f[n]);
		else
			printf("The %dth humble number is %d.\n",n,f[n]);
	}
	return 0;
}