Ивная работа по информатике (стр. 3 из 3)

пока условие, повторять:

нц

серия

кц

Выполнение серии команд (тела цикла) повторяется, пока условие цикла истинно. Когда условие становится ложным, цикл заканчивает выполнение. Служебные слова нц и кц обозначают начало цикла и конец цикла соответственно. Цикл с предусловием - это основная, но не единственная форма организации циклических алгоритмов. Другим вариантом является цикл с постусловием. Вернемся к алгоритму решения квадратного уравнения. К нему можно подойти с такой позиции: если а = 0, то это уже не квадратное уравнение и его можно не рассматривать. В таком случае будем считать, что пользователь ошибся при вводе данных, и следует предложить ему повторить ввод. Иначе говоря, в алгоритме будет предусмотрен контроль достоверности исходных данных с предоставлением пользователю возможности исправить ошибку. Наличие такого контроля - еще один признак хорошего качества программы (рис. 14). В общем виде структурная команда цикл с постусловием или цикл—до представляется на рис. 15. Здесь используется условие окончания цикла. Когда оно становится истинным, цикл заканчивает работу. Составим алгоритм решения следующей задачи: даны два натуральных числа М и N. Требуется вычислить их наибольший общий делитель — НОД(М, N). Эта задача решается с помощью метода, известного под названием алгоритма Евклида. Его идея основана на том свойстве, что если M > N, то НОД(М, N) = НОД(М — N,N). Другой факт, лежащий в основе алгоритма, тривиален НОД(М, M) = М. Для «ручного» выполнения этот алгоритм можно описать в форме следующей инструкции:

1. Если числа равны, то взять их общее значение в качестве ответа; в противном случае продолжить выполнение алгоритма. 2. Определить большее из чисел. 3. Заменить большее число разностью большего и меньшего значений. 4. Вернуться к выполнению пункта 1.

Блок-схема и алгоритм на АЯ будут на рис. 16.

4. Вспомогательные алгоритмы и процедуры

В теории алгоритмов известно понятие вспомогательного алгоритма. Вспомогательным называется алгоритм решения некоторой подзадачи из основной решаемой задачи. В таком случае алгоритм решения исходной задачи называется основным алгоритмом. Пример. Требуется составить алгоритм вычисления степенной функции с целым показателем у = хk, где k - целое число, х ≠ 0. В алгебре такая функция определена на рис. 17. Для данной задачи в качестве подзадачи можно рассматривать возведение числа в целую положительную степень. Условие: 1/х-n = (1/х) -n, основной алгоритм решения этой задачи на рис. 18. Здесь дважды присутствует команда обращения к вспомогательному алгоритму с именем СТЕПЕНЬ. Это алгоритм возведения вещественного основания в целую положительную степень путем его многократного перемножения. Величины, стоящие в скобках в команде обращения к вспомогательному алгоритму, называются фактическими параметрами. В учебном алгоритмическом языке вспомогательные алгоритмы оформляются в виде процедур. На АЯ процедура СТЕПЕНЬ выглядит как на рис. 19. Заголовок вспомогательного алгоритма начинается со слова «процедура», после которого следует имя процедуры и в скобках - список формальных параметров. В этом списке перечисляются переменные-аргументы и переменные-результаты с указанием их типов. Здесь а и k - формальные параметры-аргументы, z - параметр-результат. Следовательно, процедура степень производит вычисления по формуле z = аk. В основном алгоритме «Степенная функция» обращение к процедуре производится путем указания ее имени с последующим в скобках списком фактических параметров. Между формальными и фактическими параметрами процедуры должны выполняться следующие правила соответствия:

• по количеству (сколько формальных, столько и фактических параметров); • по последовательности (первому формальному соответствует первый фактический параметр, второму — второй и т.д.); • по типам (типы соответствующих формальных и фактических параметров должны совпадать).

Фактические параметры-аргументы могут быть выражениями соответствующего типа. Обращение к процедуре инициирует следующие действия:

1. Значения параметров-аргументов присваиваются соответствующим формальным параметрам. 2. Выполняется тело процедуры (команды внутри процедуры). 3. Значение результата передается соответствующему фактическому параметру, и происходит переход к выполнению следующей команды основного алгоритма.

В процедуре степень нет команд ввода исходных данных и вывода результатов. Здесь присваивание начальных значений аргументам (а, п) производится через передачу параметров-аргументов. А присваивание результата переменной (у) происходит через передачу параметра-результата (z). Таким образом, передача значений параметров процедур - это третий способ присваивания (наряду с командой присваивания и командой ввода). Использование процедур позволяет строить сложные алгоритмы методом последовательной детализации.

5. Использование циклов с параметром для обработки массивов.

Массив - упорядоченная структура, предназначенная для хранения однотипных данных. Упорядочение элементов в массиве происходит по их индексам. Индекс - порядковый номер элемента. Массив задается именем (заглавные латинские буквы), типом данных и размерностью. Размерность - максимально возможное количество элементов в массиве. В один момент времени можно обратиться только к одному элементу массива. Для этого указывается имя массива и в скобках индекс элемента. Массивы делятся на одномерные (линейные) и двумерные. Прообразом в математике для одномерного массива является вектор. Для двумерного - матрица.

ЗАКЛЮЧЕНИЕ

Алгоритм может быть записан словами и изображён схематически. Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, машинный код). Например, для описания алгоритма применяются блок-схемы. Другим вариантом описания, не зависимым от языка программирования, является псевдокод. Хотя в определении алгоритма требуется лишь конечность числа шагов, требуемых для достижения результата, на практике выполнение даже хотя бы миллиарда шагов является слишком медленным. Также обычно есть другие ограничения (на размер программы, на допустимые действия). В связи с этим вводят такие понятия как сложность алгоритма (временна́я, по размеру программы, вычислительная и др.). Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики. В 50-х гг. XX века появилась даже отдельная её область — быстрые алгоритмы. В частности, в известной всем с детства задаче об умножении десятичных чисел обнаружился ряд алгоритмов, позволяющих существенно ускорить нахождение произведения.

ПРИЛОЖЕНИЯ

Рис. 1

Рис. 2

Рис. 3

Рис. 4

Рис. 5

Рис. 6

Рис. 7

Рис. 8

Рис. 9

Рис. 10

Рис. 11

Рис. 12

Рис. 13

Рис. 14

Рис. 15

Рис. 16

Рис. 17

Рис. 18

Рис. 19

Табл. 1

Табл. 2.1

Таб. 2.2

Таб. 3

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. 2-е изд. М.: Вильямс, 2006. с. 1296 2. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. 3-е изд. М.: Вильямс, 2006. с. 720. 3. Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. М.: «Вильямс», 2007. с. 480 4. Н.А. Криницкий. Алгоритмы вокруг нас. М.: Наука, 1977. с. 224 5. Касаткин В. Н. Информация, Алгоритмы ЭВМ. М.: Просвещение, 1991. с. 192