丑数算法题
#include <iostream>
using namespace std;
int h[5850];
int n;
void Init()
{
int i;
int i1,i2,i3;
int t1,t2,t3;
h[1] = 1;
i1=i2=i3=1;
for(i=2;i<=5850;i++)
{
t1 = h[i1]*2; t2 = h[i2]*3;
t3 = h[i3]*5;
h[i]=min(t1,min(t2,t3));
if(h[i]==t1) i1++;
if(h[i]==t2) i2++;
if(h[i]==t3) i3++;
}
}
int main()
{
Init();
while(scanf("%d",&n)!=EOF && n)
{
printf("%d\n",h[n]);
}
return 0;
}
Ⅱ c++求丑数程序的优化（第一行输入整数T，表示求多少次 然后输入T个整数n。）
你这个属于暴力穷举，基本上不到100就要以秒计了，肯定超时
以前写过一个，主动产生丑数的算法,第1000个也就是1毫秒以内
算法的主要精神就是：后面的丑数是由前面的丑数*2，*3或者*5得来的，然后主动生成丑数序列，关于丑数算法具体细节原理，网上有很多文章，你可以自己搜索
#include<iostream>
#include<ctime>
usingnamespacestd;
intmin(inta,intb,intc)
{
intt=a<b?a:b;
returnt<c?t:c;
}
intuglnum(intn)
{
int*unum=newint[n];
intun,i,i2,i3,i5;
unum[0]=1;
i2=i3=i5=0;
for(i=1;i<n;++i)
{
un=min(unum[i2]*2,unum[i3]*3,unum[i5]*5);
i2+=(un==unum[i2]*2);
i3+=(un==unum[i3]*3);
i5+=(un==unum[i5]*5);
unum[i]=un;
}
un=unum[n-1];
delete[]unum;
returnun;
}
intmain()
{
intt,n;
time_tts;
cin>>t;
for(inti=0;i<t;++i)
{
cin>>n;
//ts=clock();
cout<<uglnum(n)<<endl;
//ts=clock()-ts;
//cout<<ts<<"ms"<<endl;
}
return0;
}
Ⅲ 1 系统的基本功能 所谓丑数，是指因子只含2,3,5的数。编写一个程序，求第1500个只有2,3,5因子的数。
#include<stdio.h>
#include<stdlib.h>
int main()
{
int count = 0;
int num = 2*3*5;
int i=0,j=0,k=0;
while(count < 1500) {
int tmp = num++;
i=0,j=0,k=0;
if(tmp % (2*3*5)) {
continue;
}
while(!(tmp % 2)) {
i ++;
tmp = tmp /2;
}
while(!(tmp % 3)) {
j ++;
tmp = tmp /3;
}
while(!(tmp % 5)) {
k ++;
tmp = tmp /5;
}
count ++;
//printf("The %dth number is x. x=2^%d*3^%d*5^%d\n", count, i, j, k);
}
printf("The %dth number is x. x=2^%d*3^%d*5^%d\n", count, i, j, k);
return 0;
}
c版本，改成c++很容易。
Ⅳ 请教一简单c语言问题：下面求1~1500丑数编程哪错了😭
#include<stdio.h>
boolIsUgly(intnumber)
{
while(number%2==0)
number/=2;
while(number%3==0)
number/3=;
while(number%5==0)
number/5=;
return(number==1)?true:false;
}
intmain()
{
inti;
for(i=0;i<1500;i++)
{
if(IsUgly(i)==1)
printf("%d ",i);
}
return0;
}
我按照你的截图运行了一下，报错没有定义IsUgly；是因为VC6.0没有bool的头文件，所以你使用bool是不对的；
我根据你的程序改进了一下，我们使用bool是为了得到返回值1或者0；
那么我可以尝试将bool改成int，在最后判断number是否是1的时候，返回1或者0；
下面是我改进的代码，
#include<stdio.h>
intIsUgly(intnumber)//将bool改成int定义IsUgly函数
{
while(number%2==0)
number=number/2;
while(number%3==0)
number=number/3;
while(number%5==0)
number=number/5;
return(number==1)?1:0;//如果number==1，返回1，否则返回0
}
intmain()
{
inti;
for(i=2;i<=1500;i++)//0除以2是0,0除以2的余数还是0，所以如果i=0，就是死循环，
//因为1不是丑数，所以建议从2开始循环；1-1500应该是包含1500的
//并且1500也是丑数,所以是小于等于1500
{
if(IsUgly(i)==1)
printf("%d ",i);
}
return0;
}
Ⅳ USACO，哪个大神帮我秒了
test3:77rwrwrwrwrwrwrwrwrwrwrwrw (->Break here) bw rwb 向左数是72个红色(r)向右数是2个蓝色(b)一共74个
Ⅵ acm h 1856
这题是经典的dp题，丑数问题。同学，你这题的算法有问题，而且照你这样算的话，题目要求的最大的第5842个数是2000000000，估计就超时了。我的ac代码，给你参考一下。
#include<iostream>
using namespace std;
int main()
{
int i,m,j,n,temp;
int a[5843];
int a1,a2,a3,a4;
a1=a2=a3=a4=1;
a[1]=1;
for(i=2;i<=5842;i++)
{
m=min(min(2*a[a1],3*a[a2]),min(5*a[a3],7*a[a4]));
if(m==2*a[a1]) a1++;
if(m==3*a[a2]) a2++;
if(m==5*a[a3]) a3++;
if(m==7*a[a4]) a4++;
a[i]=m;
}
while(scanf("%d",&n)!=EOF && n!=0)
{
if(n%10==1 && n%100!=11) printf("The %dst humble number is %d.\n",n,a[n]);
else if(n%10==2 && n%100!=12) printf("The %dnd humble number is %d.\n",n,a[n]);
else if(n%10==3 && n%100!=13) printf("The %drd humble number is %d.\n",n,a[n]);
else printf("The %dth humble number is %d.\n",n,a[n]);
}
return 0;
}
Ⅶ 3道C语言编程题，希望你们能帮助我
1.
#include <stdio.h>
int main()
{
int n,m,count=0;
scanf("%d",&n);
m = n;
while(m%2==0) m/=2;
while(m%3==0) m/=3;
while(m%5==0) m/=5;
while(m%7==0) m/=7;
if(m!=1)
{
printf("no\n");
return 0;
}
for(m=1;m<=n/2;m++)
{
if(n%m==0)
count++;
}
printf("%d\n",count);
}
----
2.
#include <stdio.h>
#include <math.h>
int main()
{
int n,m;
double temp;
scanf("%d",&n);
temp = sqrt(double(n));
for(m=2;m<=temp;m++)
{
if(n%m==0)
{
printf("no\n");
return 0;
}
}
printf("yes\n");
}
-----
3.
#include <stdio.h>
int main()
{
char s[1000];
char word[1000];
char* p;
int count = 0;
gets(s);
p = s;
while(sscanf(p,"%s",word)==1)
{
count++;
while(*p==' ') p++;
while(*p!=' '&&*p!=0) p++;
}
printf("%d\n",count);
}