Задачи и упражнения Рекурсивные алгоритмы

Упражнение № 1. Знакомство с рекурсивными алгоритмами

Пример 65. Написать программу построения изображения, представленного на сле­дующем рисунке:

о о

оПоС ]оПо

о°о°о<

о о

о

о

о ^пО° °

о()о

°о° о °о°

О ^—\ о

6° О () °6°0°0^|

° V ° ° V °

оО° ° °о°

о

°оГ> о

о — о о

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

Для того, чтобы составить программу построения этого изображения, можно:

• описать процедуру изображения одной окружности с четырьмя окружностями поменьше;

• для изображения каждой окружности следующего уровня использовать эту же процедуру, только с другими значениями параметров — координат центров, вели­чин радиусов и т. д.

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

А*'

видно, равны. Пусть — = к\, где / — радиус окружности окружения, — = к2.

г г

Ргосейиге Рл.с1: иге1 (х, у, г, г1: 1пЬедег); Ведл_п

{изобразить окружность с центром (х, у) и радиусом г}; {вычислить г1};

Еог 1: =1 То 4 Бо

Ведхп {вычислить координаты центра (х1, у1) 1-й окружности};

Рл.с1: иге1 (х1, у1, < новое значение г>, г1); Епс1; Еп< 3.

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

Как вычислить значения х1, у\1 Они зависят от х и у следующим образом: х\ = х + с! х, у\ = у + йу_л Необходимо выразить значения приращений координат (1х, йу. Воспользуемся определениями тригонометрических функций §т и со§:

йх = г\- со$(а)

йу = г\ • §т(а), где а = я/2, я, Зя/2, 2п.

Если осуществить вызов этой же процедуры из основной программы с началь­ными параметрами, то рекурсивные вызовы никогда не закончатся и программа будет работать бесконечно. Для того, чтобы этого не случилось, можно ввести в качестве аргумента процедуры некоторую величину п, которая при каждом новом вызове процедуры будет уменьшаться на 1, а в тело процедуры включить условие, что его операторы должны выполняться только при п > 0, то есть это условие будет играть роль своеобразной «заглушки», ограничивающей число вызовов процедуры. Ниже приведена программа, полностью решающая поставленную задачу. В основной программе запрашиваются радиус г самой большой окружности и число уровней п, а также задаются значения коэффициентов к\ и к2. Центр самой большой окружности располагается в центре экрана.

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

Уаг х, у, п, г, г1, сс1, дт: 1пЬедег; к1, к2: Кеа1;

Ргосейиге Р1сЬиге2(х, у, г, г1, п: 1пЬедег); Уаг х1, у1: 1пЬедег; л.: 1пЬедег; Ведхп

I€ п> 0 ТЬеп {" заглушка" } Ведхп

сл_гс1е (х, у, г); {рисование окружности}

г1: =Ьгипс(г*к2); {вычисление радиуса орбиты}

Еог 1: =1 То 4 Оо

Ведхп

х1: =Ьгипс(х+г1*соз(р±/2*±)); у1: =Ьгипс(у+г1*зл.п(рл_/2*л.)); {координаты центра 1-й окружности} рл.с1: иге2 (х1, у1, Ьгипс (г*к1), г1, п-1); {вызов процедуры с новыми параметрами}

Епс1; Епс1; Епс1;

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

ЭДгл_1: е1п ('Введите число уровней п. ¹); КеасИп (п); х: =600 □ IV 2; у: =400 □ IV 2;

ДОгл_1: е1п (¹ Введите радиус первой окружности г¹); Кеас11п (г); к1: =0.3; к2: =2;

сс!: =с! е1: ес1:; дш: =1; {инициализация графики} 1П11: дгар11 (сс1, дт, ¹ с: \'Ьр7_0\Ып ¹); рл.с1: иге2 (х, у, г, г1, п); КеасИп; {задержка на экране} с1о5едгарЬ;

Епс!.

Примечания:

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

2. Изменяя в процессе демонстрации работы программы значения к1, к2, п, можно получать множество привлекательных рисунков.

Пример 66. Снежинка. Разработать программу, которая обеспечивает рисование снежинки, число звеньев и число ветвей которой задаются пользователем.

На рисунке ниже изображена снежинка, состоящая из трех звеньев и восьми ветвей.

Сделаем расчет дайны каждого звена по известному значению п — количеству звеньев и величине экрана. Будем считать, что снежинка строится в квадрате 400 х 400 точек. Центр снежинки совпадает с центром квадрата, а длина отрезка каждого

 

очередного звена в четыре раза меньше предыдущего. Если через / обозначить дли­ну первого звена, то справедливо следующее равенство:

 

или

/ х = 200 (сумма членов геометрической прогрессии),

то есть

Л П-1

/ = 200 х 3 х —-------.

4^п -1

Пусть снежинка состоит из одного звена и р ветвей, тогда соответствующая программа проста. Основная ее часть имеет вид

Еог 1: =1 То р Ио

Ведл.п

х1: =Ьгипс (х+1*соз (2*рл_* (1-1) /р)); у1: =Ьгипс(у+1*51П(2*р1*(1-1)/р)); {координаты конца очередного звена} Ипе (х, у, х1, у1); {рисование звена}

Епс1;

Здесь х, у — координаты точки центра снежинки. Наша снежинка рисуется как бы много раз, при этом длины звеньев изменяются, поэтому их надо просчитать один раз и запомнить в массиве Ьтп элементов. Длина каждого звена уменьшается в четыре раза по отношению к предыдущему. Длина первого звена определяется из того, что в квадрате из 400 х 400 точек необходимо построить снежинку из п звеньев. Если мы дошли до этапа рисования самого маленького звена (самой маленькой снежинки), то наша программа должна работать как приведенный набросок.

Итак, логика решения задачи.

Начинаем рисовать из центра, точки А, нарисовали первый отрезок АВ (а), если это не последнее звено, то будем рисовать отрезок следующего звена ВС, звено не последнее, поэтому продолжим. Предположим, что нарисовали СЕ, это первая ветвь самой маленькой снежинки, наша программа должна работать как набросок, то есть рисовать все ветви этой снежинки. После этого мы должны вер-

 

А

В

а

б

нуться в точку В. Так как это не последняя ветвь этой снежинки, то мы снова должны нарисовать следующую ветвь — отрезок ВБ (б), а затем снова полностью самую маленькую снежинку. Что необходимо для реализации этой логики? Пусть значение переменной к будет равно текущему номеру звена снежинки, в началь­ный момент оно равно п. Тогда при переходе от точек С, В к точке В мы должны «вспомнить» координаты точки В и номер ветви снежинки, рисуемой из точки В. При переходе от точки В к точке А мы должны «вспомнить» координаты точки А и номер ветви снежинки, рисуемой из точки А. Эта логика легко реализуется с по­мощью рекурсии.

Примечание. Для вычисления значения показательной функции а^п используется тождество а^п — е^пЫа.

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

изез СгарЪ;

СопзЪ р=8; п=4;

Уаг х, у, 1, сс1, дт: 1п1: едег; Ь: Аггау[1..п] 1п1: едег;

Ргосейиге Рз_с1: игеЗ (х, у, к: 1п1: едег);

Уаг х1, у1: 1п1: едег; 1: 1п1: едег;

Вед±п

15 к> 0 ТЪеп {«заглушка»} Вед±п

• Рог 11=1 То р Во Вед±п {координаты конца очередного звена} х1: =-Ьгипс(х+Ь[к] *соз (2*рз_* (1-1) /р)); у1: =-Ьгипс(у+Ь[к] *31п(2*р1* (1-1) /р)); Нпе (х, у, х1, у1); {рисование звена} рл_с1: игеЗ (х1, у1, к-1); Еп< 1; Еп< 1;

Епс1;

Вед±п

Ъ[п]: = Ъгипс(200*3*ехр ((п-1)*1п(4))/(ехр(п*1п(4))-1))/ {***}

Рог 1: =2 То п Во Ь [п-1+1 ]: =" Ьгипс (Ь [п] /ехр ((1-1) *1п (4)));

х: =300; у: =200; {координаты центра снежинки}

сс1: =с! е1: ес1:; дш: =1; {инициализация графики}

1п11: дгарЬ (сс1, дт, ' с: \1: р7_^0\Ь1П ¹);

Рл_с1: игеЗ (х, у, п);

КеасИп; {задержка на экране}

С1озедгарЪ;

Епс!.