題目鏈接：《Humble Numbers》
題意：如果一個數的所有質數因子都來自于 { 2, 3, 5, 7 } 這個集合，就把這個數字叫做“謙遜數”，或者“低調數”（Humble Number），現在給出一個數字 i （1 <= i <= 5842），要求輸出第 i 個 humble number，比如說，前 20 個 humble number 是：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27，
分析：這個題目的描述是非常簡單的，從 i 的限定范圍最大是 5842 以及范例輸出來看，很顯然出題人暗示了我們這個題目中涉及到的 humber number 不會超出 int 的范圍，因此我們可以放心的使用 int，而不用擔心超出表示范圍，
其次可以很容易的想到，需要一個 int 陣列，把需要的所有 humber number 放進去作為供查詢的表，但是生成這個表會比較耗時，所以很容易超過 2 秒的運行時間限制，所以我們需要更快的建立這個陣列，則觀察這個序列，因為所有的數字都是如下形式：
x[i] = (2 ^ k[0]) * (3 ^ k[1]) * (5 ^ k[2]) * (7 ^ k[3]);
這里 k 是一個陣列 ( int [ 4 ] )，元素表示 2， 3， 5， 7 這四個因子的冪，因此考慮從 x [ i ] 跳到下一個 x [ i + 1] 時，就是數字的這 4 個因子的冪在發生變化，因此只要知道從 x [ i ] 變化到 x [ i + 1 ] 時，陣列 k 如何變化即可，因此我們需要找出前 5842 個 humber number 中的所有規則，這樣就可以快速的得到前 5842 個 humber number，組建成我們要查的表，
觀察前面幾個數字，很容易發現出這些規則，例如：
1->2, 2->3, 3->4, 4->5, 5->6, ...
從 10 到 12 本質上還是應用的 5->6 ，因此只有相鄰且互質的數字（a, b），才屬于我們要找的規則（a -> b），其他的相鄰數字都是應用了上述規則中的某一條，
同時這些規則還有優先級的順序之分，從表面上看，應該是數字 a 和 b 越大，規則越優先，但實際上并非如此，例如：
從 75 到 80 ，應用的實際規則是 15->16 ，而不是 25->27 （這會產生從 75 變成 81，跳過了 80），因此規則的優先級排序需要按照 a->b 的放大倍數進行從小到大排序，放大倍數（b / a）越小的規則，越優先，考慮到這個規則很多（實際有 76 條），而且涉及的數字很大，所以人工找出所有規則是不現實的，所以我使用一個程式（稱之為代碼生成器）來專門找出所有的規則，并將其輸出成一個函式的代碼，函式的名稱是 GetNext，含義是根據當前的 humble number ，找出下一個 humble number，如下：
#include <vector> #include <algorithm> #include <iostream> #include <stdio.h> #include <string.h> typedef struct tagNODE { int from; int to; double ratio; //= to / from; } NODE; //x1, x2 是否是已經排好序的， bool IsSuccessive(NODE x1, NODE x2) { return x1.ratio < x2.ratio; } void Init(std::vector<int> &v1, int nSize) { v1.reserve(nSize); v1.clear(); v1.push_back(1); int nNumber = 2; int tmp; while(v1.size() < nSize) { tmp = nNumber; while((tmp % 2) == 0) tmp /= 2; while((tmp % 3) == 0) tmp /= 3; while((tmp % 5) == 0) tmp /= 5; while((tmp % 7) == 0) tmp /= 7; if(tmp == 1) v1.push_back(nNumber); ++nNumber; } } //x1, x2 是否是互質的（沒有公共因子） bool no_comm_factor(int x1, int x2) { if(x1 % 2 == 0 && x2 % 2 == 0) return false; if(x1 % 3 == 0 && x2 % 3 == 0) return false; if(x1 % 5 == 0 && x2 % 5 == 0) return false; if(x1 % 7 == 0 && x2 % 7 == 0) return false; return true; } //give x, find k; //x = 2^k[0] * 3^k[1] * 5^k[2] * 7^k[3]; void GetK(int x, int k[4]) { memset(k, 0, sizeof(int) * 4); while((x & 1) == 0) { x /= 2; k[0]++; } while(x % 3 == 0) { x /= 3; k[1]++; } while(x % 5 == 0) { x /= 5; k[2]++; } while(x % 7 == 0) { x /= 7; k[3]++; } } int main(int argc, char* argv[]) { std::vector<int> v1; //計算出前 5842 個 humber number，這一步需要花比較長的時間， Init(v1, 5842); //找出所有策略（即找出所有的相鄰的互質的 humber number 對）， std::vector<NODE> nodes; for(int i = 5841; i > 0; --i) { if(no_comm_factor(v1[i - 1], v1[i])) { NODE item; item.from = v1[i - 1]; item.to = v1[i]; item.ratio = item.to * 1.0 / item.from; nodes.push_back(item); } } //按照放大倍數從小到大進行規則排序， std::sort(nodes.begin(), nodes.end(), IsSuccessive); int iRule = 0; int k1[4], k2[4]; char buf[1024], *pos; FILE *fp = fopen("GetNextK_code.cpp", "w"); fputs("void GetNext(int* k)\n{\n", fp); typename std::vector<NODE>::const_iterator it; for(it = nodes.begin(); it != nodes.end(); ++it) { ++iRule; GetK(it->from, k1); GetK(it->to, k2); if(iRule == 1) strcpy(buf, "\tif("); else if(iRule == nodes.size()) strcpy(buf, "else"); else strcpy(buf, "\telse if("); pos = buf + strlen(buf); if(k1[0]) { sprintf(pos, "k[0] >= %d && ", k1[0]); pos += strlen(pos); } if(k1[1]) { sprintf(pos, "k[1] >= %d && ", k1[1]); pos += strlen(pos); } if(k1[2]) { sprintf(pos, "k[2] >= %d && ", k1[2]); pos += strlen(pos); } if(k1[3]) { sprintf(pos, "k[3] >= %d && ", k1[3]); pos += strlen(pos); } if(iRule == nodes.size()) { //最后一條規則 sprintf(pos, " //(rule %d) %d -> %d (%lf);\n\t{\n", iRule, it->from, it->to, it->ratio); } else { pos -= 4; //remove " && "; sprintf(pos, ") //(rule %d) %d -> %d (%lf);\n\t{\n", iRule, it->from, it->to, it->ratio); } pos += strlen(pos); //From if(k1[0]) { sprintf(pos, "\t\tk[0] -= %d;\n", k1[0]); pos += strlen(pos); } if(k1[1]) { sprintf(pos, "\t\tk[1] -= %d;\n", k1[1]); pos += strlen(pos); } if(k1[2]) { sprintf(pos, "\t\tk[2] -= %d;\n", k1[2]); pos += strlen(pos); } if(k1[3]) { sprintf(pos, "\t\tk[3] -= %d;\n", k1[3]); pos += strlen(pos); } //To if(k2[0]) { sprintf(pos, "\t\tk[0] += %d;\n", k2[0]); pos += strlen(pos); } if(k2[1]) { sprintf(pos, "\t\tk[1] += %d;\n", k2[1]); pos += strlen(pos); } if(k2[2]) { sprintf(pos, "\t\tk[2] += %d;\n", k2[2]); pos += strlen(pos); } if(k2[3]) { sprintf(pos, "\t\tk[3] += %d;\n", k2[3]); pos += strlen(pos); } strcpy(pos, "\t}\n"); fputs(buf, fp); fflush(fp); } fputs("}\n", fp); fclose(fp); return 0; }Code_Generator
使用上面的代碼生成器，我們就得到了所有的規則，就可以方便的真正的寫用于提交的代碼了，
為了從陣列 k 計算 humber number 的方便，這里我把 2, 3, 5, 7 的 n 次方提前計算好放到一個陣列里，這樣就能更快速的計算出 humber number，這樣這個題目也就算基本完成了，但是這也只不過是完成了這個題目的一半而已，因此這個題目還有一半大坑在于輸出格式中的 “-th” 后綴！為此我 WA 了 2， 3 次以后才把后綴規則寫對，簡單來說這里需要特別注意的就是：
所有形如 xx11, xx12, xx13 后綴都是 th （而不僅僅是 11, 12, 13 ），除此以為的 xxx1 用 st，xxx2 用 nd，xxx3 用 rd，所有其他都用 th，例如，1011th, 1012th ,1023th，這里需要特別注意，
最終提交代碼如下：
// ZOJ1095_HumbleNumbers.cpp // #include <vector> #include <iostream> //選擇出下一組 k 值，按照如下規則， // x = (2^k[0]) * (3^k[1]) * (5^k[2]) * (7^k[3]); void GetNext(int* k); int main(int argc, char* argv[]) { int i, x; int k[4] = { 0, 0, 0, 0 }; int a2[31] = { 1 }; //a2[k] = 2^k; int a3[20] = { 1 }; //a3[k] = 3^k; int a5[14] = { 1 }; //a5[k] = 5^k; int a7[12] = { 1 }; //a7[k] = 7^k; for(i = 1; i < 31; i++) { a2[i] = a2[i - 1] * 2; if(i < 20) a3[i] = a3[i - 1] * 3; if(i < 14) a5[i] = a5[i - 1] * 5; if(i < 12) a7[i] = a7[i - 1] * 7; } std::vector<int> v1; v1.reserve(5842); v1.push_back(1); while(v1.size() < 5842) { GetNext(k); x = a2[k[0]] * a3[k[1]] * a5[k[2]] * a7[k[3]]; v1.push_back(x); } while(true) { std::cin >> i; if(i == 0) break; else if(i % 100 != 11 && i % 10 == 1) std::cout << "The " << i << "st humble number is " << v1[i - 1] << "." << std::endl; else if(i % 100 != 12 && i % 10 == 2) std::cout << "The " << i << "nd humble number is " << v1[i - 1] << "." << std::endl; else if(i % 100 != 13 && i % 10 == 3) std::cout << "The " << i << "rd humble number is " << v1[i - 1] << "." << std::endl; else std::cout << "The " << i << "th humble number is " << v1[i - 1] << "." << std::endl; } return 0; } //以下代碼是從另一個程式生成的， //根據當前的 humble number，選出下一個 humble number， void GetNext(int* k) { if(k[1] >= 13 && k[3] >= 2) //(rule 1) 78121827 -> 78125000 (1.000041); { k[1] -= 13; k[3] -= 2; k[0] += 3; k[2] += 10; } else if(k[0] >= 4 && k[3] >= 9) //(rule 2) 645657712 -> 645700815 (1.000067); { k[0] -= 4; k[3] -= 9; k[1] += 17; k[2] += 1; } else if(k[0] >= 4 && k[2] >= 6) //(rule 3) 250000 -> 250047 (1.000188); { k[0] -= 4; k[2] -= 6; k[1] += 6; k[3] += 3; } else if(k[0] >= 1 && k[1] >= 7) //(rule 4) 4374 -> 4375 (1.000229); { k[0] -= 1; k[1] -= 7; k[2] += 4; k[3] += 1; } else if(k[0] >= 5 && k[3] >= 8) //(rule 5) 184473632 -> 184528125 (1.000295); { k[0] -= 5; k[3] -= 8; k[1] += 10; k[2] += 5; } else if(k[0] >= 5 && k[1] >= 1 && k[2] >= 2) //(rule 6) 2400 -> 2401 (1.000417); { k[0] -= 5; k[1] -= 1; k[2] -= 2; k[3] += 4; } else if(k[0] >= 9 && k[2] >= 1 && k[3] >= 5) //(rule 7) 43025920 -> 43046721 (1.000483); { k[0] -= 9; k[2] -= 1; k[3] -= 5; k[1] += 16; } else if(k[0] >= 6 && k[3] >= 7) //(rule 8) 52706752 -> 52734375 (1.000524); { k[0] -= 6; k[3] -= 7; k[1] += 3; k[2] += 9; } else if(k[0] >= 10 && k[3] >= 4) //(rule 9) 2458624 -> 2460375 (1.000712); { k[0] -= 10; k[3] -= 4; k[1] += 9; k[2] += 3; } else if(k[0] >= 7 && k[1] >= 4 && k[3] >= 6) //(rule 10) 1219784832 -> 1220703125 (1.000753); { k[0] -= 7; k[1] -= 4; k[3] -= 6; k[2] += 13; } else if(k[0] >= 14 && k[2] >= 3 && k[3] >= 1) //(rule 11) 14336000 -> 14348907 (1.000900); { k[0] -= 14; k[2] -= 3; k[3] -= 1; k[1] += 15; } else if(k[0] >= 11 && k[3] >= 3) //(rule 12) 702464 -> 703125 (1.000941); { k[0] -= 11; k[3] -= 3; k[1] += 2; k[2] += 7; } else if(k[0] >= 15) //(rule 13) 32768 -> 32805 (1.001129); { k[0] -= 15; k[1] += 8; k[2] += 1; } else if(k[0] >= 12 && k[1] >= 5 && k[3] >= 2) //(rule 14) 48771072 -> 48828125 (1.001170); { k[0] -= 12; k[1] -= 5; k[3] -= 2; k[2] += 11; } else if(k[2] >= 8 && k[3] >= 3) //(rule 15) 133984375 -> 134217728 (1.001742); { k[2] -= 8; k[3] -= 3; k[0] += 27; } else if(k[1] >= 7 && k[2] >= 4 && k[3] >= 2) //(rule 16) 66976875 -> 67108864 (1.001971); { k[1] -= 7; k[2] -= 4; k[3] -= 2; k[0] += 26; } else if(k[1] >= 1 && k[2] >= 10) //(rule 17) 29296875 -> 29360128 (1.002159); { k[1] -= 1; k[2] -= 10; k[0] += 22; k[3] += 1; } else if(k[1] >= 14 && k[3] >= 1) //(rule 18) 33480783 -> 33554432 (1.002200); { k[1] -= 14; k[3] -= 1; k[0] += 25; } else if(k[3] >= 10) //(rule 19) 282475249 -> 283115520 (1.002267); { k[3] -= 10; k[0] += 21; k[1] += 3; k[2] += 1; } else if(k[1] >= 8 && k[2] >= 6) //(rule 20) 102515625 -> 102760448 (1.002388); { k[1] -= 8; k[2] -= 6; k[0] += 21; k[3] += 2; } else if(k[1] >= 15 && k[2] >= 2) //(rule 21) 358722675 -> 359661568 (1.002617); { k[1] -= 15; k[2] -= 2; k[0] += 20; k[3] += 3; } else if(k[2] >= 1 && k[3] >= 6) //(rule 22) 588245 -> 589824 (1.002684); { k[2] -= 1; k[3] -= 6; k[0] += 16; k[1] += 2; } else if(k[2] >= 7 && k[3] >= 3) //(rule 23) 26796875 -> 26873856 (1.002873); { k[2] -= 7; k[3] -= 3; k[0] += 12; k[1] += 8; } else if(k[1] >= 5 && k[3] >= 5) //(rule 24) 4084101 -> 4096000 (1.002913); { k[1] -= 5; k[3] -= 5; k[0] += 15; k[2] += 3; } else if(k[2] >= 13) //(rule 25) 1220703125 -> 1224440064 (1.003061); { k[2] -= 13; k[0] += 8; k[1] += 14; } else if(k[2] >= 3 && k[3] >= 2) //(rule 26) 6125 -> 6144 (1.003102); { k[2] -= 3; k[3] -= 2; k[0] += 11; k[1] += 1; } else if(k[1] >= 12 && k[3] >= 4) //(rule 27) 1275989841 -> 1280000000 (1.003143); { k[1] -= 12; k[3] -= 4; k[0] += 14; k[2] += 7; } else if(k[2] >= 9) //(rule 28) 1953125 -> 1959552 (1.003291); { k[2] -= 9; k[0] += 7; k[1] += 7; k[3] += 1; } else if(k[1] >= 6 && k[3] >= 1) //(rule 29) 5103 -> 5120 (1.003331); { k[1] -= 6; k[3] -= 1; k[0] += 10; k[2] += 1; } else if(k[2] >= 5) //(rule 30) 3125 -> 3136 (1.003520); { k[2] -= 5; k[0] += 6; k[3] += 2; } else if(k[1] >= 13) //(rule 31) 1594323 -> 1600000 (1.003561); { k[1] -= 13; k[0] += 9; k[2] += 5; } else if(k[3] >= 9) //(rule 32) 40353607 -> 40500000 (1.003628); { k[3] -= 9; k[0] += 5; k[1] += 4; k[2] += 6; } else if(k[1] >= 7 && k[2] >= 1) //(rule 33) 10935 -> 10976 (1.003749); { k[1] -= 7; k[2] -= 1; k[0] += 5; k[3] += 3; } else if(k[3] >= 6) //(rule 34) 117649 -> 118098 (1.003816); { k[3] -= 6; k[0] += 1; k[1] += 10; } else if(k[3] >= 5) //(rule 35) 16807 -> 16875 (1.004046); { k[3] -= 5; k[1] += 3; k[2] += 4; } else if(k[0] >= 4 && k[2] >= 2 && k[3] >= 2) //(rule 36) 19600 -> 19683 (1.004235); { k[0] -= 4; k[2] -= 2; k[3] -= 2; k[1] += 9; } else if(k[0] >= 1 && k[1] >= 4 && k[3] >= 4) //(rule 37) 388962 -> 390625 (1.004275); { k[0] -= 1; k[1] -= 4; k[3] -= 4; k[2] += 8; } else if(k[0] >= 5 && k[3] >= 1) //(rule 38) 224 -> 225 (1.004464); { k[0] -= 5; k[3] -= 1; k[1] += 2; k[2] += 2; } else if(k[0] >= 9 && k[2] >= 4) //(rule 39) 320000 -> 321489 (1.004653); { k[0] -= 9; k[2] -= 4; k[1] += 8; k[3] += 2; } else if(k[0] >= 6 && k[1] >= 5) //(rule 40) 15552 -> 15625 (1.004694); { k[0] -= 6; k[1] -= 5; k[2] += 6; } else if(k[0] >= 10) //(rule 41) 1024 -> 1029 (1.004883); { k[0] -= 10; k[1] += 1; k[3] += 3; } else if(k[1] >= 5 && k[2] >= 2 && k[3] >= 3) //(rule 42) 2083725 -> 2097152 (1.006444); { k[1] -= 5; k[2] -= 2; k[3] -= 3; k[0] += 21; } else if(k[1] >= 6 && k[2] >= 4) //(rule 43) 455625 -> 458752 (1.006863); { k[1] -= 6; k[2] -= 4; k[0] += 16; k[3] += 1; } else if(k[2] >= 1 && k[3] >= 3) //(rule 44) 1715 -> 1728 (1.007580); { k[2] -= 1; k[3] -= 3; k[0] += 6; k[1] += 3; } else if(k[1] >= 4 && k[3] >= 2) //(rule 45) 3969 -> 4000 (1.007811); { k[1] -= 4; k[3] -= 2; k[0] += 5; k[2] += 3; } else if(k[2] >= 3) //(rule 46) 125 -> 126 (1.008000); { k[2] -= 3; k[0] += 1; k[1] += 2; k[3] += 1; } else if(k[1] >= 5) //(rule 47) 243 -> 245 (1.008230); { k[1] -= 5; k[2] += 1; k[3] += 2; } else if(k[1] >= 3 && k[3] >= 4) //(rule 48) 64827 -> 65536 (1.010937); { k[1] -= 3; k[3] -= 4; k[0] += 16; } else if(k[1] >= 4 && k[2] >= 2) //(rule 49) 2025 -> 2048 (1.011358); { k[1] -= 4; k[2] -= 2; k[0] += 11; } else if(k[3] >= 4) //(rule 50) 2401 -> 2430 (1.012078); { k[3] -= 4; k[0] += 1; k[1] += 5; k[2] += 1; } else if(k[1] >= 2 && k[3] >= 3) //(rule 51) 3087 -> 3125 (1.012310); { k[1] -= 2; k[3] -= 3; k[2] += 5; } else if(k[0] >= 4 && k[2] >= 1) //(rule 52) 80 -> 81 (1.012500); { k[0] -= 4; k[2] -= 1; k[1] += 4; } else if(k[0] >= 5 && k[1] >= 3) //(rule 53) 864 -> 875 (1.012731); { k[0] -= 5; k[1] -= 3; k[2] += 3; k[3] += 1; } else if(k[1] >= 2 && k[3] >= 1) //(rule 54) 63 -> 64 (1.015873); { k[1] -= 2; k[3] -= 1; k[0] += 6; } else if(k[1] >= 3 && k[2] >= 2) //(rule 55) 675 -> 686 (1.016296); { k[1] -= 3; k[2] -= 2; k[0] += 1; k[3] += 3; } else if(k[3] >= 2) //(rule 56) 49 -> 50 (1.020408); { k[3] -= 2; k[0] += 1; k[2] += 2; } else if(k[0] >= 4 && k[1] >= 1) //(rule 57) 48 -> 49 (1.020833); { k[0] -= 4; k[1] -= 1; k[3] += 2; } else if(k[0] >= 9) //(rule 58) 512 -> 525 (1.025391); { k[0] -= 9; k[1] += 1; k[2] += 2; k[3] += 1; } else if(k[2] >= 1 && k[3] >= 1) //(rule 59) 35 -> 36 (1.028571); { k[2] -= 1; k[3] -= 1; k[0] += 2; k[1] += 2; } else if(k[1] >= 3) //(rule 60) 27 -> 28 (1.037037); { k[1] -= 3; k[0] += 2; k[3] += 1; } else if(k[0] >= 3 && k[1] >= 1) //(rule 61) 24 -> 25 (1.041667); { k[0] -= 3; k[1] -= 1; k[2] += 2; } else if(k[0] >= 2 && k[2] >= 1) //(rule 62) 20 -> 21 (1.050000); { k[0] -= 2; k[2] -= 1; k[1] += 1; k[3] += 1; } else if(k[0] >= 7) //(rule 63) 128 -> 135 (1.054688); { k[0] -= 7; k[1] += 3; k[2] += 1; } else if(k[1] >= 1 && k[2] >= 1) //(rule 64) 15 -> 16 (1.066667); { k[1] -= 1; k[2] -= 1; k[0] += 4; } else if(k[0] >= 1 && k[3] >= 1) //(rule 65) 14 -> 15 (1.071429); { k[0] -= 1; k[3] -= 1; k[1] += 1; k[2] += 1; } else if(k[2] >= 2) //(rule 66) 25 -> 27 (1.080000); { k[2] -= 2; k[1] += 3; } else if(k[0] >= 5) //(rule 67) 32 -> 35 (1.093750); { k[0] -= 5; k[2] += 1; k[3] += 1; } else if(k[1] >= 2) //(rule 68) 9 -> 10 (1.111111); { k[1] -= 2; k[0] += 1; k[2] += 1; } else if(k[0] >= 3) //(rule 69) 8 -> 9 (1.125000); { k[0] -= 3; k[1] += 2; } else if(k[3] >= 1) //(rule 70) 7 -> 8 (1.142857); { k[3] -= 1; k[0] += 3; } else if(k[0] >= 1 && k[1] >= 1) //(rule 71) 6 -> 7 (1.166667); { k[0] -= 1; k[1] -= 1; k[3] += 1; } else if(k[2] >= 1) //(rule 72) 5 -> 6 (1.200000); { k[2] -= 1; k[0] += 1; k[1] += 1; } else if(k[0] >= 2) //(rule 73) 4 -> 5 (1.250000); { k[0] -= 2; k[2] += 1; } else if(k[1] >= 1) //(rule 74) 3 -> 4 (1.333333); { k[1] -= 1; k[0] += 2; } else if(k[0] >= 1) //(rule 75) 2 -> 3 (1.500000); { k[0] -= 1; k[1] += 1; } else //(rule 76) 1 -> 2 (2.000000); { k[0] += 1; } }Code_ZOJ_1095_HumbleNumbers
此外，當然我也想到，代碼生成也可以這樣，把提前計算好的 5842 個 humble number 依次放入 int 陣列，或者一個全域變數陣列，應該也是可行的，但這樣的代碼行數會變更多，顯得非常的“暴力”，我沒有去嘗試這樣做，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/102048.html
標籤：C++
下一篇：嚴蔚敏資料結構原始碼及習題決議