ACM 443 Humble Numbers
http://www.tcgs.tc.edu.tw/~sagit/acm/
學習↑
不過有一些部分我不太了解,所以修改一部分讓我自己了解,之前用暴力法去尋找太慢了,改用倍數尋找的方式就快囉了。
/*************************************************************/
- #include<stdio.h>
- #include<stdlib.h>
- main()
- {
- int a,b;
- int ans[5844];
- int g7,g5,g3,g2,m;
- ans[0]=1;
- for(a=1;a<=5841;a++)
- {
- for(g7=a/7;g7<a;g7++) /*a/7只因為可能再小而已*/
- if(ans[g7]*7>m) break; /*尋找比原本數大的數 就跳出*/
- for(g5=g7;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;
- if(m>ans[g7]*7)m=ans[g7]*7;
- ans[a]=m;
- }
- int n;
- while(scanf("%d",&n)==1&&n!=0)
- {
- if(n%10==1&&n%100!=11)/*11.12.13 唸法不同*/
- {printf("The %dst humble number is %d.\n",n,ans[n-1]);continue;}
- if(n%10==2&&n%100!=12)
- {printf("The %dnd humble number is %d.\n",n,ans[n-1]);continue;}
- if(n%10==3&&n%100!=13)
- {printf("The %drd humble number is %d.\n",n,ans[n-1]);continue;}
- printf("The %dth humble number is %d.\n",n,ans[n-1]);
- }
- return 0;
- }
/**************加速版本 請觀察與上的不同***********************/
#include<stdio.h>
#include<stdlib.h>
main()
{
int a,b;
int ans[5844];
int g7=0,g5=0,g3=0,g2=0,m;
ans[0]=1;
for(a=1;a<=5841;a++)
{
for(;g7<a;g7++) /*a/7只因為可能再小而已*/
if(ans[g7]*7>m) break; /*尋找比原本數大的數 就跳出*/
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;
if(m>ans[g7]*7)m=ans[g7]*7;
ans[a]=m;
}
int n;
while(scanf("%d",&n)==1&&n!=0)
{
if(n%10==1&&n%100!=11)/*11.12.13 唸法不同*/
printf("The %dst humble number is %d.\n",n,ans[n-1]);
else if(n%10==2&&n%100!=12)
printf("The %dnd humble number is %d.\n",n,ans[n-1]);
else if(n%10==3&&n%100!=13)
printf("The %drd humble number is %d.\n",n,ans[n-1]);
else
printf("The %dth humble number is %d.\n",n,ans[n-1]);
}
return 0;
}