Мендель Купер - Искусство программирования на языке сценариев командной оболочки

#!/bin/bash

# sieve.sh

# Решето Эратосфена

# Очень старый алгоритм поиска простых чисел.

# Этот сценарий выполняется во много раз медленнее

# чем аналогичная программа на C.

LOWER_LIMIT=1 # Начиная с 1.

UPPER_LIMIT=1000 # До 1000.

# (Вы можете установить верхний предел и выше... если вам есть чем себя занять.)

PRIME=1

NON_PRIME=0

declare -a Primes

# Primes[] -- массив.

initialize ()

{

# Инициализация массива.

i=$LOWER_LIMIT

until [ "$i" -gt "$UPPER_LIMIT" ]

do

Primes[i]=$PRIME

let "i += 1"

done

# Все числа в заданном диапазоне считать простыми,

# пока не доказано обратное.

}

print_primes ()

{

# Вывод индексов элементов массива Primes[], которые признаны простыми.

i=$LOWER_LIMIT

until [ "$i" -gt "$UPPER_LIMIT" ]

do

if [ "${Primes[i]}" -eq "$PRIME" ]

then

printf "%8d" $i

# 8 пробелов перед числом придают удобочитаемый табличный вывод на экран.

fi

let "i += 1"

done

}

sift () # Отсеивание составных чисел.

{

let i=$LOWER_LIMIT+1

# Нам известно, что 1 -- это простое число, поэтому начнем с 2.

until [ "$i" -gt "$UPPER_LIMIT" ]

do

if [ "${Primes[i]}" -eq "$PRIME" ]

# Не следует проверять вторично числа, которые уже признаны составными.

then

t=$i

while [ "$t" -le "$UPPER_LIMIT" ]

do

let "t += $i "

Primes[t]=$NON_PRIME

# Все числа, которые делятся на $t без остатка, пометить как составные.

done

fi

let "i += 1"

done

}

# Вызов функций.

initialize

sift

print_primes

# Это называется структурным программированием.

echo

exit 0

# ----------------------------------------------- #

# Код, приведенный ниже, не исполняется из-за команды exit, стоящей выше.

# Улучшенная версия, предложенная Stephane Chazelas,

# работает несколько быстрее.

# Должен вызываться с аргументом командной строки, определяющем верхний предел.

UPPER_LIMIT=$1 # Из командной строки.

let SPLIT=UPPER_LIMIT/2 # Рассматривать делители только до середины диапазона.

Primes=( '' $(seq $UPPER_LIMIT) )

i=1

until (( ( i += 1 ) > SPLIT )) # Числа из верхней половины диапазона могут не рассматриваться.

do

if [[ -n $Primes[i] ]]

then

t=$i

until (( ( t += i ) > UPPER_LIMIT ))

do

Primes[t]=

done

fi

done

echo ${Primes[*]}

exit 0

Сравните этот сценарий с генератором простых чисел, не использующим массивов, Пример A-18.

--

Массивы позволяют эмулировать некоторые структуры данных, поддержка которых в Bash не предусмотрена.

#!/bin/bash

# stack.sh: Эмуляция структуры "СТЕК" ("первый вошел -- последний вышел")

# Подобно стеку процессора, этот "стек" сохраняет и возвращает данные по принципу

#+ "первый вошел -- последний вышел".

BP=100 # Базовый указатель на массив-стек.

# Дно стека -- 100-й элемент.

SP=$BP # Указатель вершины стека.

# Изначально -- стек пуст.

Data= # Содержимое вершины стека.

# Следует использовать дополнительную переменную,

#+ из-за ограничений на диапазон возвращаемых функциями значений.

declare -a stack

push() # Поместить элемент на вершину стека.

{

if [ -z "$1" ] # А вообще, есть что помещать на стек?

then

return

fi

let "SP -= 1" # Переместить указатель стека.

stack[$SP]=$1

return

}

pop() # Снять элемент с вершины стека.

{

Data= # Очистить переменную.

if [ "$SP" -eq "$BP" ] # Стек пуст?

then

return

fi # Это предохраняет от выхода SP за границу стека -- 100,

Data=${stack[$SP]}

let "SP += 1" # Переместить указатель стека.

return

}

status_report() # Вывод вспомогательной информации.

{

echo "-------------------------------------"

echo "ОТЧЕТ"

echo "Указатель стека SP = $SP"

echo "Со стека был снят элемент \""$Data"\""

echo "-------------------------------------"

echo

}

# =======================================================

# А теперь позабавимся.

echo

# Попробуем вытолкнуть что-нибудь из пустого стека.

pop

status_report

echo

push garbage

pop

status_report # Втолкнуть garbage, вытолкнуть garbage.

value1=23; push $value1

value2=skidoo; push $value2

value3=FINAL; push $value3

pop # FINAL

status_report

pop # skidoo

status_report

pop # 23

status_report # Первый вошел -- последний вышел!

# Обратите внимание как изменяется указатель стека на каждом вызове функций push и pop.

echo

# =======================================================

# Упражнения:

# -----------

# 1) Измените функцию "push()" таким образом,

# + чтобы она позволяла помещать на стек несколько значений за один вызов.

# 2) Измените функцию "pop()" таким образом,

# + чтобы она позволяла снимать со стека несколько значений за один вызов.

# 3) Попробуйте написать простейший калькулятор, выполняющий 4 арифметических действия?

# + используя этот пример.

exit 0

--

Иногда, манипуляции с "индексами" массивов могут потребовать введения переменных для хранения промежуточных результатов. В таких случаях вам предоставляется лишний повод подумать о реализации проекта на более мощном языке программирования, например Perl или C.

#!/bin/bash

# Пресловутая "Q-последовательность" Дугласа Хольфштадтера *Douglas Hofstadter):

# Q(1) = Q(2) = 1

# Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), для n>2

# Это "хаотическая" последовательность целых чисел с непредсказуемым поведением.

# Первые 20 членов последовательности:

# 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12

# См. книгу Дугласа Хольфштадтера, "Goedel, Escher, Bach: An Eternal Golden Braid",

# p. 137, ff.

LIMIT=100 # Найти первые 100 членов последовательности

LINEWIDTH=20 # Число членов последовательности, выводимых на экран в одной строке

Q[1]=1 # Первые два члена последовательности равны 1.

Q[2]=1

echo

echo "Q-последовательность [первые $LIMIT членов]:"

echo -n "${Q[1]} " # Вывести первые два члена последовательности.

echo -n "${Q[2]} "

for ((n=3; n <= $LIMIT; n++)) # C-подобное оформление цикла.

do # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]] для n>2

# Это выражение необходимо разбить на отдельные действия,

# поскольку Bash не очень хорошо поддерживает сложные арифметические действия над элементами массивов.

let "n1 = $n - 1" # n-1

let "n2 = $n - 2" # n-2

t0=`expr $n - ${Q[n1]}` # n - Q[n-1]

t1=`expr $n - ${Q[n2]}` # n - Q[n-2]

T0=${Q[t0]} # Q[n - Q[n-1]]

T1=${Q[t1]} # Q[n - Q[n-2]]

Q[n]=`expr $T0 + $T1` # Q[n - Q[n-1]] + Q[n - Q[n-2]]

echo -n "${Q[n]} "

if [ `expr $n % $LINEWIDTH` -eq 0 ] # Если выведено очередные 20 членов в строке.

then # то

echo # перейти на новую строку.

fi

done

echo

exit 0

# Этот сценарий реализует итеративный алгоритм поиска членов Q-последовательности.

# Рекурсивную реализацию, как более интуитивно понятную, оставляю вам, в качестве упражнения.

# Внимание: рекурсивный поиск членов последовательности будет занимать *очень* продолжительное время.

--

Bash поддерживает только одномерные массивы, но, путем небольших ухищрений, можно эмулировать многомерные массивы.

#!/bin/bash

# Эмуляция двумерного массива.

# Второе измерение представлено как последовательность строк.

Rows=5

Columns=5

declare -a alpha # char alpha [Rows] [Columns];

# Необязательное объявление массива.