Основы алгоритмизации и языки программирования

Основы алгоритмизации и языки программирования

Учебно-методическое пособие

УДК

ББК

 

Рекомендовано к изданию Ученым советом МИЭМИС Алтайского государственного университета

 

Рецензент: директор МИЭМИС АлтГУ, д.э.н., профессор О.П. Мамченко

 

Авторы-составители: к.ф.-м.н., доцент Алексей Юрьевич Юдинцев, к.т.н., доцент Галина Николаевна Трошкина, к.т.н., доцент Игорь Анатольевич Драгун

 

Основы алгоритмизации и языки программирования: Учебно-методичсекое пособие/ А.Ю. Юдинцев, Г.Н.Трошкина, И.А.Драгун. – Барнаул, 2009. – 219 с.

 

Пособие «Основы алгоритмизации и языки программирования» представляет собой практикум по дисциплине основы алгоритмизации и языки программирования для студентов специальности «прикладная информатика в экономике» и направления «прикладная информатика». Данное пособие представляет собой вторую часть блока программная инженерия. Предполагается, что студенты к началу изучения данного курса освоили на процедурном уровне языки Visual FoxPro и Visual Basic for Application в ходе дисциплины «Информатика и программирование». Пособие организовано в виде цикла лабораторных работ. Каждая лабораторная работа содержит теоретический материал, примеры базовых алгоритмов и программ, контрольные вопросы и задания.

При изложении теоретического материала большое внимание уделяется базовым понятиям численных методов таким, как понятие итерационной процедуры, оценка погрешности, сходимость алгоритмов, понятие разностной производной, понятие рекурсии, рекурсивные алгоритмы. Изложены основы численных методов интегрирования и решения дифференциальных уравнений. На базе стандартных генераторов равномерных распределений рассмотрены алгоритмы генерации дискретных величин распределенных по заданному закону, генерация непрерывных случайных величин распределенных по заданному закону. В пособии приведено большое количество примеров алгоритмов и готовых программ.

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

 

СОДЕРЖАНИЕ

Лабораторная работа №1. Базовые языковые конструкции VFP и VBA. Основы работы с данными 5

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

Задания. 14

Лабораторная работа №2. Определение корней уравнений. 24

Определение корня уравнения методом деления отрезка пополам (дихотомии) 24

Определение корня одномерного уравнения методами касательных и секущих. 29

Определение корня одномерного уравнения методом простой итерации. 38

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

Задания. 47

Лабораторная работа №3. Поиск максимального и минимального значения функции одной и двух переменных. 49

Поиск максимального и минимального значения функции одной переменной методом последовательного перебора. 49

Определение максимального и минимального значения функции двух переменных методом градиентного спуска (подъема) 53

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

Задания. 63

Лабораторная работа №4. Рекурсия. Рекурсивные алгоритмы.. 65

Рекурсия. Рекурсивные алгоритмы.. 65

Графика и рекурсивные алгоритмы.. 69

Способы представления древовидных структур, поиск и редактирование в древовидных структурах. Рекурсивное выполнение операций над древовидными структурами (суммирование) 72

Работа с иерархическими структурами данных. Операции на деревьях. 72

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

Задания. 83

Лабораторная работа №5. Аппроксимация, интерполяция и экстраполяция. 98

Простейшие способы интерполяции и экстраполяции данных. 98

Аппроксимация выборки случайных чисел методом наименьших квадратов. 105

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

Задания. 115

Лабораторная работа №6. Решение систем линейных уравнений. 118

Решение систем линейных уравнений методом Гаусса. 118

Решение систем линейных уравнений методом Гаусса с выбором максимального элемента 126

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

Задания. 131

Лабораторная работа №7. Итерационные методы решения систем линейных уравнений. Приложения численных методов решения систем линейных уравнений. 133

Метод Зейделя. 133

Метод Гаусса-Зейделя. 142

Обращение матрицы nхn с использованием метода Гаусса. 151

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

Задания. 162

Лабораторная работа №8. Вычисление определенных интегралов. 164

Вычисление определенных интегралов методом прямоугольников. 164

Вычисление определенных интегралов методом трапеций. 168

Вычисление интеграла по методу Симпсона. 170

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

Задания. 177

Лабораторная работа №9. Численное решение дифференциальных уравнений. 179

Методы численного решения дифференциальных уравнений первого порядка. 179

Метод Эйлера. 179

Метод Кранка-Николсона. 183

Метод Рунге-Кутты четвертого порядка для решения уравнения первого порядка. 188

Методы численного решения систем дифференциальных уравнений. 194

Гармонические колебания. 194

Затухающие колебания. 195

Периодический процесс с затуханием и с внешней силой. 196

Решение системы дифференциальных уравнений методом Эйлера. 197

Решение системы дифференциальных уравнений первого порядка методом Рунге-Кутты 201

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

Задания. 209

Лабораторная работа №10. Генерация равномерных и неравномерных распределений случайных чисел 212

Использование гистограмм для отображения характера распределения случайной величины 212

Генератор дискретно-распределенных значений: 214

Генерация дискретных распределений с заданным характером распределения вероятностей 216

Генерация непрерывных распределений вещественных величин. 217

Псевдонормальное распределение. 217

Генерация линейно возрастающего распределения. 218

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

Задания. 223

Список рекомендуемой литературы и источников. 227

 

Задания

Вариант № 1

1. Написать программу для вывода на экран таблицы 23 значений функции f(x)=x*sin(x) на отрезке [-2,2].

2. Написать программу для умножения матрицы на вектор.

3. Написать программу – мини-калькулятор, которая запрашивает два числа с клавиатуры, вычисляет их сумму и выводит результат на экран.

4. Написать программу чтения из файла строки с заданным номером и выводящую результат на экран.

5. Написать программы шифрования и расшифровки файла методом циклического сдвига. Каждый символ исходного файла (исходный код – K1) заменяется на символ с ASCII-кодом K2, измененным на одну и ту же величину Delta (K2 = K1 + Delta). Причем, если в результате сдвига получается код K2 > 255, величина K2 изменяется на величину Delta1 = 255 – K1 – Delta.

6. Даны две dbf-таблицы – таблица со списком сотрудников некоторой организации с указанием ФИО, ИНН и таблица окладов сотрудников. Написать программу начисления заработных плат сотрудников, учитывая величину оклада для заданного числа рабочих дней в месяце. Результат должен быть выведен в отдельной dbf-таблице.

7. Написать программу, которая запрашивает число и определяет простое оно или нет.

8. Написать программу для вычисления определителя матрицы 4х4, используя разложение по строке и формулы для определителя матрицы 3x3.

Вариант № 2

1. Написать программу, которая запрашивает координаты точки – X и Y. Определить попадает ли эта точка в окружность с центром в точке (13,6) и радиусом 12.

2. Написать программу для сложения матриц.

3. Написать программу – мини-калькулятор, которая запрашивает два числа с клавиатуры, вычисляет их произведение и выводит результат на экран.

4. Даны N точек на плоскости (массив N координат точек). Найдите радиус круга, охватывающего все эти точки, и координаты центра круга. Координаты точек задать в dbf-таблице.

5. Написать программу шифрования и расшифровки файла с использованием ключевой строки. В этом методе каждый символ заменяется по правилу циклического сдвига на соответствующий код из ключевой строки.

6. Дан текстовый файл со списком сотрудников и их окладов. Найти и вывести три сотрудника с максимальными окладами из списка.

7. Написать программу, определяющую все простые числа, находящиеся в заданном диапазоне. Результат вывести в массив и распечатать этот массив на экран.

8. Написать программу, которая создает матрицу размерности NxN с элементами, значения которых соответствуют их индексам (образец для матрицы 4х4):

.

Вариант № 3

1. Написать программу, которая запрашивает координаты точки – X и Y. Определить, попадает ли эта точка в кольцо, образованное окружностями с центрами в точке (13,6) и радиусами 12 и 16.

2. Написать программу для умножения матриц.

3. Написать программу – мини-калькулятор, которая запрашивает два числа с клавиатуры, возводит их в квадрат и складывает, затем выводит результат на экран.

4. Дана dbf-таблица, содержащая N точек на плоскости образующих N-угольник. Найти величины всех углов этой фигуры в градусах и радианах.

5. Написать программу для преобразования строки, изображающей двоичное число (строка должна состоять из символов “1” и “0”) в строку, изображающую соответствующее шестнадцатеричное число. Например, двоичное число “00101001”, представляющее десятичное число 41, преобразуется в строку “29”.

6. В текстовом файле заданы координаты точек многоугольника. В каждой строке – координаты точек X и Y. Написать программу нахождения величин углов многоугольника. Результат представить в градусах.

7. Написать программу, которая анализирует тип и количество введенных параметров.

8. Написать программу, которая при помощи генератора случайных чисел заполняет матрицу размерности NxN элементами со значениями в интервале от –10 до 10. Преобразовать полученную матрицу по следующему алгоритму: элементы, со значениями больше 5, заменить на 1; элементы, со значениями меньше –5, заменить на –1; остальные элементы заменить на 0.

Вариант № 4

1. Написать программу, которая запрашивает на ввод два числа – координаты точки X и Y. Определить попадает ли эта точка в фигуру с углами в точках: (1,0) – (10,0) – (10,5) – (8,5) – (8,2) – (1,2).

2. Написать программу для вычисления определителя матрицы 2х2.

3. Написать программу – мини-калькулятор, которая запрашивает число с клавиатуры, вычисляет его квадрат и выводит результат на экран.

4. Дан dbf-файл – список сотрудников (N человек). Для каждого сотрудника известен оклад и коэффициент премии. Написать программу расчета премии для каждого сотрудника, если известна общая сумма, выделенная на премирование.

5. Дан текстовый файл, каждая строка которого состоит из фамилий и оклада заработной платы сотрудника, разделенных между собой разделителем ”;”. Написать программу нахождения максимального оклада, вывести фамилию и величину оклада сотрудника.

6. В текстовом файле даны координаты точек на плоскости. Найти минимальный радиус круга, который включат в себя все точки.

7. В налоговую инспекцию пришли данные о суммах, выплаченных сотрудникам из двух фирм (A и B) в виде dbf-таблиц, в каждой строке ФИО, ИНН и сумма. Получить файл – объединение списков A и B, причем при совпадении ИНН суммы складывать.

8. Написать программу, которая создает матрицу размерности NxN с элементами, значения которых соответствуют их индексам (образец для матрицы 4х4):

.

Вариант № 5

1. Написать программу для вычисления скалярного произведения векторов.

2. Написать программу для вычисления определителя матрицы 3х3.

3. Написать программу – мини-калькулятор, которая запрашивает число с клавиатуры, вычисляет значение какой либо функции от этого числа и выводит результат на экран.

4. Написать программу, выводящую из файла на экран строку с заданным номером.

5. Дан текстовый файл, каждая строка которого состоит из фамилий, оклада и з/п, разделенных между собой разделителем ”;”. Найти средний оклад.

6. Дан массив случайных чисел в dbf-файле. Написать программу сортировки массива по убыванию, вывести результат в текстовый файл.

7. В налоговую инспекцию пришли данные о суммах, выплаченных сотрудникам из двух фирм (A и B) в виде dbf-таблиц, в каждой строке ФИО, ИНН и сумма. Получить файл – разность списков А и В (т.е. вывести только те записи, которые встречаются в файле А, но не встречаются в файле В).

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

Примеры строк:

2+ 30

10 *5

В результате обработки файла создается файл-отчет с копиями этих строк, дополненных знаком равно и результатом операции

Пример:

10 + 12 = 22

Вариант № 6

1. Написать программу для вычисления векторного произведения векторов.

2. Написать программу для обращения матрицы 2х2.

3. Написать программу, которая запрашивает число-пароль, сравнивает его с заданным в программе и выводит в случае совпадения – “Молодец, угадал!”, в случае несовпадения – “Не угадал”.

4. Написать программу, создающую копию исходного текстового файла, которая перекодирует файл из исходной кодировки (например, cp-1251) в новую (например, cp-866).

5. Дан текстовый файл, каждая строка которого состоит из фамилий, оклада и з/п, разделенных между собой разделителем ”;”. Создать новый файл, в котором список упорядочен по фамилиям.

6. В текстовом файле хранится массив точек. Каждое число отделяется от другого разделителем (пробелом, точкой с запятой и т.д.). Считать эти точки в массив и вывести их на экран в виде: (x, y).

Пример 1: 23.15 4.5

Пример 2: 4.25;23.15;4.5

7. В налоговую инспекцию пришли данные о суммах, выплаченных сотрудникам из двух фирм (A и B) в виде dbf-таблиц со структурой (ФИО, ИНН, сумма). Получить файл – объединение списков A и B, причем при совпадении ИНН, суммы складывать.

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

Примеры строк:

(2 + 30/3)/6

10 * 5 + 12

В результате обработки файла-задания создайте файл-результат с копиями этих строк, завершенных знаком равно и результатом операции.

Пример:

(2 + 30/3)/6 = 2 или 10 * 5 + 12 = 62

Вариант № 7

1. Написать программу для вычисления скалярного произведения n-мерных векторов (n-мерный вектор a – это вектор с n координатами a=(a1,a2,…,an)).

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

3. Написать программу, которая запрашивает возраст человека, и, если введенное число отрицательно, выводит на экран сообщение – “Как же ты можешь работать на компьютере, если ты еще не родился.”. Если введенный возраст находится в интервале от 1 до 6 – “Рановато тебе еще глаза портить, иди лучше на улице побегай, если сможешь.”, и т.д. по нескольким возрастным группам.

4. Написать программу, создающую копию исходного текстового файла, которая перекодирует файл из исходной кодировки (например, cp-1251) в новую (например, koi-8r).

5. Дан текстовый файл, каждая строка которого состоит из фамилий, оклада, даты, разделенных между собой разделителем ”;”. Создать новый файл, в котором список упорядочен по окладам.

6. Задан массив точек в файле (каждая пара чисел - X и Y координат точек записываются в круглых скобках, отделяются друг от друга пробелом). Написать программу, считывающую эти точки в массив и вывести его на экран.

Пример: (2.34 3.15) (12.4 4.02) (20. 5.)

7. В головную организацию поступили отчеты из двух филиалов (A и B) в виде dbf-таблиц со структурой (код статьи расходов, сумма). Получить файл - отчет по головной организации – объединение отчетов филиалов (при совпадении кода статьи расходов суммы складываются).

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

Вариант № 8

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

2. Написать программу для определения действительных корней квадратного уравнения. Если дискриминант отрицательный – вывести сообщение, что действительных корней нет.

3. Написать программу, которая запрашивает на ввод с клавиатуры 6-тизначное число и если оно счастливое – выводит на экран сообщение “Это счастливое число” или “Не счастливое число” или “Это очень счастливое число” (если цифры расположены симметрично).

4. Написать программу, создающую копию исходного текстового файла, которая перекодирует файл из исходной кодировки (например, cp-1251) в новую (например, cp-866).

5. Дан текстовый файл, каждая строка которого состоит из фамилии, оклада (з/п) и отработанных дней в месяце разделенных между собой разделителем ”;”. Получить список, в котором рассчитан оклад за месяц для указанного количества рабочих дней в месяце.

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

7. Для выпуска некоторого изделия необходимо затратить N видов сырья, причем на одну единицу изделия приходится ai количество i-го сырья. На складе имеется bi количество i-го сырья. Сколько единиц продукции можно выпустить с данным запасом сырья, и какой вид сырья будет ограничивать выпуск продукции?

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

 

Вариант № 9

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

2. Написать программу для преобразования матрицы к треугольному виду.

3. Написать программу – мини-калькулятор, которая запрашивает два числа с клавиатуры, вычисляет их сумму и выводит результат на экран.

4. Написать программу, выводящую из файла на экран строку с заданным номером.

5. Написать программы шифрования и расшифровки файла методом циклического сдвига. Т.е. каждый символ исходного файла (исходный код – K1) заменяется на символ с ASCII-кодом K2 измененным на одну и ту же величину Delta (K2 = K1 + Delta). Причем, если в результате сдвига получается код K2 > 255, то величина изменяется на Delta1 = 255 – K1 – Delta.

6. Задан массив точек в файле, каждая пара чисел – X и Y координат точек записываются в круглых скобках, отделяются друг от друга пробелом считать эти точки в массив и вывести его в dbf-таблицу.

7. Создать dbf-таблицу для хранения структуры предприятия иерархического типа (предприятие имеет филиалы, которые, в свою очередь, также могут иметь дочерние подразделения). Реализовать процедуру печати всех дочерних филиалов заданного подразделения.

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

Вариант № 10

1. Написать программу, которая запрашивает на ввод два числа – X и Y координаты точки. Определить попадает ли эта точка в круг с центром в (10,5) и радиусом 10.

2. Написать программу для сложения матриц.

3. Написать программу – мини-калькулятор, которая запрашивает два числа с клавиатуры, возводит их сумму в 3 степень и выводит результат на экран.

4. Даны N точек на плоскости (N пар чисел - координат точек). Найдите радиус круга, охватывающего все эти точки, и координаты центра круга. Координаты точек задать в dbf-файле.

5. Написать программу шифрования и расшифровки файла с использованием ключевой строки. В этом методе каждый символ заменяется по правилу циклического сдвига на соответствующий код из ключевой строки.

6. Дан текстовый файл со списком сотрудников и их окладов. Найти три максимальных оклада из списка и вывести на экран.

7. Написать программу, определяющую все простые числа, находящиеся в заданном диапазоне, выводящую их в массив и распечатывающую этот массив на экран.

8. Создать матрицу генератором случайных чисел размерности (n,n), у которой над главной диагональю элементы принимают случайные значения от 0 до 3, под главной от 0 до –3, а элементы главной диагонали равны 0.

 

Задания

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

1. ln x + (x + 1)³ = 0;

2. x ×2 ^x = 1;

3. x – cos x = 0;

4. 3 x + cos x + 1 = 0;

5. x + lg x = 0,5;

6. 2 – x = ln x;

7. (2 – x)× e^x = 0;

8. 2,2× x – 2 ^x = 0;

9. x ² + 4 sin x = 0;

10. 2 x – lg x = 7;

11. 5 x – 8 ln x = 8;

12. 3× x – e ^x = 0;

13. x (x + 1)² = 1;

14. x = (x + 1)³;

15. x ² = sin x;

16. x ³ = sin x;

17. x ² = ln (x +1);

18. 2 x + lg x = – 0,5;

19. 2 x + cos x = 0,5;

20. sin 0,5 x +1 = x ²; x >0;

21. 0,5 x + lg (x –1) = 0,5;

22. sin (0,5 + x) = 2 x – 0,5;

23. lg (2 + x) +2 x = 3;

24. lg (1 + 2 x) = 2 – x;

25. 2 sin (x – 0,6) = 1,5 – x.

Задания

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

1. f (x)=(x+ 1)²/ (x –1)

2. f (x)=(x+ 1)³/ (x –1)²

3. f (x)=2 x ² – x ⁴

4. f (x)=0,1 x ³ – 2 x ² + 10 x

5. f (x)=(x ² + 1) /(x ‑ 1)

6. f (x)=0,4 x ³ – 3 x ² + 8 x

7. f (x)=0,1 x ³ – 2 +x ² ‑ 10 x

8. f (x)=(2 x ² + 1) / (x – 1)

9. f (x)= (x ² + 3) / (x ‑ 1)

10. f (x)= (2 x ² + 1) / (x ‑ 2)

11. f (x)=0,3 x ³ – 2 x ² + 6 x

12. f (x)= x ³ – 6 x ² + 9 x –4

13. f (x)= x (x –1)²(x– 2)

14. f (x)= x+ 1/ x

15. f (x)=2 x /(1 + x ²)

16. f (x)=(x ² – 3 x+ 2)/(x ² + 2 x+ 1)

17. f (x)=(2 x – x ²)^1/2

18. f (x)= x (x– 1) ^1/3

19. f (x)= xe ^{– x}

20. f (x)= x ^1/2 ln (x)

21. f (x)= xln ²(x)

22. f (x)=cos(x) + 0.5 cos(2 x)

23. f (x)=10/(1+sin² x)

24. f (x)= e^x sin(x)

25. f (x)= x ² – 4 x+ 6

26. f (x)=(5 – 4 x)^1/2

27. f (x)=3 x – x ³

28. f (x)=(x – 2)(x ² + 1)^1/2

29. f (x)=2 x – tg(x)

30. f (x)=(x + 2) e ^{1/ x}

31. f (x)=sin(x) + 1/3sin3 x

32. f (x)=(x ⁴ + 8)/(x ³ + 1)

33. f (x)=(x – 3) x ^1/2

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

1. z(x,y)= x ² + (y –1)²

2. z(x,y)= x ² – (y –1)²

3. z(x,y)=(x – y+ 1)²

4. z(x,y)= x ² – xy + y ²–2 x + y

5. z(x,y)= x ² y ³(6– x – y)

6. z(x,y)= x ³ + y ³–3 xy

7. z(x,y)= x ⁴ + y ⁴– x ²–2 xy – y ²

8. z(x,y)=2 x ⁴ + y ⁴– x ² –2 y ²

9. z(x,y)= x y +50/ x +50/ y

10. z(x,y)=1–(x ²+ y ²)^1/2

11. z(x,y)= (5–2 x + y)exp(x ²– y)

12. z(x,y)=(8 x ²–6 xy +3 y ²) exp(2 x +3 y)

13. z(x,y)=(5 x +7 y –25) exp(–(x ²+ xy + y ²))

14. z(x,y)= x ²+ xy + y ²–4ln x –10ln y

15. z(x,y)=sin x +cos y +cos(x – y)

16. z(x,y)=sin x sin y sin(x + y)

17. z(x,y)= xy ln(x ²+ y ²)

18. z(x,y)= x + y +4 sin x sin y

19. z(x,y)=(x ²+ y ²) exp(– (x ²– y ²))

20. z(x,y)= x ²+2 y ²–ln(x + y ²)

Задания

 

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

Рис.5

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

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

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

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

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

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

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

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

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

 

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

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

Математическоеописание бесконечнодробимых объектов уравнениями линий или поверхностей очень громоздко из-за большого количества мельчайших объектов. Для преодоления этой трудности математиком Исследовательского центра корпорации 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*t^n-1).

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

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

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

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

 

Рис. 12

Алгоритм:

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

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

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

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