Пример вычисления сложности алгоритма.
| Начало |
| N |
| X:= 1,N |
| F:= 5X2 + 3x - 2 |
| X, F |
| конец |
Для определения вида О-функции найдем количество
операций, выполняемых в цикле при данном значении N.
Один раз выполняется ввод N, цикл выполняется
N раз, при этом в цикле выполняется 7 операций.
Значит, общее количество операций
равно 1 + 7 N. Это количество линейно зависит от
значения N. Функция временной сложности
T(x) = 7N.
Значит, О-функция имеет вид О(N).
Используемая литература.
1 Шишковский С.А. Компьютерное моделирование. Методические указания для студентов заочной формы обучения, тема 1.5
2 Семакин И.Г., Шестаков А.П.Основы программирования», стр. 291-293.
Порядок выполнения работы
1. Переписать задание к работе в тетрадь.
2. Выполнить задание
3. Ответить на контрольные вопросы.
Содержание отчета
1. Наименование практической работы.
2. Цель работы.
3. Конкретное задание и его выполнение.
4. Ответы на контрольные вопросы.
Контрольные вопросы
1. Какие формы сложности алгоритмов вы знаете?
2. Что такое О-функция?
3. Какие бывают виды О-функций?
4. Что такое емкостная сложность алгоритма?
Варианты заданий к практическому занятию № 6
Вариант 1
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести длину окружности. Найти площадь круга, ограниченного этой окружностью и вывести ее на экран.
|
|
|
2. Вычислить значения функции f=4x2 - 8x - 5 для значений х=2,4,6,…, 2N в цикле с постусловием. Вывод значений функции делать в теле цикла. Значение N ввести с клавиатуры.
Вариант 2
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести с клавиатуры три целых числа А,В,С. Считая их сторонами треугольника, определить, является ли он прямоугольным и вывести об этом сообщение.
2. Посчитать в цикле с постусловием сумму натурального ряда чисел со значениями от 3 до N, вывести ее на экран со всеми промежуточными суммами. Значение N ввести с клавиатуры.
Вариант 3
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести с клавиатуры три целых числа А,В,С. Определить, какое из них равно числу D и вывести об этом сообщение. Если нет такого числа, то вывести «нет».
2. Посчитать в цикле с предусловием произведение четных чисел от 2 до N. Вывести на экран все значения произведений. Значение N ввести с клавиатуры.
Вариант 4
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести с клавиатуры два целых числа А и В. Перераспределить их так, чтобы в А оказалось меньшее из них, а в В – большее. Результаты вывести на экран.
|
|
|
2. В цикле с предусловием вычислить значение функции Y=2N путем умножения, построить таблицу всех промежуточных значений степени. Значение N ввести с клавиатуры.
Вариант 5
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести с клавиатуры три целых числа А,В,С. Определить, являются ли они сторонами треугольника. Если да, то найти площадь этого треугольника и вывести ее на экран.
2. Ввести матрицу из N строк и N столбцов и найти сумму ее элементов. Сумму вывести на экран. Значение N ввести с клавиатуры.
Вариант 6
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести с клавиатуры три целых числа А,В,С. Поменять их местами так, чтобы они оказались упорядоченными по возрастанию.
2. Ввести два целых числа А и В.Найти произведения всех чисел из диапазонов (1, 2, 3,, А) и (1, 2, …, В). Вывести на экран все произведения.
Вариант 7
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести с клавиатуры два радиуса R1 и R2. Посчитать для этих радиусов длины окружностей L1, L2 и площади кругов P1 и P2. Все величины вывести на экран.
3. Для значений 1, 2, 3, …N вывести на экран кубы этих чисел. Использовать цикл с предусловием. Значение N ввести с клавиатуры.
|
|
|
Вариант 8
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести площадь круга Р и площадь квадрата S. Определить, поместится ли квадрат в круге.
2. Вычислить факториал положительного числа N и вывести его на экран. Значение N ввести с клавиатуры.
Вариант 9
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести переменные х и у. Выяснить, находится ли точка с этими координатами в круге с радиусом 10 и центром в начале координат. Ответ дать в форме «находится в круге» или «не в круге».
2. Ввести массив из N чисел и посчитать количество отрицательных чисел. Вывести его на экран. Значение N ввести с клавиатуры.
Вариант 10
Составить блок-схемы алгоритмов и определить их сложность.
1. Ввести координаты двух точек А(х1, у1) и В(х2, у2), вычислить, какая из точек ближе к началу координат, вывести об этом сообщение. на экран.
2. Ввести матрицу из N строк и N столбцов и найти суммы элементов для каждой строки. Суммы вывести на экран. Значение N ввести с клавиатуры.
Дата добавления: 2016-01-03; просмотров: 13; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!