|
|
Тема: «Разработка алгоритмов, использующих подпрограммы»Цель работы – изучить принцип построения алгоритмов, использующих подпрограммы. Теоретические сведения Часто в алгоритме имеются сходные алгоритмические структуры, отличающиеся только набором входных данных, к которым этот алгоритм применяется. Для записи таких схожих алгоритмических структур применяют подпрограммы (или вспомогательный алгоритм). Вспомогательный алгоритм является аналогом языковой подпрограммы. Он имеет имя и может иметь параметры, которые называются формальными параметрами. Имя служит для того, чтобы отличить его от других алгоритмов, а формальные параметры, которые напоминают переменные математических функций, выполняют роль входных и выходных параметров. Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан весь набор необходимых входных и выходных величин. Нередко один и тот же параметр может оказаться входным и выходным одновременно. Например, на вход такого алгоритма может быть подан массив для обработки, а на выходе процедуры он может предстать в измененном виде как выходной параметр. Пример вызова подпрограммы приведен на рис.10.1.
Рисунок 10.1 – Блок вызова подпрограммы
На рис.10.2а представлен пример оформления алгоритма подпрограммы, включающий имя процедуры Warn и один формальный параметр i. Программа рис.10.2б обращается к подпрограмме рис.10.2а.
а) б) Рисунок 10.2 – Пример определения процедуры (а) и ее вызова (б) Индивидуальные задания 1) Создайте алгоритм поиска большего из четырех чисел с использованием подпрограммы поиска большего из двух чисел. 2) Даны координаты вершин многоугольника (x1, y1,x2,y2,…x10,y10). Создайте алгоритм вычисления его периметра (вычисление расстояния между вершинами оформить подпрограммой). 3) Создайте алгоритм вычисления числа сочетаний из N по M. Число сочетаний определяется по формуле N!/(M!*(N-M)!, где N – количество элементов перебора. Используйте подпрограмму вычисления факториала. 4) Создайте алгоритм определения НОД трех натуральных чисел, используя подпрограмму. 5) Даны действительные числа s, t. Создайте алгоритм вычисления выражения f(t, -2s, 1.17) + f(2.2, t, s-t), где f(a,b,c) = (2a – b – sin(c)) / (5 + |c|), используя подпрограмму. 6) Даны натуральные m и n (m<n). Создайте алгоритм, сокращающую дробь m/n, используя подпрограмму. 7) Создайте алгоритм вычисления суммы квадратов простых чисел, лежащих в интервале (M,N), используя подпрограмму. 8) Создайте алгоритм подсчета числа четных цифр, используемых в записи N-значного числа M, используя подпрограмму. 9) Создайте алгоритм вычисления суммы трехзначных чисел, в десятичной записи которых нет четных цифр, используя подпрограмму. 10) Создайте алгоритм вывода на экран всех натуральных чисел, не превосходящих N и делящихся на каждую из своих цифр, используя подпрограмму. 11) Создайте алгоритм нахождения наименьшего натурального N-значного числа X (X>=10), равного утроенному произведению своих цифр, используя подпрограмму. 12) Создайте алгоритм подсчета числа всех натуральных чисел, меньших М, квадрат суммы цифр которых равен X, используя подпрограмму. Контрольные вопросы 1) Дайте определение понятиям процедура и функция. 2) Укажите основные отличия процедур от функций. 3) Как отображаются процедуры и функции при описании алгоритмов? 4) Приведите пример использования процедуры.
ЛАБОРАТОРНАЯ РАБОТА № 11 Тема: «Определение функции сложности алгоритмов» Цель работы – изучить принцип определения функции сложности алгоритма. Теоретические сведения Функция сложности алгоритма Эффективность программы является очень важной ее характеристикой. Эффективность программы имеет две составляющие: память (или пространство) и время. Пространственная эффективность измеряется количеством памяти, требуемой для выполнения программы. Компьютеры обладают ограниченным объемом памяти. Если две программы реализуют идентичные функции, то та, которая использует меньший объем памяти, характеризуется большей пространственной эффективностью. Временная эффективность программы определяется временем, необходимым для ее выполнения. Лучший способ сравнения эффективностей алгоритмов состоит в сопоставлении их порядков сложности. Этот метод применим как к временной, так и пространственной сложности. Порядок сложности алгоритма выражает его эффективность обычно через количество обрабатываемых данных. Например, некоторый алгоритм может существенно зависеть от размера обрабатываемого массива. Если, скажем, время обработки удваивается с удвоением размера массива, то порядок временной сложности алгоритма определяется как размер массива. Порядок алгоритма — это функция, доминирующая над точным выражением временной сложности. Функция f(n) имеет порядок O(g(n)), если имеется константа Ки счетчик n0 такие, что f(n)(K*g(n))для n > n0. Алгоритм имеет сложность O(f(N)), если с увеличением размерности исходных данных N время выполнения алгоритма возрастает с той же скоростью, что и функция f (N). Функция сложности O выражает относительную скорость алгоритма в зависимости от некоторой переменной (или переменных). Существуют три важных правила для определения функции сложности: 1) O(к*f) = O(f) 2) O(f*g) = O(f)* O(g) или O(f/g) = O(f)/O(g). 3) O(f+g) равна доминанте O(f) и O(g). Здесь «к»обозначает константу, а f и g — функции. Первое правило декларирует, что постоянные множители не имеют значения для определения порядка сложности O(1,5*N)=O(N). Из второго правила следует, что порядок сложности произведения двух функций равен произведению их сложностей O((17*N)*N)=O(17*N)*O(N)=O(N)*O(N)=O(N*N)= O(N2). Из третьего правила следует, что порядок сложности суммы функций определяется как порядок доминанты первого и второго слагаемых, т. е. выбирается наибольший порядок O(N5 + N2) = O(N5). 11.2 Виды функции сложности алгоритмов O(I) В алгоритмах константной сложности большинство операций в программе выполняются один или несколько раз. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность. 1) O(N). Время работы программы линейно, обычно, когда каждый элемент входных данных требуется обработать лишь линейное число раз. 2) O(N2), O(N3),O(Na).Полиномиальная сложность. O(N2) — квадратичная сложность, O(N3) — кубическая сложность 3) O(Log(N)). Когда время работы программы логарифмическое, программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему на маленькие и решают их по отдельности. 4) O(N*log(N)). Такое время работы имеют те алгоритмы, которые делят большую проблему на маленькие, а затем, решив их, соединяют их решения. 5) O(2n). Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода, именуемого методом грубой силы.   Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
