Re: [心得] 用 bash 算費氏數列，就當了

[rickieyang (Rickie Yang)]

※ 引述《Gold740716 (項為之強)》之銘言：
: febo(){
:         i=$1
:         (( j = i-1 , k = i-2 ))
:
:         if (( i <= 1 ))
:         then
:                 echo 1
:         else
:                 echo $(expr `febo $j` + `febo $k` )
:         fi
: }
:
:
: 邏輯問題是 febo 1 和 febo 0 都回傳 1 ，
: 所以 febo 2 = 2 ，也就是我第 0 項變成 1 ；而不是 0 。
: 我想知道 fork 炸彈在哪，小弟功力不足。
:
: -------------------------------
:   x     | 0  1  2  3  4  5  6
: --------+----------------------
: febo x  | 1  1  2  3  5  8 13
: -------------------------------
:

都已經知道了, 所以就不要偷懶, 讓 0 echo 0 不就好了?

febo(){
       i=$1
        (( j = i-1 , k = i-2 ))

        if [ $i -eq 0 ]
        then
                echo 0
        elif [ $i -eq 1 ]
        then
                echo 1
        else
                echo $(expr `febo $j` + `febo $k`)
        fi
}

然後你可以算一下, 每呼叫一次,
0 & 1 會呼叫 echo
 >1 時會呼叫 echo 跟 expr 各一次.

小弟個人不喜歡用 bash 專有的 (( )) 跟 $() 來寫 script.
不知道(()) 跟 $() 會不會 fork 子程序?

50 會呼叫 49/48, 49 會呼叫 48/47
也就是  50 第 1 次被呼叫,接著
        49 會被呼叫 1 次
        48 被呼叫 2 次 (50 跟 49)
        47 被呼叫 3 次 (49 跟 48)
        46 被呼叫 5 次 (48 跟 47)
        45 被呼叫 8 次 (47 跟 46)
依此類推. 總共會被呼叫... 剛好跟費式數列一樣的次數 (之前的推文算錯了...)
而這些程序在數列算完之前都不會結束 (遞迴的特性), 所以要累加起來.

0 & 1 共有 32,951,280,099 次
 >1 的共有 20,365,011,073 次
總共會 fork 出 73,681,302,245 個子程序

所以, 你現在可以原諒系統當掉了嗎?

還是用一般迴圈來算吧.

fibo[0]=0
fibo[1]=1
i=2
while [ $i -le $1 ]
do
        fibo[$i]=`expr ${fibo[$i-1]} + ${fibo[$i-2]}`
        i=`expr $i + 1`
done
echo ${fibo[$1]}

不過費式不拿來練習遞迴, 光算出值好像沒啥用...
而且超過 92 位, expr 就 overflow 了... 哈哈

Rickie MBPr:0 rickie$ time ./go.sh 92
7540113804746346429

real    0m0.386s
user    0m0.155s
sys     0m0.221s

Rickie MBPr:0 rickie$ time ./go.sh 93
expr: overflow


real    0m0.415s
user    0m0.163s
sys     0m0.241s

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.222.17.107
※ 文章網址: https://www.ptt.cc/bbs/Linux/M.1461511078.A.073.html
→ rickieyang: 其實我也不確定 (( )) 跟 $() 是不是只有 bash 能用?
※ 編輯: rickieyang (203.222.17.107), 04/25/2016 00:03:27
推 hijkxyzuw: 我翻了 log 只算到 9……
推 hijkxyzuw: 用ulimit 玩, 到 15 就不想等了
→ rickieyang: 樓上原 po 忘了換帳號?
→ rickieyang: 15 就要 fork 三千多次了...
→ HamalAri: 遞迴的話，bash 20   C 45 都是 30 秒內出的來
推 Gold740716: 忘了換帳號  冏
→ lantw44: (( )) 是 bash 語法，$() 是標準 shell 的語法
→ lantw44: 標準 shell 也沒有支援陣列
→ lantw44: 其實不一定要用 (( )) 或 expr，有 $(( )) 可以用
→ lantw44: 剛才測試 ksh 和 zsh 好像也有支援 (( )) 和 陣列