算法分析---尋找醜數

什麼是醜數：

一個數的因子隻包含2，3，5的數稱為醜數。數字1特别對待也看作是醜數，是以從1開始的10個醜數分别為1，2，3，4，5，6，8，9，10，12。

因子的概念:

整數m除以n，得到無餘數的商，則稱n是m的一個因子。如8的因子有1、2、4、8。而醜數要求的因子隻包含2、3、5。是以醜數中的因子應了解為質因子。即因子為質數，質數又稱素數，指一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數。與質數相對應的數稱為合數。

現在要求寫一個程式，輸出從1開始的第N個醜數。如第一個醜數為1，第二個醜數為2，第十個醜數為12

判斷是否是醜數的算法：

設待判斷整數位M，M循環除以2直到不能整除，此時接着循環除以3直到不能整除，接着循環除以5直到商為1或者不能整除為止。商為1且餘數為0則為醜數，否則為非醜數。

如：醜數12

12/2 = 6

6/2 = 3;

3/2 不能整除

3/3 = 1; 結束，12是醜數

非醜數26

26/2 = 13

13/2 不能整除

13/3 不能整除

13/5 不能整除

結束，26不是整數

尋找醜數算法1：

（1）設定一個計數器用來統計出現的醜數的個數

（2）從1開始周遊每一個整數，判斷是否是醜數，如果是醜數則計數器加1，否則周遊下一個整數。

（3）當計數器的值=N時，停止周遊，輸出醜數。

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

int isUgly(int number){ //判斷number是否是醜數
	while(number%2==0){ //判斷數能否被2整除
		number=number/2; 
	}

	while(number%3==0){ //判斷數能否被3整除
		number=number/3;
	}

	while(number%5==0){ //判斷數能否被5整除
		number=number/5;
	}
	
	if(number == 1) //
		return 1;
	else
		return 0;
}

int findUgly(int N){  //尋找從1開始的第N個醜數
	int count=0; //用于計數
	int number=1; //從1開始周遊
	while(1){
		if(isUgly(number)){  //如果number是醜數計數器加1
			count++;
		}
		if(count == N)  //找到第N個醜數，傳回醜數
			return number;
		else
			number++; 
	}
}

void main(){
	int N=0;
	scanf("%d",&N);
	clock_t start = clock();
	printf("%d\n",findUgly(N));
	clock_t stop = clock();
	printf("耗時:%lf\n",(double)(stop - start) / CLOCKS_PER_SEC);
}
           

上面算法從1開始周遊，來尋找第N個醜數，當N很大時花費的時間會很多。當N為1400的時候消耗23秒，随着N的增大，耗時相當嚴重

尋找醜數算法2：

想辦法從上一個醜數推斷出下一個醜數，而不需要從1開始周遊再判斷。從1開始的10個醜數分别為1，2，3，4，5，6，8，9，10，12。可以發現除了1以外，醜數都是由某個醜數*2或者*3或者*5得到的。如2是醜數1*2得到的，3是醜數1*3得到的，4是醜數1*4得到的，5是醜數1*5得到的，6是醜數2*3得到的……

具體算法步驟：

（1）從第一個醜數1開始，求出1*2=2 ，1*3=3 ，1*5 = 5；

（2）取上面乘積中大于1的最小值2，作為第二個醜數（醜數是個遞增序列，是以第i+1個醜數一定比第i個醜數）

（3）求醜數2之前的醜數與2、3、5的乘積：1*2=2 ，1*3=3 ，1*5 = 5； 2*2 = 4； 2*3 = 6； 2*5 =10；

（4）取上面乘積中大于2的最小值3，作為第三個醜數

       ……

       ……

（i）取出醜數i之前的醜數分别與2、3、5的乘積

（i+1）取乘積中大于i的最小值作為醜數

（i+2）重複(i)(i+1)的步驟直到計數器等于N

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

#define MaxLen 99999

//用于求出3個數的最小值
int compare(int chenTwo,int chenThree,int chenFive){
	if(chenTwo <=chenThree){
		if(chenTwo <= chenFive)
			return chenTwo;
		else
			return chenFive;
	}
	else if(chenThree <= chenFive)
		return chenThree;
	else
		return chenFive;
}

//找出第N個醜數
int findUgly(int N){
	int ugly[MaxLen]={1}; //用于儲存醜數的數組，将醜數1存入數組中
	int count=1; //數組中僅有醜數1，是以計數器為1

	while(1){
		int chenTwo = 0;
		int chenThree = 0;
		int chenFive = 0;

		/*
			ugly數組中最新的一個醜數為ugly[count-1],
			ugly[count-1]之前的醜數與2相乘,
			求出第一個乘積大于ugly[count-1]的值儲存在chenTwo中
		*/
		for(int i = 0 ; i < count ; i++){ 
			if(ugly[i]*2 >ugly[count-1]){
				chenTwo = ugly[i]*2;
				break;
			}
		}

		/*
			ugly數組中最新的一個醜數為ugly[count-1],
			ugly[count-1]之前的醜數與3相乘,
			求出第一個乘積大于ugly[count-1]的值儲存在chenThree中
		*/
		for(i = 0 ; i < count ; i++){
			if(ugly[i]*3 >ugly[count-1]){
				chenThree = ugly[i]*3;
				break;
			}
		}

		/*
			ugly數組中最新的一個醜數為ugly[count-1],
			ugly[count-1]之前的醜數與5相乘,
			求出第一個乘積大于ugly[count-1]的值儲存在chenFive中
		*/
		for(i = 0 ; i < count ; i++){
			if(ugly[i]*5 >ugly[count-1]){
				chenFive = ugly[i]*5;
				break;
			}
		}

		//chenTwo，chenThree，chenFive的最小值為新的醜數，存入ugly數組中
		ugly[count]=compare( chenTwo, chenThree, chenFive);
		count++;
		if(count==N) //第N個醜數
			return ugly[count-1];
	}
}

void main(){
	int N=0;
	scanf("%d",&N);
	clock_t start = clock();
	printf("%d\n",findUgly(N));
	clock_t stop = clock();
	printf("耗時:%lf\n",(double)(stop - start) / CLOCKS_PER_SEC);
}
           

當輸入N=1400時，耗時還不足0.1秒。可見算法2的速度是算法1所不能比拟的，這是用空間來換取效率的結果。