linux - 使用 Bash 迭代计算斐波那契数

Question

是否可以编写一个脚本来计算第 n 个斐波那契数 - 迭代。我做了递归（如下所示），但可以迭代地找到解决方案。请帮忙。

#!/bin/bash
fib()
{
  if [ $1 -le 0 ]
  then
    echo 0
    return 0
  fi
  if [ $1 -le 2 ]
  then
    echo 1
  else
    a=$(fib $[$1-1])
    b=$(fib $[$1-2])
    echo $(($a+$b))
  fi
}

标签： linuxbashalgorithmshell

Answer 1

这是迭代方法：

function fib() {
  local n=$1
  local x=0
  local prev1=0
  local prev2=0
  local cur=0
  for (( x = 1 ; x <= n ; x++ ))
  do
    if [[ $x == 1 || $x == 2 ]] ;  then
      prev1=1
      prev2=1
      cur=1
      continue
    fi
    cur=$(( prev1 + prev2 ))
    prev2=$prev1
    prev1=$cur
  done
  echo $cur
}