HDACM1058
此题有两个地方值得关注：
1.输出格式：由样品输出的格式我们可以看出 “st”, “nd”, “rd”, or “th” 有这4种后缀格式的，所以输出有4种情况：
①当n%10==1&&n%100！=11时，是以st为后缀
②当n%10==2&&n%100！=12时，是以nd为后缀
③当n%10==3&&n%100！=13时，是以rd为后缀
④其他情况时，是以th为后缀
2.如何提高效率：显然这一题采用动态规划来做，不然就Time Limit Exceeded
根据题意可知，第n个数它是由若干个2，3，5，7相乘得出的数。所以采用动态规划来做。
a=1,b=1,c=1,d=1;
第1个数是特殊的，是table[1]=1。
第2个数是2–>table[2] = table[1]*2; a++ a=2
第3个数是3–>table[3] = table[1]*3; b++ b=2
第4个数是4–>table[4] = table[2]*2; a++ a=3
第5个数是5–>table[5] = table[1]*5; c++ c=2
第6个数是6–>table[6] = table[a]*2 || table[b]*3;a++,b++
第7个数是7–>table[7] = table[1]*7;d++
第8个数是8–>table[8] = table[4]*2;a++
第9个数是9–>table[9] = table[3]*3;b++
第10个数是10–>table[10] = table[a]*2 || table[c]*5;a++,c++
第11个数是12–>table[11] = table[a]*2 || table[b]*3;a++,b++
其中a表示的是num=2+…+2（a个2）
其中b表示的是num=3+…+3（b个3）
其中c表示的是num=5+…+5（c个5）
其中d表示的是num=7+…+7（d个7）
import java.util.Scanner;public class Main{public static void main(String[] args) {int table[] = new int[5843];//定义一个表makeTable(table);//给表初始化Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();if (n==0) {break;}System.out.print("The "+n);if (n%10==1 && n%100 != 11) {System.out.print("st");}else if (n%10==2 && n%100 != 12) {System.out.print("nd");}else if (n%10==3 && n%100 != 13) {System.out.print("rd");}else {System.out.print("th");}System.out.println(" humble number is "+table[n]+".");}}private static void makeTable(int[] table) {table[1] = 1;int a=1,b=1,c=1,d=1;for (int i = 2; i < table.length; i++) {table[i] = min4(table[a]*2,table[b]*3,table[c]*5,table[d]*7);if (table[i]==table[a]*2) {a++;}if (table[i]==table[b]*3) {b++;}if (table[i]==table[c]*5) {c++;}if (table[i]==table[d]*7) {d++;}}}private static int min4(int i, int j, int k, int l) {return min(min(min(i,j),k),l);}private static int min(int i, int j) {if (i>j) {return j;}return i;}
}