挑戰極限 Part1 - 極限加法
作法:十億進制
此題由本人出題,因為太少人想到這個!
進階加速:(第2程式碼)把if (進位的)拿掉 發現速度更快
另外發現:每次都跑465次進位?嘗試用紀錄上一次的進位次數來做看看
因為上一次的進位+上第前2項，頂多增加一位數，但是呢，這樣跑似乎沒有比較快
(第3程式碼)
/*************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define N 20000
#define N2 500
int math[20001][500];
main()
{
int a,b,n;
math[0][0]=0;math[1][0]=1;
for(a=2;a<=N;a++)
for(b=0;b<N2;b++)
{
math[a][b]=math[a][b]+math[a-1][b]+math[a-2][b];
if (math[a][b]>=1000000000)
{
math[a][b+1]=math[a][b+1]+math[a][b]/1000000000;
math[a][b]=math[a][b]%1000000000;
}
}
while(scanf("%d",&n)==1)
{
for(a=N2-1;a>=0;a--)
if(math[n][a]!=0)
{
printf("%d",math[n][a]);
for(b=a-1;b>=0;b--)
printf("%09d",math[n][b]);
break;
}
printf("\n");
}
return 0;
}
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
int math[20001][465]={0};
main()
{
int a,b,c,n,N2=2,N=1000000000;
math[0][0]=0;math[1][0]=1;
for(a=2;a<=20000;a++)
{
for(b=0;b<465;b++)
{
math[a][b]=math[a][b]+math[a-1][b]+math[a-2][b];
math[a][b+1]=math[a][b+1]+math[a][b]/N;
math[a][b]=math[a][b]%N;
}
}
while(scanf("%d",&n)==1)
{
int flag=1;
for(a=464;a>=0;a--)
if(math[n][a]!=0||flag==0)
{
if(flag==1)
printf("%d",math[n][a]);
else
printf("%09d",math[n][a]);
flag=0;
}
printf("\n");
}
return 0;
}
/**********************************************************/
#include<stdio.h>#include<stdlib.h>
int math[20001][466]={0};
main()
{
int a,b,c,n;
int last[20001]={0};
math[0][0]=0;math[1][0]=1;
for(a=2;a<=20000;a++)
{
for(b=0;b<=last[a-1]+1;b++)
{
math[a][b]=math[a][b]+math[a-1][b]+math[a-2][b];
math[a][b+1]=math[a][b+1]+math[a][b]/1000000000;
math[a][b]=math[a][b]%1000000000;
}
for(b=last[a-1]+1;b>=0;b--)
if(math[a][b]!=0) {last[a]=b;break;}
}
while(scanf("%d",&n)==1)
{
printf("%d",math[n][last[n]]);
for(a=last[n]-1;a>=0;a--)
printf("%09d",math[n][a]);
printf("\n");
}
return 0;
}
可以問一下嗎?
為什麼是第2層迴圈是465?
還有最後輸出的%09d 是什麼意思阿?
465是因為最大的MAX次數，所以跑465是最保證一定不會錯的次數
因為F20000 會到達465*9位，一格存9位數，所以會跑那麼多...。
%09d 是不足9位補0 例如:x[5]=123好了 他只有3位
但是我要輸出9位 所以輸入會變成0,0000,0123 (輸出時不會有,)
想一想億進吧，假使我要123400089這個數字 但是我存在陣列之中
會變成(假使是一萬進...) 0089 2340 1 →89 2340 1
*************************************x[0] x[1] x[2]
因為我是用萬進，前面的0會被吃掉，所以要補0，
類推億進，了解回一聲唄...
為您補上新的程式碼 2009-07-09 17:47:53
謝謝你: )
你好厲害!!
我懂了~ 謝謝你喔~
不過你怎麼知道 F2000是465 * 9位阿>?