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 150′th ugly number.
METHOD 1 (Simple)
Thanks toNedylko Draganovfor suggesting this solution.
Algorithm:
Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.
To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.
For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing
25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.
下面是这个简单方法,这里带了可以打印所有小于n的ugly number的程序:
int maxDivide(int num, int div)
{
while (num % div == 0)
{
num /= div;
}
return num;
}
bool isUgly(int num)
{
num = maxDivide(num, 2);
num = maxDivide(num, 3);
num = maxDivide(num, 5);
return num == 1? true:false;
}
int getNthUglyNo(int n)
{
int c = 0;
int i = 0;
while (c < n)
{
if (isUgly(++i)) c++;
}
return i;
}
#include <vector>
using std::vector;
vector<int> getAllUglyNo(int n)
{
vector<int> rs;
for (int i = 1; i <= n; i++)
{
if (isUgly(i)) rs.push_back(i);
}
return rs;
}
动态规划法:
注意:可能会有重复的数字要跃过,程序注释出去了。否则答案错误!
细想一下,其实一句话概括就是:
由最小的Ugly number算起,然后每个都分别乘以2,3,5得到最终答案。
class UglyNumbers
{
public:
int getNthUglyNo(int n, vector<int> &rs)
{
if (n < 1) return n;
int n2 = 2, n3 = 3, n5 = 5;
int i2 = 0, i3 = 0, i5 = 0;
rs.resize(n, 1);
for (int i = 1; i < n; i++)
{
int t = min(n2, min(n3,n5));
if (t == n2)
{
rs[i] = n2;
n2 = rs[++i2]*2;
}
if (t == n3) //注意:不能使用else,避免重复
{
rs[i] = n3;
n3 = rs[++i3]*3;
}
if (t == n5) //注意:不能使用else
{
rs[i] = n5;
n5 = rs[++i5]*5;
}
}
return rs.back();
}
};
测试:
int main()
{
unsigned no = getNthUglyNo(35);
printf("ugly no. is %d \n", no);
vector<int> rs = getAllUglyNo(35);
for (auto x:rs) cout<<x<<" ";
cout<<endl;
UglyNumbers un;
printf("Ugly no. is %d \n", un.getNthUglyNo(35, rs));
for (auto x:rs) cout<<x<<" ";
cout<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
geeks-for-geeks-solutions:有关Geeks-for-Geeks的问题的解决方案。解决方案可用于C ++
2022最新版:GEEKS V1.0.10主题:在线学习市场WordPress主题.rar
Geeks2TheRescue:使用MERN的Web App,旨在连接雄心勃勃的开发人员
geeks_algorithms 极客算法编码问题
带有React JS的WebApp样板 要求: 确保您使用的是节点版本10 安装软件包: $ npm install 创建一个.env文件: $ cp .env.example .env 开始编码! 以及具有实时重新加载功能的webpack开发服务器(适用于Windows...
夏季极客提交 这个Web应用程序被配制成在Innnovaccer SDE实习分配的一部分,使用的NodeJS,MongoDB的,NodeMailer的电子邮件和Nexmo的手机信息,根据。 预习 报到表格 结帐电子邮件 使用的技术 ...
欢迎来到4Geeks学院 <\编码时间>内容关于。创始人。团队。奖项。校友关于4Geeks是一家大公司,感觉就像一家小公司;每个人都可以访问,我们喜欢与人接触,我们相信量身定制的教育,而不会离开您的工作,并且100%...
:sparkles: gloomhaven-geeks :sparkles: 这是一个使用Git作为的网站。 它是在不到一分钟的时间内使用创建的。 您可以像这样,或探索一些变体。 如何不同: :artist_palette: 看 :pencil: 内容管理系统 :gear: 静态...
geeks for geeks上的资源,大家下载下,我攒点几分,呵呵。
极客换极客 Geeks-For-Geeks 实习文章 使用 scapy 嗅探数据包 - 使用 Javascript 和 DOM 创建棋盘模式 - 如何将链接从一个 iframe 加载到另一个 iframe -
Geeks for Geeks的DSA练习: :
本题的难度并不在最短路径本身这个算法,而是在于堆的操作: 1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好...
Geeks3D Furmark(OpenGL显卡基准测试工具)V1.17.1 中文官方版
Hardware Hacking Projects for Geeks 英文chm 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
geek极客们都用什么神器,这篇文章给了你答案。
Mac OS X For Unix Geeks 2003
Ubuntu for Non-Geeks (Fourth Edition)
当你准备面试 Java 编程工作时,考虑将被问到的问题非常重要。这些面试问题可能将因许多因素而异,包括公司类型、职位级别以及你面试的公司的经营时间。考虑这么多因素,你如何准备回答这些问题?通过考虑展示你的 ...
Cooking.for.Geeks, hope all programer have good food
A HashMap for Geeks and normal programmers.