Re: [問題] 費氏級數

[loveme00835 (高金素箍)]

※ 引述《wayne79 (wayne)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: c++
: 前面的include
: 到int main()
: 在下就省略了
: 以下是我寫的程式
: {
:    int z=0,a=0,b=1,c;
:    while(c!=500000)
:    {
:    a=b;
:    b=c;
:    c=a+b;
:    z++
:    }
:    cout<<endl<<"第"<<z<<"個數後會大於500000";
: system("pause");
: return 0;
: 題目:設計一個程式，找出費氏級數從第幾個數開始值會大於500000

假如你已經有費氏數列了:

      ╭──╮  ╭──╮  ╭──╮  ╭──╮  ╭──╮
數列: │  1 │  │  1 │  │  2 │  │  3 │  │  5 │
      ╰──╯  ╰──╯  ╰──╯  ╰──╯  ╰──╯

那麼在作加法的時候便是:

─────────────────────────────
Step 1.

     current_sum
     ╭───╮
     │   1  │
     ╰───╯
         ↑(加進去)
      ╭──╮  ╭──╮  ╭──╮  ╭──╮  ╭──╮
數列: │  1 │  │  1 │  │  2 │  │  3 │  │  5 │
      ╰──╯  ╰──╯  ╰──╯  ╰──╯  ╰──╯
─────────────────────────────
Step 2.

              current_sum
               ╭───╮
               │   2  │
               ╰───╯
                   ↑(加進去)
      ╭──╮  ╭──╮  ╭──╮  ╭──╮  ╭──╮
數列: │  1 │  │  1 │  │  2 │  │  3 │  │  5 │
      ╰──╯  ╰──╯  ╰──╯  ╰──╯  ╰──╯
─────────────────────────────
Step 3.

                        current_sum
                         ╭───╮
                         │   4  │
                         ╰───╯
                             ↑加進去
      ╭──╮  ╭──╮  ╭──╮  ╭──╮  ╭──╮
數列: │  1 │  │  1 │  │  2 │  │  3 │  │  5 │
      ╰──╯  ╰──╯  ╰──╯  ╰──╯  ╰──╯
─────────────────────────────

迴圈長相是這樣:

   unsigned i = 0; // 項次
   unsigned current_sum = 0;

   while( current_sum <= 500000 )
   {
      current_sum += fibonacci( i );
      i += 1;
   }

當然這個 fibonacci() 還沒定義, 最陽春的實作可以是這樣:

   unsigned fibonacci( unsigned i )
   {
      unsigned previous_term = 0,
               current_term = 1; 

      for( unsigned cnt = 1; cnt <= i; ++cnt )
      {
         unsigned shift_space = current_term;

         current_term += previous_term;

         previous_term = shift_space;
      }

      return current_term;
   }

這樣就可以比較專注在更高層面的演算法, 而不用擔心語言細節
, 為了加速也可以把程式碼作合併:

   unsigned i = 0; // 項次
   unsigned current_sum = 0;
   unsigned previous_term = 0,
            current_term = 1; 


   while( current_sum <= 500000 )
   {
      current_sum += current_term;
      i += 1;

      unsigned shift_space = current_term;

      current_term += previous_term;

      previous_term = shift_space;
   }


按部就班來, 我想不到會出問題的點在哪...

--
   ★    ★                                                          ★    ★
 ★   ★   ★  ███  ███  █  █▌█  ██◣  ███  ▋▋█  ★   ★   ★
               █▂█  █▃█  █  ███  █▆█  █▄█  ███
   ★    ★    █  ◣  █  █  █  ▋██  █▆◤  ███  ███    ★    ★
 Kim Jae Kyung  Koh Woo Ri  Cho Hyun Young Kim Ji Sook
φwindyhorse                                  No Eul  Oh Seung A  Jung Yoon Hye

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.121.197.115
推 ericinttu:有畫圖先推
※ 編輯: loveme00835     來自: 140.121.197.115      (07/29 17:43)
推 adxis:版主揪甘心
推 tropical72:  ~ 有圖有真相 ~ 版主揪甘心 ~
推 xatier:版主推一個！