丑数
丑数
1944864971 发表于2年前
丑数
  • 发表于 2年前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

http://poj.org/problem?id=1338
题意:
因子中只含2 3 5的数成为丑数;

分析:
可以判断每一个数是不是丑数,但是这样太慢,可以根据定义直接求出每一个丑数

因为每一个丑数都是在已有的丑数中通过乘以2或3或5得来的
第一步: 每一个数都乘以2,会得到很多大于或者小于当前的最大丑数,小于当前的最大丑数已经在当前丑数序列中,因此不用记录
因为我们要递增的找出丑数所以只需刚刚好大于当前的最大丑数即可并记录下来;
第二步 :每一个数都乘以3...................................记录下刚刚大于当前最大的丑数即可

第三步 ;每一个数都乘以5...................................记录下刚刚大于当前最大的丑数即可

第四步:找出三个数中最小的数就是下一个丑数;

#include
#include
using namespace std;
int ugly[1550];
void print()
{
ugly[1]=1;
ugly[2]=2;
ugly[3]=3;
ugly[4]=4;
ugly[5]=5;

 int n=5;
 bool max1Op=true,max2Op=true,max3Op=true;
 int max1,max2,max3;
 while(n<=1500)
 {
     for(int i=1;i<=n;i++)
    {

     if(max1Op)  max1=ugly[i]*2;
     if(max1>ugly[n])max1Op=false;
     if(max2Op)  max2=ugly[i]*3;
     if(max2>ugly[n])max2Op=false;
     if(max3Op)  max3=ugly[i]*5;
     if(max3>ugly[n])max3Op=false;
    }
    max1Op=true,max2Op=true,max3Op=true;
    ++n;
    ugly[n]=min(max1,min(max2,max3));
 }

}
int main()
{
print();
int n;
while(scanf("%d",&n),n)
printf("%d\n",ugly[n]);
return 0;

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: