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

Пример 25-10. Исследование математических последовательностей

Пример 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

# См. книгу Дугласа Хольфштадтера, "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 поддерживает только одномерные массивы, но, путем небольших ухищрений, можно эмулировать многомерные массивы.

Оглавление книги