23.3. 不使用局部变量的递归

   1 #! /bin/bash
   2 #
   3 # 汉诺塔(The Towers Of Hanoi)
   4 # Bash script
   5 # Copyright (C) 2000 Amit Singh. All Rights Reserved.
   6 # http://hanoi.kernelthread.com
   7 #
   8 # 在bash version 2.05b.0(13)-release下测试通过
   9 #
  10 #  经过作者同意后在"Advanced Bash Scripting Guide"书中使用
  11 #
  12 #  由ABS的作者做了少许修改.
  13 
  14 #=================================================================#
  15 #  汉诺塔是由Edouard Lucas提出的数学谜题 ,
  16 #+ 他是19世纪的法国数学家.
  17 #
  18 #  有三个直立的柱子竖在地面上.
  19 #  第一个柱子有一组的盘子套在上面.
  20 #  这些盘子是平整的，中间带着孔，
  21 #+ 因此它们才能套在柱子上面.
  22 #  这组盘子有不同的直径，它们是依照直径从小到大来从高到低放置.
  23 #
  24 #  最小的盘在最高，最大的盘在最底部.
  25 #
  26 #  现在的任务是要把这一组的盘子从一个柱子全部地搬到另一个柱子上.
  27 #
  28 #  你只能一次从一个柱子上移动一个盘子到另一个柱子.
  29 #  允许把盘子重新移回到它原来的最初位置.
  30 #  你可以把一个小的盘子放在大的盘子上面,
  31 #+ 但不能把大的盘子放在小的盘子上面.
  32 #  请注意这一点.
  33 #
  34 #  对于这一组盘子，数量少时，只需要移动很少的次数就能达到要求.
  35 #+ 但随着这组盘子的数量的增加,
  36 #+ 移动的次数几乎成倍增长的,
  37 #+ 而移动的策略变得愈加复杂.
  38 #
  39 #  想了解更多的信息, 请访问 http://hanoi.kernelthread.com.
  40 #
  41 #
  42 #         ...                   ...                    ...
  43 #         | |                   | |                    | |
  44 #        _|_|_                  | |                    | |
  45 #       |_____|                 | |                    | |
  46 #      |_______|                | |                    | |
  47 #     |_________|               | |                    | |
  48 #    |___________|              | |                    | |
  49 #   |             |             | |                    | |
  50 # .--------------------------------------------------------------.
  51 # |**************************************************************|
  52 #          #1                   #2                      #3
  53 #
  54 #=================================================================#
  55 
  56 
  57 E_NOPARAM=66  # 没有参数传给脚本.
  58 E_BADPARAM=67 # 传给脚本的盘子数不合法.
  59 Moves=        # 保存移动次数的全局变量.
  60               # 这儿修改了原脚本.
  61 
  62 dohanoi() {   # 递归函数.
  63     case $1 in
  64     0)
  65         ;;
  66     *)
  67         dohanoi "$(($1-1))" $2 $4 $3
  68         echo move $2 "-->" $3
  69 	let "Moves += 1"  # 这儿修改了原脚本.
  70         dohanoi "$(($1-1))" $4 $3 $2
  71         ;;
  72     esac
  73 }
  74 
  75 case $# in
  76 1)
  77     case $(($1>0)) in     # 至少要有一个盘子.
  78     1)
  79         dohanoi $1 1 3 2
  80         echo "Total moves = $Moves"
  81         exit 0;
  82         ;;
  83     *)
  84         echo "$0: illegal value for number of disks";
  85         exit $E_BADPARAM;
  86         ;;
  87     esac
  88     ;;
  89 *)
  90     echo "usage: $0 N"
  91     echo "       Where \"N\" is the number of disks."
  92     exit $E_NOPARAM;
  93     ;;
  94 esac
  95 
  96 # 练习:
  97 # ---------
  98 # 1) 从现在这个位置以下的命令会不会总是被执行?
  99 #    为什么? (容易)
 100 # 2) 解释这个可运行的"dohanoi"函数的原理.
 101 #    (难)