思路:
通过 2 ,3 ,5, 7这4个数来构造Humble Numbers;
对于用dp[]数组存的数要事先打表;
AC代码:
#include<stdio.h> int dp[5843]; int n; int Min(int a,int b,int c,int d) { if(a<=b&&a<=c&&a<=d)return a; else if(b<=a&&b<=c&&b<=d)return b; else if(c<=a&&c<=b&&c<=d)return c; else return d; } int main() { int i; int t2,t3,t5,t7; int t; dp[1]=1; t2=t3=t5=t7=1; for(i=2;i<=5842;i++) { t=Min(2*dp[t2],3*dp[t3],5*dp[t5],7*dp[t7]); if(t==2*dp[t2])t2++; if(t==3*dp[t3])t3++; if(t==5*dp[t5])t5++; if(t==7*dp[t7])t7++; dp[i]=t; } while(scanf("%d",&n)!=-1&&n) { if(n%10==1&&n%100!=11)printf("The %dst humble number is %d.\n",n,dp[n]); else if(n%10==2&&n%100!=12)printf("The %dnd humble number is %d.\n",n,dp[n]); else if(n%10==3&&n%100!=13)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; }