Опубликовано Bash в Ср, 23/12/2009 — 21:04
Функции допускают выполнять рекурсивный вызов даже без использования локальных переменных.
Пример 22-13. Ханойские Башни
-
#! /bin/bash
-
#
-
# Ханойские Башни
-
# Bash script
-
# Copyright (C) 2000 Amit Singh. All Rights Reserved.
-
# <a href=»http://hanoi.kernelthread.com
-
#
-
#» title=»http://hanoi.kernelthread.com
-
#
-
#»>http://hanoi.kernelthread.com
-
#
-
#</a> Тестировался под bash 2.05b.0(13)-release
-
#
-
# Используется в «Advanced Bash Scripting Guide»
-
#+ с разрешения автора.
-
# С небольшими изменениями, внесенными автором документа.
-
#=================================================================#
-
# Ханойские Башни — это древняя математическая головоломка.
-
# Дается три вертикальных стержня.
-
# На первый нанизан набор колец.
-
# Эти кольца представляют собой плоские диски с дыркой по-середине,
-
#+ так что они могут свободно скользить по стержню.
-
# Кольца имеют различный диаметр, и изначально расположены на первом стержне
-
#+ в порядке убывания их диаметров.
-
# Наименьшее кольцо расположено сверху, наиболшее — внизу.
-
#
-
# Суть задачи заключается в том, чтобы перенести кольца с первого
-
#+ стержня на последний так, чтобы порядок следования колец не изменился.
-
# Кольца можно перемещать со стержня на стержень только по одному за раз.
-
# Можно помещать кольца обратно на тот же самый стержень.
-
# При перемещении нельзя класть больший диск на меньший.
-
#
-
# Для небольшого количества колец требутся некоторое количество перемещений.
-
#+ Каждое дополнительное кольцо
-
#+ увеличивает необходимое количество перемещений примерно в два раза,
-
#+ при этом «стратегия» перемещения усложняется все больше и больше.
-
#
-
# За дополнительной информацией обращайтесь на <a href=»http://hanoi.kernelthread.com.
-
#
-
#
-
#» title=»http://hanoi.kernelthread.com.
-
#
-
#
-
#»>http://hanoi.kernelthread.com.
-
#
-
#
-
#</a> … … …
-
# | | | | | |
-
# _|_|_ | | | |
-
# |_____| | | | |
-
# |_______| | | | |
-
# |_________| | | | |
-
# |___________| | | | |
-
# | | | | | |
-
# .—————————————————————.
-
# |**************************************************************|
-
# #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».
-
# (А вот это уже сложнее)
- Страница для печати
- 7129 просмотров