不能直接output了,囧。
第一次嘗試用DP解題目,似乎也沒這麼難,
不過要想得到算法。
主要的想法參考於這裡!
真是好厲害!
humble number = (2 ^ w) * (3 ^ x) * (5 ^ y) * (7 ^ z)
用DP的想法是,一開始只有1,1會變成2 3 5 7,
而2 3 5 7各自再乘上2 3 5 7後共有16種組合,
但是沒這麼多,因為有重複的情況。
前項的結果再乘上2 3 5 7,必定也是humble number,
(偉哉DP,好強大)
再繼續深入思考,
若一開始只有1,乘上2 3 5 7之後,取其中最小的一個數值。
這個情況下是2,這樣的話,下次質數2就是從第二個humble number開始乘(即2 * 2),
3 5 7還是要乘第一個質數(即3 * 1 5 * 1 7 * 1),
接著四個數值繼續做比大小的動作(4 3 5 7相比),
這個情況下是3,所以下次質數3要從第二個humble number開始乘(即3 * 2)
也就是說,每次取完最小的值,
下次該質數就要從下一個humble number做相乘的動作,
因為上一個humble number已經乘完啦!
但還沒結束,還要考慮humble number相同的情況,
例如3 * 5或5 * 3,是一樣的,
所以如果一樣,就必須把3跟5的紀錄次數各 + 1,
意即,每次找到最小值之後,只要是2 3 5 7的乘積與此值相等,
就各要 + 1。
最後要注意ordinal number,以前英文沒學好,-_-,傻傻搞不清楚。
只要十位數是1,都是加th,(不管個位數是不是1 2 3)
其他的情況下,1 2 3分別加st nd rd,
其餘都是th。
/* ACM 443 Humble Numbers * mythnc * 2011/12/11 21:49:31 * run time: 0.012 */ #include <stdio.h> #include <string.h> #define MAXN 5842 void precal(int *); void output(int, int *); int main(void) { int ans[MAXN]; int n; precal(ans); while (scanf("%d", &n) && n != 0) output(n, ans); return 0; } /* precal: previous calculation the answer */ void precal(int *ans) { int t2, t3, t5, t7; int p2, p3, p5, p7, count; p2 = p3 = p5 = p7 = 0; ans[0] = count = 1; while (count < MAXN) { t2 = ans[p2] * 2; t3 = ans[p3] * 3; t5 = ans[p5] * 5; t7 = ans[p7] * 7; /* find the minimal */ if (t2 <= t3 && t2 <= t5 && t2 <= t7) ans[count] = t2; else if (t3 < t2 && t3 <= t5 && t3 <= t7) ans[count] = t3; else if (t5 < t2 && t5 < t3 && t5 <= t7) ans[count] = t5; else if (t7 < t2 && t7 < t3 && t7 < t5) ans[count] = t7; /* if same, prime number have to move to next */ if (t2 == ans[count]) p2++; if (t3 == ans[count]) p3++; if (t5 == ans[count]) p5++; if (t7 == ans[count]) p7++; count++; } } /* output: print out the answer in the format */ void output(int n, int *ans) { char number[3]; if (n % 100 < 10 || n % 100 > 20) switch (n % 10) { case 1: strcpy(number, "st"); break; case 2: strcpy(number, "nd"); break; case 3: strcpy(number, "rd"); break; default: strcpy(number, "th"); } else strcpy(number, "th"); printf("The %d%s humble number is %d.\n", n, number, ans[n - 1]); }
沒有留言:
張貼留言