您现在的位置是:首页 > 文章详情

经典算法详解(9)寻找丑数

日期:2018-07-12点击:364

题目:我们把只含有因子2、3、5的数称为丑数。例如6、8都是丑数,而14不是丑数,因为它含有因子7.通常也把1当做丑数。编程找出1500以内的全部丑数。注意:使用的算法效率应尽量高。

C++实现:

 1 #include<iostream>  2  3 using namespace std;  4  5 //判断一个数是否是丑数,uglynum=2*2……*2*3*3*……*3*5*5……*5组成  6 int isUglyNumber(int n) {  7 while (n%2==0)  8  {  9 n /= 2; 10  } 11 while (n%3==0) 12  { 13 n /= 3; 14  } 15 while (n%5==0) 16  { 17 n /= 5; 18  } 19 return n == 1; 20 } 21 //方法1:逐个判断是否是丑叔,思路简单,但是计算冗余,因为越到后面很多都不是丑数也在计算。 22 int get_Ugly_fir(int number) { 23 int i = 1; 24 int count = 0; 25 while (i<=number) 26  { 27 if (isUglyNumber(i)) { 28 cout << i << "\t"; 29 count++; 30 if (count % 10 == 0) 31 cout << endl; 32  } 33 i++; 34  } 35 return count; 36 } 37 38 //方法二:算法效率高。 39 //思路:(1)后面的丑数肯定是已存在的丑数乘以2、3或者5,找到比现有丑数大的且是最小的丑数作为下一个丑数(如何找是关键)。 40 //2分别从现有丑数中从前往后乘以丑数,找到第一个大于当前所有丑数的值以及位置,3、5同样如此,再把他们相乘之后的结果做对比,取最小的。 41 //下次将从上一次的位置开始往下找,这样将不会出现冗余,详细见如下函数。 42 43 int Next_Ugly(int ugly_arr[], int *loc2, int *loc3, int *loc5, int *index) { 44 while (ugly_arr[*loc2] * 2 <= ugly_arr[*index]) { //千万注意这里是小于等于,不要写成小于了 45 (*loc2)++; 46  } 47 while (ugly_arr[*loc3] * 3 <= ugly_arr[*index]) { 48 (*loc3)++; 49  } 50 while (ugly_arr[*loc5] * 5 <= ugly_arr[*index]) { 51 (*loc5)++; 52  } 53 if (ugly_arr[*loc2] *2< ugly_arr[*loc3]*3) { 54 return (ugly_arr[*loc2] * 2 < ugly_arr[*loc5] * 5) ? ugly_arr[*loc2] * 2 : ugly_arr[*loc5] * 5; 55  } 56 else { 57 return (ugly_arr[*loc3] * 3) < ugly_arr[*loc5] * 5 ? ugly_arr[*loc3] * 3 : ugly_arr[*loc5] * 5; 58  } 59 } 60 61 int get_Ugly_sec(int num) { 62 int ugly_arr[1000]; 63 int index = 0, value = 1; 64 int loc2=0, loc3=0, loc5=0; 65 while (value<=num) { 66 ugly_arr[index] = value; 67 cout << ugly_arr[index] << "\t"; 68 if ((index + 1) % 10 == 0) 69 cout << endl; 70 71 value = Next_Ugly(ugly_arr, &loc2, &loc3, &loc5, &index); 72 index++; 73  } 74 return index; 75 } 76 77 int main(int argc, char *argv[]) { 78 get_Ugly_fir(1500); 79 cout << endl; 80 get_Ugly_sec(1500); 81  getchar(); 82 return 0; 83 }

(1)说明:总共使用了两种办法,第一种算法效率低,编程简单,第二种算法效率高,编程相对复杂。

(2)方法二思路:后面的丑数肯定是已存在的丑数乘以2、3或者5,找到比现有丑数大的且是最小的丑数作为下一个丑数(如何找是关键)。用2分别从现有丑数中从前往后乘以丑数,找到第一个大于当前所有丑数的值以及位置,3、5同样如此,再把他们相乘之后的结果做对比,取最小的。下次将从上一次的位置开始往下找,这样将不会出现冗余。

原文链接:https://yq.aliyun.com/articles/611873
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章