2009-02-11 21:25:06來源不明
ACM 136 Q136: Ugly Numbers
這一題跟點我很像,一題學會可以寫2題=]
/************************************************************/
- #include<stdio.h>
- #include<stdlib.h>
- main()
- {
- int a,b;
- int ans[1501];
- int g5,g3,g2,m=1;
- ans[0]=1;
- for(a=1;a<=1499;a++)
- {
- for(g5=a/5;g5<a;g5++)
- if(ans[g5]*5>m) break;
- for(g3=g5;g3<m;g3++)
- if(ans[g3]*3>m) break;
- for(g2=g3;g2<m;g2++)
- if(ans[g2]*2>m) break;
- m=ans[g2]*2;
- if(m>ans[g3]*3)m=ans[g3]*3;
- if(m>ans[g5]*5)m=ans[g5]*5;
- ans[a]=m;
- }
- printf("The 1500'th ugly number is %d.",ans[1499]);
- /*system("pause");*/
- return 0;
- }
/******************加速版本 請觀察與上的不同**********/
#include<stdio.h>
#include<stdlib.h>
main()
{
int a,b;
int ans[1501];
int g5=0,g3=0,g2=0,m=1;
ans[0]=1;
for(a=1;a<=1499;a++)
{
for(;g5<a;g5++)
if(ans[g5]*5>m) break;
for(;g3<m;g3++)
if(ans[g3]*3>m) break;
for(;g2<m;g2++)
if(ans[g2]*2>m) break;
m=ans[g2]*2;
if(m>ans[g3]*3)m=ans[g3]*3;
if(m>ans[g5]*5)m=ans[g5]*5;
ans[a]=m;
}
printf("The 1500'th ugly number is %d.",ans[1499]);
return 0;
}