2007-02-15

【Q136】 Ugly Numbers

題目:
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1500'th ugly number.

  這題目看似簡單,用直覺的想法莫過於一一檢查其因數是否只有2, 3或5,對於這樣的演算法去run花了109秒。程式如下(或下載):

#include <stdio.h>
#include
<stdlib.h>
#include
<time.h>

int isUgly(int number) ;

int genUgly(int order) ;

int main() {
time_t start, end ;
time(&start) ;
int count = 0 ;
int i = 0 ;


while(count < 1500) {
if(isUgly(++i))
count++ ;
}
printf("%d\n", i) ;
time(&end) ;
printf("It takes %.0f seconds!!\n", difftime(end, start)) ;
system("pause") ;
return 0 ;
}


int isUgly(int number) {
while(!(number%2))
number >>= 1 ;
while(!(number%3))
number /= 3 ;
while(!(number%5))
number /= 5 ;

if(number > 1) {
return 0 ;
}
return 1 ;
}

  這題目的其中要義應該是要解題者想出更有效率的演算法,上面的作法是檢查該數字是不是Ugly Number;另一種想法則是去產生Ugly Number,用這演算法去run時間一秒都不需要,瞬間跑出結果,這也印證了好的演算法與不好的演算法差異是很大的!程式如下(或下載):

內容:
#include <stdio.h>
#include
<stdlib.h>

int number[1500] = {1, 2, 3, 4, 5} ;
int base[3] = {2, 3, 5} ;


int ugly(int order) ;
int genUgly(int count) ;

int main() {
printf("The 1500'th ugly number is %d.\n", ugly(1500) ) ;
system("pause") ;
return 0 ;
}


int ugly(int order) {
int count = 4 ;
int temp, i, j ;
int min ;
order-- ;
if(order < 5)
return number[order] ;
while(count < order) {
min = 0 ;
for(i=0 ; i<count ; i++) {
for(j=0 ; j<3 ; j++) {
temp = number[i]*base[j] ;
if(temp <= number[count]) {
continue ;
}
else if(min==0 min > temp) {
min = temp ;
}
}
}
number[++count] = min ;
}
return number[order] ;
}

沒有留言: