1. Определение алгоритма. 3 2. Свойства алгоритмов. 3 3. Способы описания алгоритма. 3 4. Базовые структуры блок-схем. 3 5. Структурированные блок-схемы и их построение. 3 6. Линейные и разветвляющиеся структуры; циклические структуры, типы циклов. 3 7. Предопределенные процессы. Рекрусия. 3 Задача 1……………………………………………………………………………..12 Задача 2 …………………………………………………………………………….14 Список литературы……………………………………………………...……….15
Определение алгоритма.
Алгоритм – это одно из фундаментальных понятий математики и вычислительной техники. Под алгоритмом понимают точное предписание, определяющее содержание и порядок действий, которые необходимо выполнить над исходными и промежуточными данными для получения конечного результата при решении всех задач определенного типа. Создание алгоритма, пусть даже самого простого – процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершить исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образуют систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
Свойства алгоритмов.
Понятность – каждая команда должна быть понятна исполнителю, т.е. входить в систему команд исполнителя. Дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего. Определенность – каждое правило алгоритма должно быть четким, однозначным. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче. Результативность – при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определённый результат. Вывод о том, что решения не существует - тоже результат. Массовость – алгоритм должен решать любую задачу из того класса задач, для решения которых он разработан. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Способы описания алгоритма.
Для описания алгоритмов существует множество способов. Основные способы описания следующие: - словесный; - формульно-словесный; - алгоритмический язык; - схема; - псевдокод. Словесное описание алгоритма рассмотрим на конкретном примере: необходимо найти корни квадратного уравнения: ах2 + bx + c = 0 (a ≠ 0): Вычислить D = b2 – 4ac; Если D < 0, перейти к 4 действию; Вычислить корни уравнения: x1, x2 = (- b ± √D)/2a; Конец. Здесь алгоритм описан с помощью естественного языка, а объекты обработки, которые являются числами, обозначены буквами. Формульно-словесный – задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями. Например, требуется вычислить площадь треугольника по 3 сторонам. п.1 – вычислить полупериметр треугольника p=(a+b+c)/2. К п.2. п.2 – вычислить S =√(p(p-a)(p-b)(p-c)) К п.3. п.3 – вывести S , как искомый результат и прекратить вычисления. При использовании этого способа может быть достигнута любая степень детализации, более наглядно, но не строго формально. Алгоритмический язык – набор символов и правил образования и истолкования конструкций их этих символов для записи алгоритмов. Под схемой программы будем понимать графическое представление последовательности шагов алгоритма, которое наглядно показывает очередность и взаимосвязь операций, осуществляемых в алгоритме на каждом его шаге. Иначе говоря, схема программы служит для графического изображения структуры алгоритма. Любая схема содержит набор геометрических фигур или блоков. Последовательность действий указывается с помощью стрелок, соединяющих отдельные блоки. Основные блоки, используемые при изображении схемы программы:
Блок, обозначающий начало или конец алгоритма.
Функциональный блок.
Логический блок.
Блок, обозначающий операции ввода-вывода.
Изображение цикла
Псевдокод - позволяет формально изображать логику программы, не заботясь при этом о синтаксических особенностях конкретного языка программирования. Обычно представляет собой смесь операторов языка программирования и естественного языка. Является средством представления логики программы, которое можно применять вместо блок-схемы.
Базовые структуры блок-схем.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур. Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем. Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем она настолько достаточна, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами. Базовые структуры (конструкции): - следование; - ветвление (полное и не полное); - повторение (цикл с предусловием или постусловием); - вход; -выход.
Структурированные блок-схемы и их построение.
Для повышения производительности и качества работы необходимо иметь данные, максимально приближенные к реальным аналогам. Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным. Каждый язык программирования имеет свои структурированные типы. Рассмотрим структуру, объединяющую элементы одного типа данных, — массив. Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность - «Ящик № 1», «Ящик № 2», «Ящик № З» и т.д.; «Ящик» - общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы. Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (аi) и геометрическая (bi) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив А(10)», это означает, что даны элементы: a1, a2, ... , а10 . Рассмотрим алгоритмы обработки элементов одномерных массивов. Ввод элементов одномерного массива осуществляется поэлементно, в порядке, необходимом для решения конкретной задачи. Обычно, когда требуется ввести весь массив, порядок ввода элементов не важен, и элементы вводятся в порядке возрастания их индексов.
Линейные и разветвляющиеся структуры; циклические структуры, типы циклов.
Доказано, что любую программу можно написать с использованием трех управляющих структур: - следования, или последовательности операторов; - ветвления, или условного оператора; - повторения, или оператора цикла. Программа, составленная из канонических структур, будет называться регулярной программой, т.е. иметь 1 вход и 1 выход, каждый оператор в программе может быть достигнут при входе через ее начало (нет недостижимых операторов и бесконечных циклов). Управление в такой программе передается сверху-вниз. Снабженные комментариями, такие программы хорошо читабельны. Следование Образуется последовательностью действий, следующих одно за другим:
Действия А и В могут быть: - отдельным оператором; - вызовом с возвратом некоторой процедуры; - другой управляющей структурой.
Ветвление Выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. «если – то - иначе»
Проверка P представляется предикатом, т.е. функцией, задающей логическое выражение или условие, значением которого может быть истина или ложь. Эта структура может быть неполной, когда отсутствует действие, выполняемое при ложном значении логического выражения. Тогда структура будет следующая: «если - то»
Повторение Практически все алгоритмы решения задач содержат циклически повторяемые участки. Цикл – это одно из фундаментальных понятий программирования. Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов: Цикл типа «пока». Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.
Цикл типа «для». Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
Предопределенные процессы. Рекрусия.
Предопределенными процессами называются процессы, определенные в системе заранее. Для языка С таким процессом является функция, имеющая прототип, то есть определенная и несущая сведения о своем существовании в систему до начала работы самой системы. Рекурсия – это способ организации вычислительного процесса, при котором подпрограмма в ходе производит вызов из раздела операторов самой себя. Рекурсивным называется обьект частично состоящий или определяемый с помощью самого себя. Рекурсия, как правило, применяется в тех случаях, когда основную задачу можно разбить на подзадачи той же структуры, что и первоначальная задача. Прямой рекурсией является вызов функции внутри тела этой функции. Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными. Особое внимание необходимо уделить корректному выходу из рекурсивной подпрограммы. Рекурсивный вызов подпрограммы должен управляться некоторым условием, которое в определенный момент перестает выполняться. Пока условие истинно, рекурсия повторяется, но как только условие становится ложным, начинается последовательный рекурсивный возврат из всех созданных копий подпрограммы. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом. По месторасположению условия входа из всех созданных копий рекурсивных подпрограмм: Тип 1 – с выполнением действий на рекурсивном спуске; Тип 2 – c выполнением действий на рекурсивном возврате; Тип 3 - с выполнением действий на рекурсивном спуске и возрате. Рекурсивные алгоритмы особенно подходят для задач, где обабатываемые данные определяются в терминах рекурсии. Однако это не означает, что рекурсивное определение данных гарантирует эффективность использования рекурсивных алгоритмов для решения таких задач.
Список литературы
Вирт Н. “Алгоритмы + структуры данных = программы”, Москва, Мир, 1985 г. Тимошевская Н.Е. «Программирование и основы алгоритмизации: Учеб. Пособие». - Томск: Том. гос.ун-т систем управления и радиоэлектроники, 2003. Аляев Ю.А., Козлов О.А. «Алгоритмизация и языки программирования Pascal, C++, Visual Basic: Учебно-справочное пособие». М.: Изд-во "Финансы и статистика", 2004. Окулов С.М. «Программирование в алгоритмах». М.: Изд-во "БИНОМ. Лаборатория знаний", 2004.
