首页 > 代码库 > 算法分析---寻找丑数

算法分析---寻找丑数

什么是丑数:

一个数的因子仅仅包括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所不能比拟的,这是用空间来换取效率的结果。

技术分享



算法分析---寻找丑数