首页 > 代码库 > 两种方法求丑数
两种方法求丑数
我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
方法1 :
暴力破解,逐个判断
代码:
<pre name="code" class="cpp">#include <iostream> #include <vector> using namespace std; //判断是否是丑数 bool isUgly(int index){ while(index % 2 == 0){ index /= 2; } while(index % 3 == 0){ index /= 3; } while(index % 5 ==0){ index /=5; } if(index == 1) return true; else return false; } int print(int index){ int count=1; int number = 0; int uglyFound =0; while(uglyFound < index){ ++number; if(isUgly(number)){ ++uglyFound; } } return number; } int main() { cout<<print(1500); return 0; }
运行结果:
方法2 : 采用空间换时间,只是判断丑数。一个丑数可以有另外一个丑数* 2 或者*3 或者*5 得到。
#include <iostream> #include <vector> using namespace std; int Min(int pm2,int pm3,int pm5){ int min = pm2 > pm3 ? pm3 : pm2; return min > pm5 ? pm5 : min; } void print(unsigned int index){ if(index == 0) return; int * pUglyNumber = new int[index]; int pNextIndex=1; pUglyNumber[0] = 1; int *pM2 = pUglyNumber; int *pM3 = pUglyNumber; int *pM5 = pUglyNumber; while(pNextIndex < index){ int min=Min(*pM2 * 2,*pM3 * 3, *pM5 * 5); pUglyNumber[pNextIndex] = min; while(*pM2 * 2 <=pUglyNumber[pNextIndex]) ++pM2; while(*pM3 * 3 <=pUglyNumber[pNextIndex]) ++pM3; while(*pM5 * 5 <= pUglyNumber[pNextIndex]) ++pM5; pNextIndex ++; } int ugly = pUglyNumber[pNextIndex - 1]; delete [] pUglyNumber; cout<< ugly; } int main() { print(7); return 0; }
运行结果:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。