Re: [問題] 費氏級數

看板C_and_CPP (C/C++)作者loveme00835 (高金素箍)時間14年前 (2011/07/29 17:38)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串2/2 (看更多)

※ 引述《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