丑數演算法題
#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);
}