Файл: «Алгоритмизация как обязательный этап разработки программы».pdf

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

Блок « решение» используется для обозначения переходов управления по условию. В каждом таком блоке должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок « модификация - видоизменение, преобразование» используется для организации циклических структур. Внутри блока записывается параметр цикла, для которого указывается его начальное значение, граничное условие и шаг изменения параметра цикла для каждого повторения.

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

Программы, написанные на языке программирования, можно также рассматривать в качестве форм представления алгоритмов.

Современное программирование в отличие от классической теории алгоритмов стремится предоставить разработчику реальных алгоритмов богатый арсенал мощных и разнообразных средств, как для представления информации, так и для выражения процессов ее обработки. Стремление избавить пользователя от излишней детализации и кодировки при составлении программ привело к появлению целого семейства алгоритмических языков высокого уровня. Этот процесс продолжает бурно развиваться и является определяющим фактором современного программирования [26, с.117].

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

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

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

Например, язык ЛИСП опирается на идею реализации алгоритмов как последовательностей вычислений рекурсивных функций. Другой язык программирования - РЕФАЛ использует «универсальный» алгоритмический язык в виде схем нормальных алгоритмов Маркова, а в основе языка ПРОЛОГ лежит модель, заимствованная из логики предикатов первого порядка.

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

Язык большинства современных ЭВМ достаточно беден и состоит из команд типа «выделить память определенного размера»; «выбрать из определенного места в памяти информацию»; «запомнить информацию в определенном месте памяти»; «сложить два числа»; «перейти к выполнению очередной команды, выбрав ее из определенного места в памяти» и т. п.

Как правило, команд - несколько сотен. Все они настолько просты, что могут быть эффективно реализованы аппаратурой. Набор команд функционально полон, и, в принципе, используя команды из этого набора (в программировании говорят, пользуясь заданной системой команд), можно описать любой алгоритм [15, с.45].

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

Существует лишь два выхода из этого положения. Первый из них связан с созданием более сложных ЭВМ и, вследствие этого, с аппаратурой поддержки более мощных языков.

Второй путь - программное моделирование более мощного входного языка. Такой прием в программировании называют созданием виртуальной вычислительной машины, состоящей частично из аппаратуры, а частично из программного обеспечения. На практике обычно создается иерархия виртуальных ЭВМ, где каждый следующий уровень позволяет программисту использовать все более и более мощный входной язык. При этом конечно, требуются специальные программы-переводчики (трансляторы), функция которых - преобразование программ на входном языке виртуальной машины в эквивалентные программы, понимаемые аппаратурой ЭВМ.

Такая трансляция может быть одношаговой или многошаговой, в зависимости от числа уровней в иерархии виртуальных ЭВМ.

Уже разработаны тысячи языков программирования, но лишь сотни из них реализованы хотя бы для одной ЭВМ. Однако даже среди этих сотен языков активно используются лишь несколько десятков.

Основные алгоритмические конструкции.

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

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

Рис.1. Блок «один вход и один выход»

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

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

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

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

Команда следования состоит только из простых команд. На рисунке простые команды имеют условное обозначение S1 и S2. Из команд следования образуются линейные алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел, введенных с клавиатуры.

Рис.3. Команда ветвления

Команда ветвления - это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1, или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры.

Рис.4. Неполная форма команды ветвления

Команда ветвления может быть полной и неполной формы. Неполная форма команды ветвления используется тогда, когда необходимо выполнять действие S только в случае соблюдения условия P. Если условие P не соблюдается, то команда ветвления завершает свою работу без выполнения действия. Примером команды ветвления неполной формы будет уменьшение в два раза только четного числа.

Рис.5. Команда повторения

Команда повторения - это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S. Из команд следования и команд повторения составляются циклические алгоритмы (алгоритмы повторения). На рисунке представлена команда повторения с предусловием. Называется она так потому, что вначале проверяется условие, а уже затем выполняется действие. Причем действие выполняется, пока условие соблюдается. Пример циклического алгоритма может быть следующий. Пока с клавиатуры вводятся положительные числа, алгоритм выполняет нахождение их суммы [23, с.77].

Команда повторения с предусловием не является единственно возможной. Разновидностью команды повторения с предусловием является команда повторения с параметром. Она используется тогда, когда известно количество повторений действия. В блок-схеме команды повторения с параметром условие записывается не в ромбе, а в шестиугольнике. Примером циклического алгоритма с параметром будет нахождение суммы первых 20 натуральных чисел.

Рис.6. Выполнение действия S и проверка условия P

В команде повторения с постусловием вначале выполняется действие S и лишь затем, проверяется условие P. Причем действие повторяется до тех пор, пока условие не соблюдается. Примером команды повторения с постусловием будет уменьшение положительного числа до тех пор, пока оно неотрицательное. Как только число становится отрицательным, команда повторения заканчивает свою работу [24, с.71].

С помощью соединения только этих элементарных конструкций (последовательно или вложением) можно "собрать" алгоритм любой степени сложности.

Рис.7. Способы соединения базовых структур алгоритма

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

Таким образом, можно сделать вывод, что понятие алгоритма - одно из основных в программировании и информатике.

Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу.

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

Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» - почти синонимы.

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

2.1 Алгоритмизация как обязательный этап в разработке программного

обеспечения

Алгоритм Евклида - эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».

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

Первое описание алгоритма находится в «Началах Евклида» (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако, в 19 веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как «Евклидово кольцо». Позже алгоритм Евклида также был обобщен на другие математические структуры, такие как узлы и многомерные полиномы [17, с.90].

Для данного алгоритма существует множество теоретических и практических применений. В частности он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений, при построении непрерывных дробей, в методе Штурма. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например, таких как «теорема Лагранжа о сумме четырёх квадратов» и «основная теорема арифметики».

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις - «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды - в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.