книги / Математическая логика и теория алгоритмов. Анализ алгоритмов

(21/55=0,381; 34/89 =0,382; 55/144=0,382); деление «через два числа»даёт0,236(34/144 =0,236;21/89 =0,236).

Такая же закономерность, оказывается, проявляется в колебаниях цен и используется в качестве ценовых уровней (линий) в так называемом трейдинге (торговле ценными бумагами).

Пример 2 [3].				xn 2	4xn 1 xn ,x0					1;x1			2.	(2.18)
Берём опять		x pn ,подставляя в преобразованное исход-
		n
ное выражение xn 2		4xn 1 xn 0, получаем:
				pn 2	4pn 1		pn		0.					(2.19)
Делим обе части выражения на:
	p2 4p1 1 0.p2						4p1 1 0.							(2.20)
Находим корни:
p ( 4)	( 4)2		4(1 1) 4				12		4 2				3 2	3, (2.21)
1,2	2 1						2				2
	xn	pn		c1 2		3 n c2 2						3	n ,	(2.22)
			x0 c1 c2			1,								(2.23)
			x c p1 c p1							2.
				1	1		2
Тогда:					c2 1 c1,									(2.24)
			c p1		(1 c ) p1				2,					(2.25)
				1		1
	c1 2			3 1	(1 c1) 2					3	1	2,		(2.26)
отсюда:
	2 c1			3 c1 (1 c1) (2							3) 2,
2 c1			3 c1 2 2 c1					3 c1				3 2,		(2.27)
				3 c1		3 c1 3,

31

2

3 c1 3,

c1 12.

Таким образом, окончательно получаем:

xn 12[ 2

3 n c2 2

3 n ].

(2.28)

2.2.РЕКУРСИВНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О ХАНОЙСКОЙ БАШНЕ

Задача о Ханойской башне [5, 6] представляет собой игру, придуманную французским математиком Франсуа Эдуардом Анатолем Люка (1842–1891) (рис. 2.1).

а б

Рис. 2.1. Задача о Ханойской башне: а – игрушка с восемью дисками; б – её автор Франсуа Эдуард Анатоль Люка

Это задача оптимального (за кратчайшее число ходов) и своего рода безопасного (бо́льший диск не может быть на меньшем, в этом ограничении безопасность и заключается!) перемещения («перемещения упорядоченности») с одного стержня – объекта Х на другой объект Z с дополнительным вспомогательным объектом Y (между прочим, есть задачи и не с одним Y).

Рассмотрим, например, всего три диска, то есть n = 3. Исходное состояние изображено на рис. 2.2.

32

Рис. 2.2. Исходное в задаче о Ханойской башне для трёх дисков (n = 3)

Очевидно, что для того, чтобы перенести самый большой диск на стержень Z необходимо его «освободить», то есть выстроить «подбашню» из двух дисков на стержне Y, поэтому сначала верхний диск переносится на стержень Z (рис. 2.3).

Рис. 2.3. Первый шаг – перенос верхнего диска на ось Z:

этот шаг можно обозначить как (Х, Z)

Далее осуществляется перенос (Х, Y) (рис. 2.4).

Рис. 2.4. Второй шаг – перенос (Х, Y)

Теперь, после переноса (Z, Y), получим подбашню из двух дисков (из n–1) на Y (рис. 2.5).

Рис. 2.5. Третий шаг – подбашня перенесена

33

Теперь наступает «переломный» момент – перенос самого большого диска (Х, Z) (рис. 2.6).

Рис. 2.6. Четвёртый шаг – перенос самого большого диска (Х, Z)

Далее опять переносится подбашня, но уже только из одного диска и теперь с y на х, чтобы большой диск подбашни из двух дисков переместить на Z (рис. 2 7).

Рис. 2.7. Пятый шаг (Y, Х)

Теперь перенос большого диска подбашни из двух дисков

(Y, Z) (рис. 2.8).

Рис. 2.8. Шестой шаг (Y, Z)

И, наконец, перенос последней подбашни, состоящей из одного диска (рис. 2.9).

С тремя дисками понятно. Допустим, мы не знаем, как решать задачу для n дисков. Мы не знаем, как делать первый шаг: перенести на Z либо на Y? Мы не знаем и последний шаг: где будет самый малый диск, на Х или на Y?

34

Рис. 2.9. Седьмой шаг (Х, Z) и получаем целевое состояние

Но зато мы знаем, как разделить задачу на более крупные этапы-подзадачи: самый большой диск должен оказаться свободным на Х, именно на Х, а не на Y, иначе решение будет неоптимальным (кратчайшим), ибо тогда ещё нужно было бы сначала перенести этот диск с Х на Y. Поэтому и подбашня n–1 должна оказаться именно на Y, так как Z должен быть свободным для переноса самого большого диска. Затем аналогично подбашня n–1 выстраивается на Х, а затем перемещается на Z.

Таким образом, выясняется фрактальная структура решения этой задачи: 1) перенос подбашни, состоящей из n–1, n–2…1 дисков с некоторого исходного стержня на некоторый целевой, используя некоторый дополнительный; 2) перенос большого диска данного этапа; 3) перенос подбашни на большой диск данного этапа. Следовательно, вызывая одну и ту же процедуру, необходимо только определять на каждом этапе: «откуда» – исходный стержень, «куда» – целевой и «дополнительный». В самом начале на первом шаге «откуда» = x, «куда» = z, «дополнительный» = y. Рекурсивная процедура, например, может иметь вид [2]:

CARRY (n, x, z, y) – перенос дисков с х на z, используя y.

Разбиваем CARRY (n, x, z, y) на две основных рекурсивных подзадачи (по башням):

1.CARRY (n–1, x, y, z) башню n–1 (без самого большого диска) перенести с х на y, используя z;

2.CARRY (1, x, z, _) перенести один нижний диск с х на z;

3. CARRY (n–1, y, z, x) перенести башню n–1 перенести с y на z, пользуясь x.

35

Перенос одного диска выполним как нерекурсивную процедуру ONEDISC (x, z). Получаем:

procedure CARRY(n, x, z, y: integer);

begin if n>0 then

begin CARRY(n–1, x, y, z);

ONEDISC(x, z);

CARRY(n–1, y, z, x)

end

end;

Изобразим этот алгоритм (рис. 2.10).

Рис. 2.10. Схема алгоритма решения задачи о Ханойской башне

Да, не зря пишут на форумах: «Рекурсивное решение напоминает волшебный фокус – не зная решения, а зная только некоторую закономерность задачи, получаем само решение. Фактически указывается не сама последовательность перемещений дисков, а алгоритм сведения задачи к более простому случаю» [8]. Попробуем раскрыть секрет этого «фокуса».

36

2.3.АНАЛИЗ РЕКУРСИВНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ О ХАНОЙСКОЙ БАШНЕ

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

x

z

y

n,

,

,

;

x

z

y

x

y

z

n 1,

,

,

;

x

y

z

(2.29)

x

z

.

,

;

x

z

y

z

x

n 1,

,

,

y

z

x

В (2.29) выражение

x

z

y

– это название проце-

n,

,

,

z

y

x

дуры CARRY (n, x, z, y: integer); с указанием изменяющегося «смысла» переменных. В числителе – как бы глобальный смысл, в знаменателе – локальный, то есть на данном этапе.

В начале – х «откуда» – исходный стержень = x, z – «куда» – целевой=z,y –«дополнительный»= y.

– это сами команды процедуры.

n 1,xx , yy , zz ; – CARRY (n–1, x, y, z) – перенос подбашни

n–1 с исходного на дополнительный стержень, то есть здесь дополнительный в качестве целевого, а целевой – в качестве дополнительного.

37

xx , zz ; – ONEDISC (x, z) – перенос большого диска с ис-

ходного на целевой стержень

n 1, yy ,zz ,xx – CARRY (n–1, y, z, x) перенос подбашни n–1

с дополнительного, он теперь в качестве исходного, на целевой стержень, он был в качестве дополнительного, а дополнительный теперь тот, который был исходным.

Таким образом, при вызовах процедуры до тех пор, пока n > 0, осуществляется подстановка переменных:

x

z

y

x

z

y

x

z

y

n,

,

,

;

n 1,

,

,

;

n

2,

,

,

;

x

y

z

x

z

y

x

z

y

x

y

z

x

y

z

x

y

z

n 1,

,

,

;

n 2,

,

,

;

n

3,

,

,

;

(2.30)

x

z

y

x

y

z

x

y

z

....

x

z

x

z

x

z

,

;

,

;

,

;

x

y

x

z

x

z

y

z

x

y

z

x

y

z

x

n 1,

,

,

;

n 2,

,

,

;

n

3,

,

,

;

y z x

z y x

y z x

x

z

y

Так, нижняя часть во второй скобке

n 1,

,

,

получа-

z

x

y

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

частьвыражения n 1,

x

,

y

,

z

;

изпредыдущей«скобки»–первой:

y

z

x

x

z

y

n,

,

,

;

x

z

y

x

y

z

n

1,

,

,

;

x

y

z

x

z

.

,

;

x

z

y

z

x

n 1,

,

,

;

y

z

x

38

Получаем xx , zz ; xx , zy ; xx , zz ; xx , zy ;…. Это был первый шаг, зависящий от чётности числа дисков n. Нечётное – xx , zz ,

чётное – xx , zy . Получаем подстановки: 1) x, z, y, 2) x, y, z и пе-

реносы xz и xy.

Обратим ещё раз внимание на чередование подстановок на этом первом проходе:

x

z

y

x

z

y

x

z

y

n,

,

,

; n 1,

,

,

;

n

2,

,

,

;

.... (2.31)

x

z

y

x

y

z

x

z

y

Соответственно,

для

команды

CARRY

(n–1, x, y, z);

переноса подбашни с х на у, пользуясь z:

x

y

z

x

y

z

x

y

z

n

1,

,

,

;

n 2,

,

,

; n 3,

,

,

; .... (2.32)

x y z

x z y

x y z

Для команды CARRY (n–1, y, z, x) переноса подбашни

с у на z, пользуясь х, будет:

y

z

x

y

z

x

y

z

x

.... (2.33)

n 1,

,

,

; n

2,

,

,

;

n 3,

,

,

;

y

z

x

z

y

x

y

z

x

Теперь ещё от них (после (2.3), (2.33)) как бы «пере-

ломная» команда либо yy , zz , xx , либо yz , zy , xx . Проверим после yy , zz , xx :

39

x

z

y

n i,

,

,

;

y

z

x

x

y

z

n i 1,

,

,

;

y

x

z

x

z

.

,

;

y

z

y

z

x

n i 1,

,

,

;

x

z

y

Получаем подстановку: 3) y, z, x и перенос yz.

Проверим после yz , zy , xx ;

j,

x

,

z

,

y

;

n

z

y

x

x

y

z

n j 1,

,

,

;

z

x

y

x

z

.

,

;

z

y

y

z

x

n j 1,

,

,

;

x

y

z

(2.34)

(2.35)

Получаем подстановку: 4) z, y, x и перенос zy.

Подстановки x, y, z, получаемые из xy , zy , xz и x, z, y из xy , zz , xy (2.32), уже были выше.

Но получаются ещё вот какие: xz , xy , zy

40