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

  1 #! /bin/bash
  2 #
  3 # 汉诺塔
  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 #  经过脚本原作者同意
 11 #+ 可以使用在"Advanced Bash Scripting Guide"中. 
 12 #  本书作者对此脚本做了少许修改. 
 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 #    (比较难)