Искусство программирования на языке сценариев командной оболочки
Шрифт:
Пример 25-10. Исследование математических последовательностей
#!/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
#
# 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 поддерживает только одномерные массивы, но, путем небольших ухищрений, можно эмулировать многомерные массивы.
Пример 25-11. Эмуляция массива с двумя измерениями
#!/bin/bash
# Эмуляция двумерного массива.
# Второе измерение представлено как последовательность строк.
Rows=5
Columns=5
declare -a alpha # char alpha [Rows] [Columns];
#
load_alpha
{
local rc=0
local index
for i in A B C D E F G H I J K L M N O P Q R S T U V W X Y
do
local row=`expr $rc / $Columns`
local column=`expr $rc % $Rows`
let "index = $row * $Rows + $column"
alpha[$index]=$i # alpha[$row][$column]
let "rc += 1"
done
# Более простой вариант
# declare -a alpha=( A B C D E F G H I J K L M N O P Q R S T U V W X Y )
# но при таком объявлении второе измерение массива завуалировано.
}
print_alpha
{
local row=0
local index
echo
while [ "$row" -lt "$Rows" ] # Вывод содержимого массива построчно
do
local column=0
while [ "$column" -lt "$Columns" ]
do
let "index = $row * $Rows + $column"
echo -n "${alpha[index]} " # alpha[$row][$column]
let "column += 1"
done
let "row += 1"
echo
done
# Более простой эквивалент:
# echo ${alpha[*]} | xargs -n $Columns
echo
}
filter # Отфильтровывание отрицательных индексов.
{
echo -n " "
if [[ "$1" -ge 0 && "$1" -lt "$Rows" && "$2" -ge 0 && "$2" -lt "$Columns" ]]
then
let "index = $1 * $Rows + $2"
echo -n " ${alpha[index]}" # alpha[$row][$column]
fi
}
rotate # Поворот массива на 45 градусов
{
local row
local column
for (( row = Rows; row > -Rows; row-- )) # В обратном порядке.
do
for (( column = 0; column < Columns; column++ ))
do
if [ "$row" -ge 0 ]
then
let "t1 = $column - $row"
let "t2 = $column"
else
let "t1 = $column"
let "t2 = $column + $row"
fi
filter $t1 $t2 # Отфильтровать отрицательный индекс.
done
echo; echo
done
# Поворот массива выполнен на основе примеров (стр. 143-146)
# из книги "Advanced C Programming on the IBM PC", автор Herbert Mayer