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

相关推荐

  • TCP常见问题总结

    TCP协议和UDP协议的区别是什么 TCP协议是有连接的,有连接的意思是开始传输实际数据之前TCP的客户端和服务器端必须通过三次握手建立连接,会话结束之后也要结束连接。而UDP是无连接的 TCP协议保证数据按序发送,按序到达,提供超时重传来保证可靠性,但是UDP不保证按序到达,甚至不保证到达,只是努力交付,即便是按序发送的序列,也不保证按序送到。 TCP协议…

    Linux干货 2017-09-02
  • CentOS6.9系统上编译安装httpd.2.2.32

    本文所做的所有操作是在一部新安装的CentOS6.9系统上。 1.环境与配置 环境说明:VMware上安装的CentOS6.9系统,两张系统盘做成的yum源 配置:编译生成的所有的文件都存放在/usr/local/httpd22/这个目录下 2.安装GCC编译器 [root@localhost ~]# yum grouplist | grep “Develo…

    2017-04-20
  • Linux的自动化安装实现

    在介绍自动化安装系统之前让我们来回顾一下系统的启动流程,系统的启动大概分为一下几个步骤:加电自检 boot sequence(mbr)— boot loader –>kernel(initramfs)—>rootfs  /sbin/init大概就是这么几个过程了,接下来来介绍系统的安装,安装系统虽然看起来简单,普…

    系统运维 2016-09-19
  • centos启动流程

    linux系统启动流程 内核的设计结构单内核:linux(线程–lwp轻量级进程)微内核:windows(支持真正意义上的多线程) 单内核:很多功能驱动都集成在一起 微内核:内核很小,功能单一。模块化 linux为了适应众多用户的不同硬件需求,linux内核在设计上采用模块化设计。可以动态加载模块。核心模块:ko 内核所独有的。共享对象:so 红…

    Linux干货 2016-09-09
  • grep和正则表达式

    grep       作用:文本搜索工具,根据用户指定的“模式(过滤条件)”对目标文件逐行进行匹配检查;打印匹配到的行;       模式:由正则表达式的元字符及文本所编写出的过滤条件    语法:【选项】【文件】  &…

    2017-08-04