【版权所有】转载请说明作者【Jev Tes】
【本文导航】
零、关于斐波那契数列
一、输入参数合法性判断
二、TYP 1:常规累加法
三、TYP 2:数组传递法
四、TYP 3:递归法
1、shell递归
2、awk优化递归
五、效率比较
零、关于斐波那契数列
斐波那契数列又称黄金分割数列,因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列: 0、 1、 1、 2、 3、 5、 8、 13、 21、 34、 ……,这个数列从第3项开始,每一项都等于前两项之和。
斐波纳契数列以如下被以递归的方法定义: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)( n≥2)
编写脚本/函数时,对输入参数合法性的判断非常重要,可以规避很多不必要的麻烦,特别是调试递归函数时!
#--------------------------------输入参数合法性判断-------------------------------- if ! echo $1 | egrep "^[0-9]+$" &> /dev/null ; #如果输入不是0或正整数,执行下面语句 then echo "-Fib 119:error token is \""$1"\"!" #回显错误信息 exit 110 #退出脚本 fi #------------------------------------------------------------------------------
二、TYP 1:常规累加法
整体思路:从第3阶开始计算F3=F2+F1=1+1=2、F4=F3+F2=2+1=3…依次计算到第N阶;
主体代码跟分析如下:
#--------------------------------累加算法-------------------------------- fib() #定义函数 { local i=2 #本地变量,做计数用 local Fib0=0 #本地变量,记录传递F(n-2)的值,初始值为F0的值 local Fib1=1 #本地变量,记录传递F(n-1)的值,初始值为F1的值 local $Fibn #本地变量,记录传递F(n)的值 [ $1 -eq 0 ] && echo "F(0)=0" && return 0 #如果$1值为0,直接回显F(0)=0,退出函数 [ $1 -eq 1 ] && echo "F(1)=1" && return 1 #如果$1值为1,直接回显F(1)=1,退出函数 until [ $i -gt $1 ] ; do #当$i大于$1(计算阶数)时,退出循环 Fibn=$[Fib1+Fib0] #Fn=F(n-1) +F(n-2),n为此时$i的值 Fib0=$Fib1 #将当前F(n-1)的值,即为下轮F(n-2)的值 Fib1=$Fibn #将当前F(n)的值,即为下轮F(n-1)的值 i=$[i+1] #对$i进行累加1 done echo "F("$1")=$Fibn" #退出循环后,输出Fn的值 } fib $1 #引用函数
三、TYP 2:数组传递法
整体思路:跟常规累加传递法类似,从第3阶开始计算,依次计算到第N阶,但这方法奇妙在于用数组来储存整个数列,可以将整个数列完整保存下来;
主体代码跟分析如下:
#--------------------------------数组传递法-------------------------------- fib() #定义函数 { declare -a Fib #定义数组Fib Fib[0]=0 #赋值F0=0 Fib[1]=1 #赋值F1=1 Fib[2]=1 #赋值F1=1 case $1 in 0) echo ${Fib[0]} #如果$1值为0,直接回显F(0)=0 ;; 1) echo ${Fib[1]} #如果$1值为0,直接回显F(0)=0 ;; *) for i in `seq 2 $1`;do #$i在2-$1时进行循环 Fib[$i]=$[${Fib[$i-1]}+${Fib[$i-2]}] #Fib[$i]的值为前两项的值之和 done echo ${Fib[$1]} #退出循环后,输出Fn的值 ;; esac } fib $1 #引用函数
四、TYP 3:递归法
整体思路:跟以上俩种思路相反,函数从N阶开始,依次向下递归展开,直到$1=1,$1=0,时停止递归,并将值回传给父函数;
主体代码跟分析如下:
1、shell递归
#-------------------------------shell递归--------------------------------- Fib() #定义函数 { if [ $1 -eq 0 ] ; then echo 0 #当$1值为0,回显0 elif [ $1 -eq 1 ] ;then echo 1 #当$1值为0,回显1 else echo $[$(Fib $[$1-1])+$(Fib $[$1-2])] #递归展开Fn=F(n-1)+F(n-2)直到$[$1-1]=1,$[$1-2]=0,递归终止fi} Fib $1 #引用函数
2、awk优化递归
#--------------------------------awk递归算法-------------------------------- awk -v i=$1 'function Fib(i){ if(i==0){ return 0} #当$i值为0,返回0 else if(i==1){return 1} #当$i值为0,返回0 else{return Fib(i-1)+Fib(i-2)} #展开递归,计算Fib(i-1)+Fib(i-2)的值 }BEGIN{ print Fib(i)}'
简单递归思路解析:(以4阶为例,即$1=4)
F4=F3+F2
=(F2+F1)+(F1+F0)
=[(F1+F0)+F1]+(F1+F0)
=3F1+2F0
=3
递归解析图如下:(以4阶为例,即$1=4)
五、效率比较
测试环境
虚拟平台:VMware
虚拟机系统:centos6.8
虚拟机配置:CPU*2(宿主主机CPUI56300),内存1664MB
简单测试结果如下:
常规累加法
数组传递法
shell递归
awk优化递归
从这个简单的测试可以得出:
从算法角度来说,直接累加运算效率最高,数组传递算法略逊些,由于递归比较耗资源,效益最低;
从计算速度来讲awk计算高于bash计算;
注:递归计算时间与资源消耗都随着阶数的变化呈指数性增长
【版权所有】转载请说明作者【Jev Tes】
原创文章,作者:Jev Tse,如若转载,请注明出处:http://www.178linux.com/60651