Задания. 1. Модифицировать программу так, чтобы пересекающиеся части отрезков (АВ, ВТ) рисовались один раз

1. Модифицировать программу так, чтобы пересекающиеся части отрезков (АВ, ВТ) рисовались один раз.

2. Если строку программы, помеченную {***}, изменить на

Ъ[1]: =-Ьгипс (200*3*ехр ((п-1) *1п (4)) / (ехр (п*1п (4))-1)); то какие дальнейшие изменения необходимо внести в программу?

Упражнение № 2. Простые задачи

Пример 67. Написать рекурсивную программу поиска минимального элемента мас­сива.

Решение. Опишем функцию р_тл_п, которая определяет минимум среди первых п элементов массива а. Параметрами этой функции являются число элементов в рассматриваемой части массива п и значение последнего элемента этой части а[п]. При этом если п > 2, то результатом является минимальное из двух чисел — а[п] и минимального числа из первых (п — 1) элементов таблицы. В этом заключается рекурсивный вызов. Если же п = 2, то результатом является минимальное из пер­вых двух элементов массива. Чтобы найти минимум всех элементов массива, надо обратиться к функции р_тл_п, указав в качестве параметров значение размерности массива и значение последнего его элемента. Минимальное из двух чисел опреде­ляется с помощью функции Ш1п, параметрами которой являются эти числа.

Ргодгат Ехатр1е_67;

СопзЪ п=10;

Туре МуАггау=Аггау[1..п] 0± 1пЬедег;

СопзЪ а: МуАггау=(4, 2, -1, 5, 2, 9, 4, 8, 5, 3);

РипсЫоп Ш1П (а, Ъ: 1пЬедег): 1пЬедег;

Вед±п

1± а> Ъ ТЬеп тл_п: =Ъ Е1зе тл_п: =а; •

Епс1;

РипсЫоп р_тл_п (п, Ь: 1пЬедег): 1пЬедег;

Вед±п

1± п=2 ТЬеп р_Ш1П: =Ш1П(п, а[1])

Е1зе р_Ш1П: =тл_п (а [п], р_Ш1П (п-1, а [п]));

Епс1;

Вед±п

^г1Ье1п('Минимальный элемент массива - ¹, р_ш1П(п, аIп]));

Епс1.

Пример 68. Ханойские башни. Имеются три стержня Л, В, С. На стержень А нанизано п дисков радиуса 1, 2,..., п таким образом, что диск радиуса / является 1-м сверху. Требуется переместить все диски на стержень В, сохраняя их порядок распо­ложения (диск с большим радиусом находится ниже). За один раз можно перемещать только один диск с любого стержня на любой другой стержень. При этом должно выполняться следующее условие: на каждом стержне ни в какой момент времени никакой диск не может находиться выше диска с меньшим радиусом.

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

Предположим, что мы умеем перекладывать пирамиду из (п— 1) кольца. Рас­смотрим пирамиду из п колец. Переместим первые (п— 1) колец на стержень С (это мы умеем). Затем перенесем последнее я-е кольцо со стержня А на стержень В. Далее перенесем пирамиду из (п— 1) кольца со стержня С на стержень В. Так как я-е кольцо самое большое, то условие задачи не будет нарушено. Таким образом, вся пирамида будет на стержне В. Действуя так, можно переложить любое число колец. При этом для решения задачи будет достаточно 2^п— 1 перекладываний.

Ргодгат Ехатр1е_68;

Сопз'Ь к=3;

Уаг а, Ъ, с: СЪаг;

Ргосейиге К.л_пд(п: 1пЬедег; а, Ъ, с: СЬаг);

Вед±п

И п> 0 ТЬеп Вед±п

К1пд (п-1, а, с, Ъ); ДОгл_1: е1п (¹ кольцо ¹, п, ¹ с ¹, а, ¹ —> ¹, Ъ, ^{1 1}); Кл_пд (п-1, с, Ъ, а); Епс1; Епс1; Вед±п

а: = ' А'; Ь: = ' В '; с: = 'С'; Кл_пд (к, а, Ъ, с); КеасИп Епс1.

Упражнение № 3. Фрактальные кривые Пример 69. Написать программу получения следующего изображения:

 

В треугольнике проводятся все три средние линии. В результате он разбивается на 4 новых треугольника. К трем из них, примыкающим к вершинам первоначаль­ного треугольника, применяется та же процедура.

Ргодгат Ехатр1е_69; 11зез СгарЪ;

Уаг хс, ха, хЪ, уа, уЪ, ус: 1п1: едег; {координаты вершин треугольника}

п, сс1, дт: 1п1: едег; Ргосейиге Тг1апд1е(ха, уа, хЪ, уЪ, 'хс, ус, п: 1п1: едег); {координаты середин сторон треугольника} Уаг хр, хд, хг, ур, уд, уг: 1п1: едег; Вед±п

И п> 0 ТЪеп {«заглушка»}

Вед1п {вычисление координат середин сторон треугольника} хр: =(хЪ+хс) Бл^ 2;

ур: =(уЪ+ус) Бл^ 2; хд: =(ха+хс) Бл^ 2; уд: =(уа+ус) Бл^ 2; хг: =(хЪ+ха) Бл^ 2; уг: =(уЪ+уа) Бл^ 2; Ппе (хр, ур, хд, уд);

{изображение средних линий треугольника} Ппе{хд, уд, хг, уг); Ппе (хр, ур, хг, уг); Тг1апд1е(ха, уа, хг, уг, хд, уд, п-1); ТЬг1апд1е(хЬ, уЪ, хр, ур, хг, уг, п-1)/ Тг1апд1е(хс, ус, хд, уд, хр, ур, п-1); Еп< 1;

Еп< 1;

Вед±п {задание начальных значений}

{координаты вершин самого большого треугольника} хс: =300; ус: =0; хЪ: =600; уЬ: =400; ха: =0; уа: =400; с< 1: =< 1е" Ьес1:; дт: =1;

1п11: дгар]1 (сс1, дт, ¹ с: \Ьр7_0\В1П ¹);

{изображение первого самого большого треугольника} Ппе (ха, уа, хЬ, уЬ); Ппе (хЪ, уЬ, хс, ус); Ппе (ха, уа, хс, ус); Тг1апд1е(ха, уа, хЬ, уЬ, хс, ус, 6); КеасИп; {задержка на экране} СИозедгарЬ; Еп< 1.

Задания для самостоятельного выполнения

1. Написать рекурсивную программу вычисления п-то члена геометрической прогрессии, суммы ее п первых членов и суммы ее членов, начиная с /-го по к-й.

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

3. Описать рекурсивную функцию поиска индекса минимального элемента массива.

4. Составить рекурсивную программу, проверяющую, является ли палиндромом фрагмент строки с /-го по у-й символ.

5. Составить программы для построения на экране следующих изображений:

 

6. Изменить программу рисования кривых Гильберта так, чтобы обеспечить рисование кривых С[ 1], С[2], С[3], С[4], С[5] (см. базовый учебник «Информа­тика»).

7. Изменить программу рисования кривых Гильберта так, чтобы обеспечить ри­сование кривых А[3], 2? [3], С[3], /)[3].

8. На рисунке изображены кривые Серпинского 1 и 2-го порядков. Составить программу построения кривых 1, 2, 3, 4 и 5-го порядков, так чтобы центры этих кривых совпадали.

 

9. На рисунке изображены кривые Коха 1 и 2-го порядка. Составить программу построения кривой 7У-го порядка.

1_

 

10. На рисунке изображены прокладки Серпинского 1 и 2-го уровня. Разработать программу построения прокладки Серпинского 7У-го порядка.

 

11. На рисунке изображен ковер Серпинского 1 и 2-го уровня. Разработать про­грамму построения ковра Серпинского 7У-го порядка.

а	□	& '
о	......	- - С О

 

Упражнение № 4. Перебор с возвратом

Многие комбинаторные задачи можно представить как поиск элементов конеч­ного множества, удовлетворяющих определенным условиям. Очевидно, что всегда есть «лобовое» решение, состоящее в переборе всех элементов этого множества с

проверкой соответствующих условий. Однако даже для простых задач такой пере­бор потребует огромных временных затрат.

Общая схема

Любая комбинаторная задача, к которой применим алгоритм перебора с возвра­том, может быть описана в общем случае следующим образом: даны п линейно упо­рядоченных множеств 1/_и 11_ъ..., 1/„ и требуется построить вектор А = (а_ь а_ъа_п), где а_хе 1]_и а₂е 1]_ъ..., а_пе 11_п, удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора с возвратом вектор А строится покомпонентно слева на­право: Предположим, что уже найдены значения первых к— 1 компонент,

А = (а,, а₂, а_к-,,?,...,?),

тогда заданное множество условий ограничивает выбор следующей компоненты ^некоторым множеством 8_кс V_к. Если ^оказалось непустым, мы вправе выбрать в качестве а_к наименьший элемент 8_к и перейти к рассмотрению 8_к+, и так далее. Однако, если условия таковы, что 8_к оказалось пустым, мы возвращаемся к пре­дыдущему этапу, выбрасываем (к — 1)-й элемент а_к-_х и выбираем в качестве но­вого а_к— 1 тот элемент 8_к-_и который непосредственно следует за только что от­брошенным. Может оказаться, что для нового а_к-_х условия задачи допускают непустое 8_Ь и тогда мы попытаемся снова выбрать элемент а_к. Если невозможно выбрать а_к-_и то возвращаемся еще на шаг назад и выбираем новый элемент а_к-₂ и так далее.

Алгоритм

Шаг 1. [Начало] Положить к = 1 и ^ = \]_х.

Шаг 2. [Следующий элемент Если 8_к пусто, то перейти к шагу 5, иначе — положить а_к равным наименьшему из элементов 8_к.

Шаг 3. [Закончено ли решение? ] Если к< п, то перейти к шагу 4, иначе — записать (а_и а_ъ..., а_п) как решение. Если необходимо найти все возможные реше­ния, то положить к = к + 1 и перейти к шагу 5, иначе — остановиться.

Шаг 4. [Увеличение к] Увеличить А; на 1, вычислить 8_к и вернуться к шагу 2.

Шаг 5. [Возврат] Если к = 1, то дальнейшее продвижение назад невозможно; поэтому — остановиться; при этом либо все решения найдены, либо их не суще­ствует. Если к > 1, то уменьшить А; на 1, положить 8^= и вернуться к шагу 2.

Пример 70. Задача о шахматном коне. Существуют способы обойти шахматным конем шахматную доску, побывав на каждом поле по одному разу. Составить про­грамму нахождения всех возможных способов обхода доски.

Решение

Структуры данных. Для хранения «истории» прохождения конем доски необхо­димо знать, был на конкретном поле[/, у] конь или нет.

Из поля [/, у] конь может попасть (в максимальном варианте) на восемь полей. В массивах А'[1..8], д]\ 1..8] будем хранить приращения к значениям координат, в сумме с которыми /, у дают возможные координаты нового хода коня.

Примечание. На рисунке символом ** обозначено положение коня, а цифрами 1, 2,..., 8 — номера ходов, которые можно сделать из поля [3, 5].

Выполнив очередной ход, можно:

• попасть за пределы доски;

• попасть в поле, которое уже занято;

• попасть в поле, которое пока еще свободно.

Учитывая это, для доски из т горизонталей и п вертикалей вводится массив

						6,			Г1 [к]	гз [к]	к
									-2
■									-1
					**
Ж										-1
										-2
■									-1	-2
									-2	-1

г: Аггау [-1.. т+2, -1.. п+2] 1п1: едег;,

 

где

О, если поле [/, у] конем не посещалось;

г [/, у] = 1-1, если поле [/, у] находится за пределами доски;

если поле [/, у] посещалось конем в результате хода с номером

Основная логика работы достаточно проста:

Ведл.п

II < клетка занята> Ог < клетка за пределами доски>

ТЬеп ехп_-Ь

Е1зе

Ведл.п

< сделать ход>; < выбрать очередной ход>; Епс1;

Епс1;

Поиск варианта обхода начинается с левой верхней клетки доски, то есть с г[ 1, 1]. Выполнить ход можно только в том случае, если клетка свободна или если не осуществляется выход за пределы доски (г[/, у] = 0). Сделать ход конем означает изменить значение соответствующего элемента массива г на очередное значение / — Если очередная клетка занята или если ход делается за пределы доски, надо попытаться сделать из той же позиции другой ход— взять следующие значе­ния из массивов п и лу. Если все 8 вариантов ходов из текущего положения будут проверены и ни одно из них не приведет к выполнению хода, то есть это ситуа­ция, когда конь не может продолжать обход доски. В этом случае мы должны вер­нуть один ход или серию ходов и попытаться найти новый вариант обхода. Для этого надо взять следующие значения приращений координат из массивов п и лу, попытаться сделать новый ход и так далее. Но для того, чтобы осуществить «воз­врат», необходимо знать «историю» обхода. Завершается поиск обхода, если все клетки пройдены, то есть значение I равно т* п (тогда надо вывести массив на экран), или если конь не может выполнить очередной ход (на экран надо вывести сообщение о невозможности выполнения обхода).

Реализовать такую логику поиска обхода выгоднее всего с помощью рекурсии.

Ргодгат Ехатр1е_7 0;

Сопз" Ь п=4; т=5; {размеры доски}

д: Воо1еап=^а1зе; {возможно ли сделать обход}

сИ: Аггау[1..8] О? 1пЪедег=(-2, -1, 1, 2, 2, 1, -1, -2); с! ^: Аггау [1.. 8] 1п*: едег= (1, 2, 2, 1, -1, -2, -2, -1); Уаг а: Аггау [-1..п+2, -1..т+2] 01 ШЪедег; 1, 1: 1п-Ьедег;

Ргосес1иге РгхпЪ; {вывод двумерного массива на экран} Вед±п

Еог ±: =1 То п Оо Ведхп

Еог □: =1 То т Оо Мгке(а[1, ]]: 3); ЭДгл.1: е1п Епс1; Епс1;

Ргосейиге гес (1, ^, Ь: 1п" Ьедег); {процедура поиска обхода}

Уаг к: 1п1: едег;

Ведхп

(а[1, ]]< > 0) ТЬеп ехИ: {выход за пределы доски или клетка

занята}