287
poj 2247 Humble Numbers
这道题和1338几乎一模一样
不同就是数据量变得更大了，而且多了一个素数 7 参与运算，这道题我用了更“高明”的数字转换技术，用了重定向，可是因为代码太长不能提交，不能用终极打表了，只能另谋他法。。。
打表程序：
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
freopen("result.txt","w",stdout);
for(i=1;i<=5842;i++)
{
printf("%d,",ans[i]);
if(i%10==0)
printf("\n");
}
return 0;
}
后来又想了一种方法，理论上一定可行，但是超内存。。。
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=2000000000;
int ans[5850];
int visit[MAXN];
void Process()
{
int num;
int pos=1; //正在处理的数字
int count=1; //存储指针
int flag; //用来看是否处理过了
ans[1]=1;
while(count<=5842)
{
flag=0;
num=ans[pos]; //赋给num，用来处理
if(num*2<=MAXN && visit[num*2]==0)
{
count++;
ans[count]=num*2;
flag=1;
visit[ans[count]]=1;
}
if(num*3<=MAXN && visit[num*3]==0)
{
count++;
ans[count]=num*3;
flag=1;
visit[ans[count]]=1;
}
if(num*5<=MAXN && visit[num*5]==0)
{
count++;
ans[count]=num*5;
flag=1;
visit[ans[count]]=1;
}
if(num*7<=MAXN && visit[num*7]==0)
{
count++;
ans[count]=num*7;
flag=1;
visit[ans[count]]=1;
}
if(flag==0)
break;
//test
//printf("pos = %d: count=%d\n",pos,count);
pos++;
}
sort(ans,ans+count);
//sort(&ans[1],&ans[count+1]);
//test
for(int i=1;i<=100;i++)
printf("i = %d: ans=%d\n",i,ans[i]);
}
int main()
{
//打表
Process();
int n;
while (scanf("%d",&n)!=EOF && n)
{
if (n%10==1 && n%100!=11)
printf("The %dst humble number is %d.\n",n,ans[n]);
else if (n%10==2 && n%100!=12)
printf("The %dnd humble number is %d.\n",n,ans[n]);
else if (n%10==3 && n%100!=13)
printf("The %drd humble number is %d.\n",n,ans[n]);
else
printf("The %dth humble number is %d.\n",n,ans[n]);
}
return 0;
}
后来继续去做这种题实在没有太多思路，看懂了网上一个同学的结题报告，基本上参考了他的代码，他的思路很清晰简单。
题意：找出所有因子中只有2,3,5,7的数，给出n，求出第n个这样的数
思路：
每个这样的数都可以表示为num2 * num3 * num5 * num7，其中num i 表示i的一个幂
解释得再清楚些，2^mi2 * 3^mi3 * 5^mi5 * 7^mi7
num2, num3, num5, num7分别从1开始，依次记下小于20亿的乘积，最后对这个数组排序。这就是预处理阶段
后面的大家都会了
总结：11th，而不是11st。32ms【注意：这里不仅仅是11，12，13。。。111，112，113等等也是】
AC的代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAXN=2000000000;
int ans[5850];
void Process()
{
__int64 num2,num3,num5,num7;
int total=0;
num2=1;
while(num2<=MAXN)
{
num3=1;
while(num2*num3<=MAXN)
{
num5=1;
while(num2*num3*num5<=MAXN)
{
num7=1;
while(num2*num3*num5*num7<=MAXN)
{
ans[++total]=num2*num3*num5*num7;
num7*=7;
}
num5*=5;
}
num3*=3;
}
num2*=2;
}
sort(&ans[1],&ans[total+1]);
}
int main()
{
//打表
Process();
int n;
while (cin>>n && n)
{
if (n%10 == 1 && n%100 != 11)
printf("The %dst humble number is %d.\n", n, ans[n] );
else
if (n%10 == 2 && n%100 != 12)
printf("The %dnd humble number is %d.\n", n, ans[n] );
else
if (n%10 == 3 && n%100 != 13)
printf("The %drd humble number is %d.\n", n, ans[n] );
else
printf("The %dth humble number is %d.\n", n, ans[n] );
}
return 0;
}
后来之前参考的代码也A了：
#include <iostream>
#include <stdio.h>
using namespace std;
const int M=5850;
int ans[M];
int getMin(int a,int b,int c,int d)
{
int rs=0;
rs=a<b?a:b;
rs=rs<c?rs:c;
rs=rs<d?rs:d;
return rs;
}
int main()
{
int a2,a3,a5,a7,i,tmp,n;
a2=1;
a3=1;
a5=1;
a7=1;
ans[1]=1;
for(i=2;i<M;i++)
{
tmp=getMin(ans[a2]*2,ans[a3]*3,ans[a5]*5,ans[a7]*7);
ans[i]=tmp;
if(tmp==ans[a2]*2)
++a2;
if(tmp==ans[a3]*3)
++a3;
if(tmp==ans[a5]*5)
++a5;
if(tmp==ans[a7]*7)
++a7;
}
while (cin >> n && n)
{
if (n%10 == 1 && n%100 != 11)
printf("The %dst humble number is %d.\n", n, ans[n] );
else
if (n%10 == 2 && n%100 != 12)
printf("The %dnd humble number is %d.\n", n, ans[n] );
else
if (n%10 == 3 && n%100 != 13)
printf("The %drd humble number is %d.\n", n, ans[n] );
else
printf("The %dth humble number is %d.\n", n, ans[n] );
}
return 0;
}
最后更新：2017-04-03 14:53:53