24h購物| | PChome| 登入
2009-05-17 07:01:25| 人氣595| 回應5 | 上一篇 | 下一篇

挑戰極限 Part1 - 極限加法

推薦 0 收藏 0 轉貼0 訂閱站台

作法:十億進制

此題由本人出題,因為太少人想到這個!

進階加速:(第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;     
}

我要檢舉
#網路情報#挑戰極限
台長： 來源不明

您可能對以下文章有興趣

人氣(595) | 回應(5)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: | 個人分類: ZeroJudge 基礎+原創題庫 |
此分類下一篇:漂亮數碼
此分類上一篇:矩形對角線

我要回應
terry
可以請問一個問題嗎~

關於這題

(以下是我的程式碼)

#include <iostream>
#include <iomanip>
#define MAX 6000

using namespace std;

int list[20001][(MAX-1)/9+1]; // 為何一定要在這邊作全域宣告...? 在 main區塊內宣告卻會得到 RE (SIGSEGV)

int main()
{
int n, i, j;

// 建表 TODO
int nums[(MAX-1)/9+1], temp[(MAX-1)/9+1], temp2[(MAX-1)/9+1];
// init Arrays to zero
for(i = 0; i < (MAX-1)/9+1; i++)
nums[i] = 0, temp[i] = 0, temp2[i] = 0;
temp[(MAX-1)/9] = 0, temp2[(MAX-1)/9] = 1;
// 計算
for(i = 2; i < 20001; i++) {
for(j = (MAX-1)/9; j >= 0; j--) {
nums[j] = temp[j] + temp2[j];
temp[j] = temp2[j];
temp2[j] = nums[j];
}
// 進位 每一元素存放9位數
for(j = (MAX-1)/9; j >= 0; j--) {
if (temp[j] / 1000000000 != 0 && j-1 >= 0) {
temp[j-1] += temp[j]/1000000000;
temp[j] %= 1000000000;
}
if (temp2[j] / 1000000000 != 0 && j-1 >= 0) {
temp2[j-1] += temp2[j]/1000000000;
temp2[j] %= 1000000000;
}
if (nums[j] / 1000000000 != 0 && j-1 >= 0) {
nums[j-1] += nums[j]/1000000000;
nums[j] %= 1000000000;
}
}
// save
for(j = 0; j < (MAX-1)/9+1; j++)
list[i][j] = nums[j];
}
while(cin >> n) {
if (n <= 1) {
cout << n << endl;
continue;
}
// show
for(i = 0; i < (MAX-1)/9+1; i++) {
if (list[n][i] > 0) {
cout << list[n][i];
break;
}
}
for(j = i+1; j < (MAX-1)/9+1; j++) {
if (list[n][j] > 0)
cout << setw(9) << setfill(’0’) << list[n][j];
}
cout << endl;
}
return 0;
}
2009-05-22 14:22:48
版主回應
區域變數內的陣列
舉例int的型態的話 只能開到50萬格
全區變數 只要你家的記憶體夠大 開多大都可以
在ZERO 全區變數 int 可以開到1000萬左右　char 可以開到6000萬
2009-05-23 17:34:04
terry
不好意思 空格都被留言系統消除了0.0

沒縮行的程式碼看起來一定很暈
2009-05-22 14:24:02
terry0412
謝謝你: )

你好厲害!!
2009-05-24 00:51:07
xx
可以問一下嗎?

為什麼是第2層迴圈是465?

還有最後輸出的%09d 是什麼意思阿?
2009-07-09 10:53:21
版主回應
耶 過了好久終於有人留言了....先不談這個
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
xx
我懂了~ 謝謝你喔~


不過你怎麼知道 F2000是465 * 9位阿>?
2009-07-10 11:27:58
版主回應
當然是瘋狂的測試...
2009-07-10 18:22:19
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文