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