Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Alg_Lang_All.doc
Скачиваний:
11
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

Контрольные вопросы

  1. Дать понятие рекурсии.

  2. Дать определение рекурсивного алгоритма.

  3. Привести примеры рекурсивных алгоритмов.

  4. Что такое “Точка останова” рекурсивной процедуры?

  5. Дать определение графа.

  6. Дать определение иерархической структуры.

  7. Дать определение родительского, дочернего элемента, листа, ветки, корня.

  8. Какие операции можно проводить на иерархических структурах?

  9. Как представить иерархическую структуру в табличном виде?

  10. Привести алгоритм добавления дочернего элемента.

  11. Привести алгоритм поиска дочернего элемента по его ключу.

  12. Привести алгоритм получения количества дочерних элементов.

  13. Привести алгоритм получения суммы значений числовых атрибутов дочерних элементов данного узла.

  14. Привести алгоритм получения среднего значения числовых атрибутов дочерних элементов данного узла.

  15. Привести алгоритм получения максимального или минимального значения числовых атрибутов дочерних элементов данного узла.

  16. Как осуществляется поиск в иерархической структуре?

  17. Приведите алгоритм вывода на экран иерархической структуры.

Задания

Задание 1. Написать программу построения изображения, представленного на рисунке 5.

Рис.5

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

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

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

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

Алгоритм рисования окружности радиуса r с центром в точке (x,y) с четырьмя окружностями вокруг (при этом необходимо знать расстояния r1 от точки (x,y) до центров окружностей окружения, которые равны): пусть , где - радиус окружности окружения, .

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

Для вычисления значений x1 и y1 воспользуемся определениями тригонометрических функций sin и cos:

Для того, чтобы программа с данной рекурсивной процедурой работала не бесконечно, необходимо в качестве аргумента процедуры ввести некоторую величину n (здесь логично за величину n взять число уровней окружностей), которая при каждом новом вызове процедуры будет уменьшаться на 1, а в тело процедуры включить условие, что его операторы будут выполняться только при n>0. Данное условие будет играть роль «точки останова» (граничное условие), ограничивающее число вызовов процедуры.

В основной программе запрашивается количество уровней n, задаются координаты центра большой окружности (x,y) и ее радиус r, а также коэффициенты k1 и k2. Центр самой большой окружности располагается в центре экрана. Для того, чтобы проследить последовательность рисования окружностей при рекурсивных вызовах, в тело процедуры можно включить процедуру паузы.

Фрактальные кривые.

Понятие фрактала. Многие объекты обладают свойством “самоподобия”. Например, строение гористой поверхности или изрезанность морского берега, снежинка.

Математическое описание бесконечно дробимых объектов уравнениями линий или поверхностей очень громоздко из-за большого количества мельчайших объектов. Для преодоления этой трудности математиком Исследовательского центра корпорации IBM Бенуа Мандельбротом в 1975 году был введен термин “фрактал” (от латинского fractus – раздробленный, разбитый, состоящий из фрагментов), а в 1982 году опубликована основополагающая книга “Фрактальная геометрия природы”, где описаны фрактальные множества, их свойства, методы получения и изображения.

В машинной графике фракталы применяются при генерации искусственных облаков, гор, поверхности моря. Образы фракталов похожи на природные объекты — деревья, растения, узоры, звездные скопления т.п.

Задание 2. Напишите программу построения изображения, представленного на рисунке 6.

Рис.6

Задание 3. Напишите программу построения изображения, представленного на рисунке 7.

Рис. 7

Задание 4. Напишите программу построения изображения, представленного на рисунке 8 - (кривая Коха).

Рис. 8

Рекомендации: Процесс формирования кривой Коха состоит в следующем: отрезок разбивается на три равные части, и на средней части отрезка строится, например, квадрат или равносторонний треугольник. Для простоты рассмотрим кривую Коха с квадратом. На рисунке изображены кривые Коха первого и второго порядка. Для рисования кривой Коха используются только повороты на +90° и -90° и смещения вдоль прямолинейных отрезков.

Алгоритм рисования кривой Коха можно записать следующим образом:

  • нарисовать прямолинейный отрезок заданной длины;

  • повернуть на +90°;

  • нарисовать прямолинейный отрезок заданной длины;

  • повернуть на -90°;

  • нарисовать прямолинейный отрезок заданной длины;

  • повернуть на -90°;

  • нарисовать прямолинейный отрезок заданной длины.

Затем эта последовательность вновь применяется к каждому прямолинейному участку построенной ломаной линии.

Прямолинейные отрезки, начинающиеся из текущей точки и оканчивающиеся в точке с заданными координатами, в программе необходимо рисовать процедурой. Процедура рисования является рекурсивной, она строит кривую Коха. Параметрами этой процедуры являются x и y (эти два числа задают единичный вектор в направлении очередного смещения) и величина смещения.

Задание 5. Напишите программу построения изображения, представленного на рисунке 8 – (“Множество Кантора”).

Рис. 8 Множества Кантора

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

Алгоритм рисования “множества Кантора”:

  • построить большой квадрат, внутреннюю часть которого, например, закрасить каким-либо цветом;

  • на его вершинах, как на центрах, рисуются квадраты в четыре раза меньшие первоначального;

  • это повторяется для каждого оставшегося квадрата, причем бoльшие квадраты перекрывают меньшие.

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

Задание 6. Напишите программу построения изображения, представленного на рисунке 9 - (треугольник Серпинского).

Рис. 9 Треугольник Серпинского

Рекомендации: фигура строится путем разбиения треугольника, необязательно равностороннего – средними линиями на четыре подобных треугольника, исключением центрального и рекурсивного разбиения угловых треугольников до получения площадных элементов желаемого разрешения.

Алгоритм построения треугольника Серпинского:

  • строится большой внешний треугольник (А);

  • строится треугольник, получающийся при соединении середин сторон большого треугольника (Б);

  • строятся треугольники, получающиеся аналогично элементу Б, но в качестве большого треугольника берутся треугольники, образованные элементами А и Б.

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

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

Спирали – это геометрические фигуры, у которых каждая последующая сторона немного больше предыдущей. Спираль также является примером графической рекурсии.

Задание 7. Напишите программу построения изображения, представленного на рисунке 10.

Рис. 10

Рекомендации: В изображении можно заметить ряд закономерностей:

  • построение начинается из “середины” рисунка;

  • каждый следующий отрезок увеличивается на определённую величину;

  • все отрезки либо вертикальные, либо горизонтальные;

  • при рисовании происходит последовательное построение сходных элементов с изменяющимися параметрами, следовательно, данный рисунок можно построить с использованием рекурсии.

Задание 8. Напишите программу построения изображения, в которой, кроме стороны, задан еще и угол витков спирали. На рисунке 10 приведена спираль с углом 90 градусов.

Задание 9. Напишите программу построения изображения, представленного на рисунке (“Снежинка”). Количество звеньев и ветвей, коэффициент уменьшения каждого звена ветви задаются пользователем.

Рис. 11

Рекомендации: На рисунке 11 изображена снежинка, состоящая из 3 звеньев и 6 ветвей.

Алгоритм:

  • Определить данные, необходимые для рисования снежинки и ввести обозначения: n – количество звеньев снежинки, p – количество ветвей снежинки, l – длину (в точках) ветви внутреннего звена, t – коэффициент уменьшения каждого звена.

  • Центр снежинки расположить в центре экрана монитора (320, 240).

  • Начинаем рисовать из центра снежинки: рисуем первый (длины l) отрезок, далее, если это не последнее звено, то рисуем отрезок длины l*t следующего звена, и так до тех пор, пока не нарисуем отрезок последнего звена (l*tn-1).

  • На последнем звене дорисовываем самую маленькую снежинку.

  • Возвращаемся на предпоследний отрезок и дорисовываем самое маленькое звено со снежинкой.

  • Продолжаем до тех пор, пока не нарисуем всю снежинку.

Задание 10. Напишите программу построения изображения, представленного на рисунке (“Ветка”). Длина первоначального звена, коэффициент уменьшения следующих звеньев задаются пользователем.

Рис. 12

Алгоритм:

  • Введем обозначения: n – количество звеньев ветки, длина первоначального (вертикального) отрезка ветки (в точках) - dl, коэффициент уменьшения каждого звена – t.

  • Начинаем рисовать с первоначального (вертикального) отрезка, далее, если это не последнее звено, просчитывается длина следующего отрезка и строится этот отрезок; так продолжается до тех пор, пока не прорисуются все n звеньев (часть рисунка, выделенная жирной линией).

  • Далее аналогично рисованию снежинки – прорисовывается левая часть ветви, а затем правая.

При работе с данной программой обратите внимание на ограничения, накладываемые на ввод данных: n – количество звеньев (>1); dl – длина первоначального отрезка в точках, брать 10 точек …(начните со 100); 0<m<1.

Задание 11. Напишите программу построения изображения, представленного на рисунке 13 с использованием рекурсии и без нее. Укажите достоинства и недостатки каждой из программ.

Рис. 13

Задание 12. Напишите программу построения изображения, представленного на рисунке 14 с использованием рекурсии и без нее. Укажите достоинства и недостатки каждой из программ.

Рис. 14

Упражнения на работу с иерархическими структурами

Задать в dbf таблице следующей структуры (номер элемента, код родительского элемента, наименование узла, сумма узла) 15-20 записей. Написать программу для соответствующего варианта задагий с помощью рекурсивных процедур.

Вариант 1.

  1. Получить количество корневых элементов.

  2. Вычислить сумму дочерних узлов.

  3. Результат записать в файл txt.

Вариант 2.

  1. Получить количество дочерних узлов.

  2. Получить сумму узла по ключу.

  3. Результат записать в файл doc.

Вариант 3.

  1. Получить ключ корневого элемента по порядковому номеру.

  2. Вычислить сумму дочерних узлов и заменить сумму в соответствующем родительском элементе новой суммой.

  3. Результат записать в файл xls.

Вариант 4.

  1. Получить ключ дочернего элемента по порядковому номеру.

  2. Заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл dbf.

Вариант 5.

  1. Добавить 2 дочерних узла.

  2. Получить по ключу название заданного узла.

  3. Результат записать в файл txt.

Вариант 6.

  1. Получить количество дочерних узлов.

  2. Если у узла есть дочерние узлы, то для всех дочерних узлов вычислить сумму, сравнить с суммой в родительском узле и если они различаются, то заменить сумму в родительском узле на вычисленную.

  3. Результат записать в файл doc.

Вариант 7.

  1. Получить количество корневых элементов.

  2. Если дочерних узлов нет, оставить сумму родительского узла без изменения.

  3. Результат записать в файл xls.

Вариант 8.

  1. Получить ключ корневого элемента по порядковому номеру.

  2. Заменить сумму в родительском узле суммой дочерних узлов.

  3. Результат записать в файл dbf.

Вариант 9.

  1. Получить ключ дочернего элемента по порядковому номеру.

  2. Если у узла есть дочерние узлы, то заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл txt.

Вариант 10.

  1. Добавить 3 дочерних узла.

  2. Вычислить сумму дочерних узлов и заменить сумму в родительском узле, если она отличается от суммы, вычисленной в дочерних узлах.

  3. Результат записать в файл doc.

Вариант 11.

  1. Получить количество дочерних узлов.

  2. Заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл xls.

Вариант 12.

  1. Получить количество корневых элементов.

  2. Если у узла есть дочерние узлы, то заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл dbf.

Вариант 13.

  1. Получить ключ корневого элемента по порядковому номеру.

  2. Вычислить сумму дочерних узлов.

  3. Результат записать в файл txt.

Вариант 14.

  1. Получить ключ дочернего элемента по порядковому номеру.

  2. Если у узла есть дочерние узлы, то заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов, если суммы отличаются.

  3. Результат записать в файл doc.

Вариант 15.

  1. Получить количество дочерних узлов.

  2. Заменить сумму в узле с заданным номером суммой дочерних узлов.

  3. Результат записать в файл xls.

Вариант 16.

  1. Получить ключ корневого элемента по порядковому номеру.

  2. Вычислить сумму дочерних узлов и заменить сумму в родительском элементе, если она отличается от вычисленной суммы в дочерних узлах.

  3. Результат записать в файл dbf.

Вариант 17.

  1. Получить ключ дочернего элемента по порядковому номеру.

  2. Заменить сумму в узле с заданным номером суммой дочерних узлов.

  3. Результат записать в файл txt.

Вариант 18.

  1. Добавить 3 дочерних узла.

  2. Если у узла есть дочерние узлы, то заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл doc.

Вариант 19.

  1. Получить количество дочерних узлов.

  2. Заменить сумму в узле суммой дочерних узлов.

  3. Результат записать в файл xls.

Вариант 20.

  1. Получить количество корневых элементов.

  2. Если у узла есть дочерние узлы, то заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл dbf.

Вариант 21.

  1. Получить ключ дочернего элемента по порядковому номеру.

  2. Вычислить сумму дочерних узлов.

  3. Результат записать в файл txt.

Вариант 22.

  1. Получить ключ корневого элемента по порядковому номеру.

  2. Если у узла есть дочерние узлы, то заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл doc.

Вариант 23.

  1. Получить ключ дочернего элемента по порядковому номеру.

  2. Заменить сумму в узле суммой дочерних узлов.

  3. Результат записать в файл xls.

Вариант 24.

  1. Получить количество корневых элементов.

  2. Заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл dbf.

Вариант 25.

  1. Получить количество дочерних узлов.

  2. Если у узла есть дочерние узлы, то заменить значение в узле с родительским кодом на новую сумму, состоящую из суммы всех дочерних узлов.

  3. Результат записать в файл txt.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]