bash(awk递归)N阶【斐波那契数列】多种实现(含递归解析图)

【版权所有】转载请说明作者【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)
   递归-兔子数列.png

五、效率比较
   测试环境
   虚拟平台:VMware
   虚拟机系统:centos6.8
   虚拟机配置:CPU*2(宿主主机CPUI56300),内存1664MB
简单测试结果如下
     常规累加法
   递归-兔子数列1.png
     数组传递法
   递归-兔子数列2.png
     shell递归
   递归-兔子数列3.png
     awk优化递归
   递归-兔子数列4.png
   从这个简单的测试可以得出:
    从算法角度来说,直接累加运算效率最高,数组传递算法略逊些,由于递归比较耗资源,效益最低;
    从计算速度来讲awk计算高于bash计算;
注:递归计算时间资源消耗都随着阶数的变化呈指数性增长
    

     

【点击返回页首】

【版权所有】转载请说明作者【Jev Tes】

原创文章,作者:Jev Tse,如若转载,请注明出处:http://www.178linux.com/60651

(0)
Jev TseJev Tse
上一篇 2016-11-24
下一篇 2016-11-24

相关推荐

  • Linux下编译安装httpd

    本章学习内容         ———介绍httpd         ———-rpm和yum不同   &nbs…

    Linux干货 2016-08-25
  • linux基础知识

    基本命令,man自助使用手册,linux文件目录。

    Linux干货 2017-12-11
  • 细说CP使用

    cp详细用法和常用选项

    Linux干货 2017-11-26
  • 操作系统概述

                                 操作系统概述 对于一个真正的计算机系统来说,我们可以说它是由硬件+软件组成。没有软件的计算机,我们称它为裸机。当然,它也干不成什么事。所以,要想使得计算…

    Linux干货 2016-10-27
  • 浅谈筛选日志中的IP地址信息

    作为运维人员,经常会需要会对日志中的某些重要信息进行筛选,比如说ip等参数。 案例一:筛选出IP地址信息 日志信息如下: [root@C67-X64-A1 hanghang]# cat test.txt  Jul 13 08:13:09 localhost sshd[14678]…

    系统运维 2016-07-22
  • openvpn安装配置过程

    前言     之前为了方便远程办公时访问公司的内部系统,如:svn、OA、wiki、禅道等等;通通在防火墙上做了端口映射。然后有个内部系统被黑了,各种弱口令没办法。果断关闭端口映射,看来还是得搭建个VPN服务器,vpn设备感觉大材小用。马上就想到了开源的openvpn,下面就来介绍openvpn的安装配置过程。 ope…

    Linux干货 2015-05-11