POJ 2247 Humble Numbers：四指針生成 2,3,5,7 平滑數

問題描述

Humble 數定義為質因子僅包含 2、3、5、7 的正整數。求第 n 個 Humble 數（n ≤ 5842），並按英文序數詞綴正確輸出（如 1st, 2nd, 3rd, 4th, 11th, 12th, 13th...）。

解法：動態規劃 / 多指針合併

維護四個指針 p2, p3, p5, p7，分別指向下一個待乘 2/3/5/7 的 humble 數索引。每步取四者最小值作為下一個 humble 數，並前進對應指針（可能多個指針同時前進以去重）。

humble[1] = 1;
for i = 2 .. 5842:
    humble[i] = min(2*humble[p2], 3*humble[p3], 5*humble[p5], 7*humble[p7]);
    if (humble[i] == 2*humble[p2]) ++p2;
    if (humble[i] == 3*humble[p3]) ++p3;
    if (humble[i] == 5*humble[p5]) ++p5;
    if (humble[i] == 7*humble[p7]) ++p7;

序數詞綴處理

根據個位數與十位數判斷：

• 11, 12, 13 → th
• 個位 1 → st（除 11）
• 個位 2 → nd（除 12）
• 個位 3 → rd（除 13）
• 其餘 → th

代碼片段

long humble[6000];
int main() {
    // ... 生成 humble ...
    int n;
    while (cin >> n && n) {
        int last2 = n % 100, last1 = n % 10;
        cout << "The " << n;
        if (last1 == 1 && last2 != 11) cout << "st";
        else if (last1 == 2 && last2 != 12) cout << "nd";
        else if (last1 == 3 && last2 != 13) cout << "rd";
        else cout << "th";
        cout << " humble number is " << humble[n] << "." << endl;
    }
}