英文題目傳送門，中文題目傳送門
目標是要找出2, 3, 5的倍數，並且是由小而大算起的第1500個！
最開始的想法是由小而大一個個的找，一開始不知道著了什麼魔，一直覺得得用遞迴來做，設計了devideFactors函數，如果遇到可以被5, 3, 2整除、而且商為1的數就一層層的return 1回去，如果沒有整除那就再丟給deviceFactors去繼續計算，直到沒有辦法被5, 3, 2整除，就會return 0，做為停止的flag值。
就變成了下面醜醜的怪獸程式碼：
#include <stdio.h>
#include <stdlib.h>
int devideFactors(int value){
int flag = 0;
if (value >= 5){
if (value % 5 == 0){
if ( value/5 == 1 ){
/* get ugly value*/
flag = 1;
} else {
/* go next run*/
flag = devideFactors(value/5);
}
}
}
if (value >= 3){
if ( value % 3 == 0){
if ( value/3 == 1 ){
/* get value*/
flag = 1;
} else {
/* go next run*/
flag = devideFactors(value/3);
}
}
}
if (value >= 2){
if (value % 2 == 0){
if (value/2 == 1){
/* get value*/
flag = 1;
} else {
/* go next run*/
flag = devideFactors(value /2);
}
}
}
return flag;
}
int main( int argc , char *argv []) {
int i = 2, j = 2, k;
int flag = 0;
while (1){
if (devideFactors(i) == 1){
/* printf("order == %d, number == %d\n", j, i);*/
if (++j > 1500)
break;
}
i++;
}
printf("The 1500'th ugly number is %d" , i );
return 0;
}
經過一段不算短的運算時間後，得到了答案，但是UVa也給了TLE，拒絕了這組程式碼
請示google大神之後，找到了GeeksforGeeks上的這篇文章，他所寫的解題概念蠻清楚的，如果勇於看原文的話可以直上原文，該文章中提到了兩種方法，一種是類似剛剛上述的方法，只是他先將數值不斷除以2，直到產生餘數（無法整除，表示被除數已非2的倍數），再將數值除以3，再除以5，如果商數為1的話，表示他是2, 3, 5的倍數！
舉例來說，假設要檢查300是否為Ugly Number（英文實在太長了，怒用中文，就叫你「醜數」吧）
- 首先除以5得60，再除以5得12，此時商數無法再被5整除，換下一個因數3
- 接著除以3得4，此時商數無法再被3整除，換下一個因數2
- 4除2得2，2再除2得1，無法繼續整除，餘數為1，確認300（2^2 * 3 * 5^2）為醜數，檢查結束
按照上述方法，可以不用遞迴，直接用while除，不能整除就換下一個因數，最後如果餘1就是醜數！
#include <stdio.h>
#include <stdlib.h>
int devideByFactors(int a, int b){
while (a % b == 0)
a = a /b;
return a;
}
int isUglyNumber(int value){
int flag;
flag = devideByFactors(value , 5);
flag = devideByFactors(value , 3);
flag = devideByFactors(value , 2);
return (flag == 1)? 1 : 0;
}
int main(int argc , char *argv []) {
int i = 2, j = 2, k;
int flag = 0;
while (1){
if (devideFactors(i) == 1){
/* printf("order == %d, number == %d\n", j, i);*/
if (++ j > 1500)
break;
}
i++;
}
printf("The 1500'th ugly number is %d" , i);
return 0;
}
根據geeksforgeeks網站說，上述程式碼的時間複雜度為O(1)，另外上面這個方法仍然是會慢到被UVa退件QQ
接下來就是另一種思考方式，醜數的序列為1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...，而每個醜數都可以除以2, 3, 5，因此醜數又可以依照這種思考方式，分成下面三組數列：
- 1x2, 2x2, 3x2, 4x2, 5x2, 6x2, 8x2, ...
- 1x3, 2x3, 3x3, 4x3, 5x3, 6x3, 8x3, ...
- 1x5, 2x5, 3x5, 4x5, 5x5, 6x5, 8x5, ...
我們可以發現，這三個序列都是將先前已算出的醜數再乘以2, 3, 5，來得出下一個醜數。
演算法流程：
- 宣告並出使化uglyNums陣列記錄已排序的醜數
uglyNums[1600] = {[0 ... 1599] = 1}; - 初始化第一個醜數
uglyNumIndex = 1; - 初始化陣列index，i2, i3, i5皆指向uglyNums陣列的第一個元素。
i2 = i3 = i5 = 0; - 初始化下一輪待比較的醜數
next_multiple_0f_2 = uglyNums[i2]*2;
next_multiple_0f_3 = uglyNums[i2]*3;
next_multiple_0f_5 = uglyNums[i2]*5; - 使用for迴圈不斷尋找下一個醜數，直到找到第1500個
for (i = 1; i < 1500; i++){
/* find the smallest ugly number */
next_ugly_no = Min(next_multiple_0f_2, next_multiple_0f_3, next_multiple_0f_5);
/* save it as the ugly number we have got */
uglyNums[i] = next_ugly_no;
/* increase the index to count next ugly number*/
/* if it equals to the ugly number we have got in this loop */
if (next_ugly_no == next_multiple_0f_2){
i2++;
next_multiple_0f_2 = uglyNums[i2]*2;
}
if (next_ugly_no == next_multiple_0f_3){
i3++;
next_multiple_0f_3 = uglyNums[i3]*3;
}
if (next_ugly_no == next_multiple_0f_5){
i5++;
next_multiple_0f_5 = uglyNums[i5]*5;
}
} /* end of for loop */ - 回傳next_ugly_number
運行時的變數變化：
初始化
uglyNums[] = | 1 |
i2 = i3 = i5 = 0;
第一次迴圈
uglyNums[1] = Min(uglyNums[i2]*2, uglyNums[i3]*3, uglyNums[i5]*5)
= Min(2, 3, 5)
= Min(2, 3, 5)
= 2
uglyNums[] = | 1 | 2 |
i2 = 1, i3 = i5 = 0 (i2增加了)
第二次迴圈
uglyNums[2] = Min(uglyNums[i2]*2, uglyNums[i3]*3, uglyNums[i5]*5)
= Min(4, 3, 5)
= Min(4, 3, 5)
= 3
uglyNums[] = | 1 | 2 | 3 |
i2 = 1, i3 = 1, i5 = 0 (i3增加了)
第三次迴圈
uglyNums[3] = Min(uglyNums[i2]*2, uglyNums[i3]*3, uglyNums[i5]*5)
= Min(4, 6, 5)
= Min(4, 6, 5)
= 3
uglyNums[] = | 1 | 2 | 3 | 4 |
i2 = 2, i3 = 1, i5 = 0 (i2增加了)
第四次迴圈
uglyNums[4] = Min(uglyNums[i2]*2, uglyNums[i3]*3, uglyNums[i5]*5)
= Min(6, 6, 5)
= Min(6, 6, 5)
= 5
uglyNums[] = | 1 | 2 | 3 | 4 | 5 |
i2 = 2, i3 = 1, i5 = 1 (i5增加了)
第五次迴圈
uglyNums[5] = Min(uglyNums[i2]*2, uglyNums[i3]*3, uglyNums[i5]*5)
= Min(6, 6, 10)
= Min(6, 6, 10)
= 6
uglyNums[] = | 1 | 2 | 3 | 4 | 5 | 6 |
i2 = 3, i3 = 2, i5 = 1 (i2, i3增加了)
持續計算直到第1500個醜數被算出來，
程式碼如下：
#include <stdio.h>
#include <stdlib.h>
int getMin( int a , int b , int c){
if (a <= b && a <= c){
return a;
}else if (b <= a && b <= c){
return b;
}else if (c <= a && c <= b){
return c;
}
}
int main( int argc , char *argv []) {
int i2 = 1, i3 = 1, i5 = 1;
int uglyVal = 1;
int uglyNumIndex = 1;
int uglyNums [1600] = {[0 ... 1599] = 1};
while(uglyNumIndex++ < 1500){
uglyVal = getMin(uglyNums [i2]*2, uglyNums[i3]*3, uglyNums [i5]*5);
uglyNums[uglyNumIndex] = uglyVal;
if (uglyVal == uglyNums[i2]*2)
i2 ++;
if (uglyVal == uglyNums[i3]*3)
i3 ++;
if (uglyVal == uglyNums[i5]*5)
i5 ++;
/*printf("uglyNumIndex %d, value %d\n", uglyNumIndex, uglyVal);*/
}
/* don't forget the dot in the end... */
printf("The 1500'th ugly number is %d.\n" , uglyVal);
return 0;
}
然後就成功被UVa接受了（灑花）~程式時間複雜度為O(n)。
總結：
最後真的是一個超級簡潔的寫法，重點就是已經算出來的東西不要重複計算，可以想想如何再運用，有效增加程式運算效率，不止要算得出來，更要很快地算出來！
以後比較理解時間複雜度後，再來做分析！
| 這封郵件來自 Evernote。Evernote 是您專屬的工作空間，免費下載 Evernote |
Comments
Post a Comment