Заработай на задачках

Оригинальный текст: Working with Functions: Towers of Hanoi by Dave Taylor

Перевод: собственный, вольный с исправлениями.

В этой статье я бы хотел вернуться к основам создания shell-скриптов и рассмотреть работу с функциями. Многие не пользуются ими при написании простых сценариев, так как скрипты часто представляют собой обычную последовательность команд, заключённую в исполняемый файл.

Однако если одни и те же строчки повторяются в программе несколько раз, то использование функций приобретает смысл. Согласно философии структурного программирования, так можно значительно упростить процесс создания и сопровождения сценария.

Синтаксис объявления функции в bash-скрипте выглядит следующим образом:

ИмяФункции{ список команд для исполнения }

Вызвать функцию можно в главном цикле программы или другой функции по имени:

echo "До вызова" ИмяФункции echo "После вызова"

Обращение к передаваемым аргументам происходит так же, как и к аргументам командной строки в основном коде программы: $1, $2, $3 и т.д. Это значит, что в теле функции я бы мог написать:

if [ -n "$1 " ] ; then echo "В функцию было передано $1 в качестве первого аргумента." fi

Узнать число аргументов, переданных в функцию, можно с помощью переменной $#. Тогда предыдущий пример примет вид:

if [ $# -gt 0 ] ; then echo "В функцию было передано $# аргументов." fi

Главное ограничение, которое возникает при использовании функций в shell-скриптах – они могут возвращать только целое число от 0 до 127. При этом, обычно на практике используются только два значения: 0 – при возникновении ошибок и 1 – при удачном завершении. Многие при написании сценариев полностью отказываются от возвращаемого значения и применяют глобальные переменные. Так можно получать из функции даже строки, чего нельзя сделать стандартным способом.

В таких мощных языках как С++, Ruby или Java использовать глобальные переменные в функциях – пример плохого стиля программирования. Однако в этом случае нет другого выхода.

Ханойская башня

Чтобы сделать эту заметку интересней, я рассмотрю работу функций в shell-скриптах на примере классической задачи, которая решается с помощью рекурсии. Программа будет называться ханойская башня и вы наверняка сталкивались с похожими детскими игрушками.

Существует набор дисков разного диаметра и три штырька. Цель – переместить все диски с одного крайней шпильки на другой, при этом нельзя положить больший диск на меньший. Если пронумеровать штырьки как 0, 1, и 2, то простейший способ решить эту задачу с одним диском – переложить его с 0 на 2. Если рассматривать вариант с двумя дисками, то необходимо переложить меньший с 0 на 1, затем диск большего диаметра с 0 на 2, и закончить ходом с 1 на 2.

Алгоритм для N дисков можно выразить с помощью простого shell-сценария:

#!/bin/sh read –ep "Ханойская башня. Сколько в ней дисков? " disks for (( x=1; x < ( 1 << $disks ); x++ )) ; do i=$((($x & $x - 1 ) % 3)) j=$(((($x | $x - 1 ) + 1 ) % 3)) echo "Перемещение с башни $i на $j" done

После запуска исполняемого файла будет показано пошаговое решение:

Ханойская башня - итеративная функция

Получается, что решение для N дисков состоит из 2^N – 1 шаг. Для 20 дисков потребуется 1_048_577 перемещений.

Рекурсия в функциях shell-скриптов в Linux

Смысл предыдущего примера – познакомить с постановкой задачи и показать, насколько элегантно она может решаться с помощью рекурсии.

Основной алгоритм работы программы состоит из трёх шагов:

  1. Перемещаем верхние диски с исходной позиции на временную.
  2. Перемещаем самый большой диск с исходной позиции на целевую.
  3. Перемещаем верхние диски с временной позиции на исходную.

В интернете можно найти много наглядных примеров, которые бы демонстрировали принцип работы этого алгоритма. Посмотрим же на мою реализацию:

#!/bin/sh moves=0 hanoi(){ if [ $1 -gt 0 ] ; then hanoi "$(($1 - 1))" $2 $4 $3 echo “Перемещение $2 --\> $3” moves=$(($moves + 1)) hanoi "$(($1 - 1))" $4 $3 $2 fi } read –ep "Ханойская башня. Сколько в ней дисков? " disks hanoi $disks 1 2 3 echo "Для решения потребовалось $moves перемещений."

Для начала работы рекурсивной функции необходимо передать четыре аргумента:

hanoi $disks 1 2 3

Это количество дисков и обозначения шпилек, которые будут использоваться. Результат выполнения скрипта для 4 дисков и трёх пронумерованных башен:

Рекурсия в Bash

Понадобилось 15 шагов для решения задачи. Кроме того, для запуска рекурсивной функции можно использовать строки для именования позиций:

hanoi $disks "Исходная" "Временная" "Целевая"

Это сделает немного понятней процесс исполнения скрипта. Пример для трёх дисков:

Рекурсия в Bash. Пример 2.

Конечно, вам может никогда не потребоваться на практике использовать рекурсию в своих скриптах. Обычные функции часто эффективней и легче для понимания, но всегда стоит рассматривать и рекурсивный вариант решения задачи.

Я буду очень рад комментарию!

Не переживайте, e-mail нигде не отображается. Обязательные поля помечены *

Навигация по записям