Функции допускают выполнять рекурсивный вызов даже без использования локальных переменных.
#! /bin/bash
#
# Ханойские Башни
# Bash script
# Copyright (C) 2000 Amit Singh. All Rights Reserved.
# http://hanoi.kernelthread.com
#
# Тестировался под bash 2.05b.0(13)-release
#
# Используется в "Advanced Bash Scripting Guide"
#+ с разрешения автора.
# С небольшими изменениями, внесенными автором документа.
#=================================================================#
# Ханойские Башни -- это древняя математическая головоломка.
# Дается три вертикальных стержня.
# На первый нанизан набор колец.
# Эти кольца представляют собой плоские диски с дыркой по-середине,
#+ так что они могут свободно скользить по стержню.
# Кольца имеют различный диаметр, и изначально расположены на первом стержне
#+ в порядке убывания их диаметров.
# Наименьшее кольцо расположено сверху, наиболшее -- внизу.
#
# Суть задачи заключается в том, чтобы перенести кольца с первого
#+ стержня на последний так, чтобы порядок следования колец не изменился.
# Кольца можно перемещать со стержня на стержень только по одному за раз.
# Можно помещать кольца обратно на тот же самый стержень.
# При перемещении нельзя класть больший диск на меньший.
#
# Для небольшого количества колец требутся некоторое количество перемещений.
#+ Каждое дополнительное кольцо
#+ увеличивает необходимое количество перемещений примерно в два раза,
#+ при этом "стратегия" перемещения усложняется все больше и больше.
#
# За дополнительной информацией обращайтесь на http://hanoi.kernelthread.com.
#
#
# ... ... ...
# | | | | | |
# _|_|_ | | | |
# |_____| | | | |
# |_______| | | | |
# |_________| | | | |
# |___________| | | | |
# | | | | | |
# .--------------------------------------------------------------.
# |**************************************************************|
# #1 #2 #3
#
#=================================================================#
E_NOPARAM=66 # Сценарий запущен без параметров.
E_BADPARAM=67 # Неверное число колец.
Moves= # Глобальная переменная, хранит число перемещений.
# Добавлено в оригинальный сценарий.
dohanoi() { # Рекурсивная функция.
case $1 in
0)
;;
*)
dohanoi "$(($1-1))" $2 $4 $3
echo move $2 "-->" $3
let "Moves += 1" # Добавлено в оригинальный сценарий.
dohanoi "$(($1-1))" $4 $3 $2
;;
esac
}
case $# in
1)
case $(($1>0)) in # Как минимум должен быть хотя бы один диск.
1)
dohanoi $1 1 3 2
echo "Всего перемещений = $Moves"
exit 0;
;;
*)
echo "$0: Неверное число колец";
exit $E_BADPARAM;
;;
esac
;;
*)
echo "Порядок использования: $0 N"
echo " Где \"N\" -- это число колец."
exit $E_NOPARAM;
;;
esac
# Упражнения:
# ---------
# 1) Будут ли исполнены дополнительные команды, если разместить их ниже этой строки?
# Почему нет? (Это так просто!)
# 2) Объясните -- как работает функция "dohanoi".
# (А вот это уже сложнее)