В рассмотрении циклического алгоритма следует выделить несколько понятий.
Тело цикла – это набор инструкций, предназначенный для многократного выполнения.
Итерация – это единичное выполнение тела цикла.
Переменная цикла – это величина, изменяющаяся на каждой итерации цикла.
Каждый цикл должен содержать следующие необходимые элементы:
- первоначальное задание переменной цикла,
- проверку условия,
- выполнение тела цикла,
- изменение переменной цикла.
Циклы бывают двух видов – с предусловием и с постусловием. В цикле с предусловием сначала проверяется условие входа в цикл, а затем выполняется тело цикла, если условие верно. Цикл с предусловием представлен на рис. 2.9. Цикл с предусловием также может быть задан с помощью счетчика. Это удобно в тех случаях, когда точно известно количество итераций.
В общем виде блок-схема, реализующая цикл с предусловием, представлена ниже. Сначала задается начальное значение переменной цикла, затем условие входа в цикл, тело цикла и изменение переменной цикла. Выход из цикла осуществляется в момент проверки условия входа в цикл, когда оно не выполняется, т.е. условие ложно. Цикл с предусловием может ни разу не выполниться, если при первой проверке условия входа в цикл оно оказывается ложным.
Блок схема. Программа примера
Рис. 2.9. Циклический алгоритм с предусловием в общем виде
В цикле с постусловием сначала выполняется тело цикла, а потом проверяется условие. Циклический алгоритм с постусловием представлен на рис. 2.10.
Рис. 2.10. Циклический алгоритм с постусловием в общем виде
Если условие верно, то итерация повторяется, если же неверно, то осуществляется выход из цикла. В отличие от цикла с предусловием, любой цикл с постусловием всегда выполнится хоть раз.
Примечание. Как видно из представленных блок-схем для циклов с предусловием и постусловием, условие записывается внутри блока условия (формы ромба), как и в разветвляющемся алгоритме. Принципиальная разница между разветвляющимся и циклическим алгоритмами при графической реализации состоит в том, что в циклическом алгоритме в обязательном порядке присутствует стрелка, идущая наверх. Именно эта стрелка обеспечивает многократный повтор тела цикла.
Приведем простейшие примеры, соответствующие циклическому алгоритму.
Пример 7. Вася звонит Пете, но у Пети может быть занята линия. Составить блок-схему действий Васи в этом случае.
Решение. Когда телефонная линия занята, то необходимо снова и снова набирать номер, пока Петя не закончит предыдущий разговор, и телефонная линия не окажется вновь свободной. Блок-схема представлена на рис. 2.11.
Алгоритм. Трассировка. Тестирование. Блок-схема|| информатика 8 класс
Рис. 2.11. Блок-схема для примера 7
Здесь тело цикла состоит из одного действия «Набрать номер Пети», т.к. именно это действие следует повторять, пока линия будет занята. Под итерацией цикла понимается очередная попытка дозвониться до Пети. Как таковой переменной цикла здесь нет, т.к. ситуация взята из жизни. Выход из цикла происходит в тот момент, когда условие «У Пети занято» стало неверным, т.е. телефонная линия свободна – действительно, нет необходимости больше набирать номер Пети. В данном примере применен цикл с постусловием, т.к. сначала необходимо набрать номер Пети, ведь иначе мы не можем ответить на вопрос – занята ли линия у Пети.
Пример 8. Ученику требуется купить учебник. Составить блок-схему, описывающую действия ученика в случае, если учебника нет в ряде магазинов.
Решение. Действия ученика в данном примере очевидны: когда он приходит в первый и любой последующий магазины, то возможны два варианта – учебник имеется в наличии или учебника нет в продаже.
Если учебника нет в продаже, то ученику следует пойти в другой книжный магазин и спросить данный учебник, и т.д. пока учебник не будет куплен, т.к. перед учеником стоит конечная цель – купить учебник. Мы будем использовать цикл с предусловием, т.к. сначала требуется найти магазин, имеющий в наличии данный учебник.
Цикл будет выполняться, пока условие «В данном магазине нет учебника» будет верным, а выход из цикла осуществится, когда условие станет ложным, т.е. когда ученик придет в магазин, в котором есть данный учебник. Действительно, в этом случае ученик купит нужный ему учебник и не будет больше искать книжные магазины. Результат блок-схемы представлен на рис. 2.12.
Рис. 2.12. Блок-схема для примера 8
Здесь тело цикла состоит из одного действия «Найти другой книжный магазин». Переменной цикла в явном виде нет, но можно подразумевать номер магазина, в который пришел ученик в очередной раз. Как любой другой цикл с предусловием, данный цикл может ни разу не выполниться (не иметь итераций), если в первом же магазине окажется нужный учебник.
Примечание. Если в данную задачу добавить условие выбора учебника в жесткой или мягкой обложке, как в примере 5, то оно появится после выхода из цикла. На реализацию циклического алгоритма данное условие не повлияет.
Пример 9. Даны числа 
. Известно, что число 
меняется от -10 до 10 с шагом 5, 
и не изменяется. Вычислить сумму 
и разность 
чисел 
и 
для всех значений и .
Решение. В отличие от примеров 3 и 6 здесь число меняется от -10 до 10 с шагом 5. Это означает, что число является переменной цикла. Сначала равно -10 – это первоначальное задание переменной цикла.
Далее будет изменяться с шагом 5, и т.д. пока не будет достигнуто значение 10 – это соответствует изменению переменной цикла. Итерации надо повторять, пока выполняется условие «
Итак, будет принимать следующие значения: -10, -5, 0, 5, 10. Число не будет являться переменной цикла, т.к. и не изменяется по условию задачи. Результат блок-схемы (с предусловием) представлен на рис. 2.13.
Рис. 2.13. Блок-схема для примера 9 (с предусловием)
Тело цикла состоит из нескольких действий: вычисление суммы, вычисление разности и вывод полученных данных на экран. Таким образом, у нас получится несколько значений сумм и разностей, т.к. изменяется. Количество сумм и количество разностей совпадет с количеством различных значений , т.е. пять.
Данная задача может быть сделана и с циклом с предусловием, и с постусловием. В этом случае тело цикла, условие и изменение переменной цикла будут такими же, как и в цикле с предусловием, но сначала необходимо выполнить тело цикла, а потом проверить условие для выполнения следующей итерации.
Приведем блок-схему, использующую цикл с постусловием, на рис. 2.14.
Рис. 2.14. Блок-схема для примера 9 (с постусловием)
В данной задаче также могут быть соединены циклический и разветвляющийся алгоритмы, если по условию задачи требуется сравнить полученные значения суммы и разности, как в примере 6. В этом случае цикл можно реализовать как с предусловием, так и с постусловием, а сравнение суммы и разности добавится внутрь тела цикла, т.к. следует сравнить между собой все полученные суммы и разности. Организация самого цикла останется прежней. Приведем на рис. 2.15а блок-схему с предусловием, а на рис. 2.15б блок-схему с постусловием.
Источник: intuit.ru
КР по ОАиП / алгоритмы и блок-схемы
1. АЛГОРИТМ Узнавать о новых алгоритмах и учиться их применять — важная часть программистского образования Говард Джонстон Понятие «алгоритм» происходит от имени математика из Хорезма Мухаммеда бен Муссу, которого в Европе знали под именем аль-Хорезми (лат. algorithmi), жившего в 783-850 гг. и сформулировавшего правила сложения чисел, названные в его честь алгоритмом. Алгоритм — конечная последовательность точно определенных действий (правил и команд), предназначенных для решения задачи. “Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер”, — Дональд Э. Кнут.
Примеры алгоритмов : правила сложения, умножения, деления, возведения в степень; решение уравнений; вычисление площади и объема фигуры и т.д. Алгоритм обладает следующими свойствами : дискретность – алгоритм состоит из отдельных шагов; конечность – завершение после определенного числа шагов; массовость – пригодность для решения широкого класса задач; понятность – однозначное понимание выполнения алгоритма. Для описания алгоритма следует: задать (ввести) исходные данные; определить правило обработки информации и получения результата; вывести результаты. Алгоритмы могут записываться : на естественном языке ( словесно — формульный способ описания); при помощи блок-схем ( структурный способ описания); с использованием специальных алгоритмических языков ; с помощью граф — схем (граф — совокупность точек и линий, в которой каждая линия соединяет две точки); с помощью сетей Петри . Перед составлением программ чаще всего применяют первый или второй способы записи алгоритмов. При словесно-формульном способе описания алгоритм записывается последовательно в виде текста с формулами.
Например , алгоритм решения квадратного уравнения a·x 2 +b·x+c=0 , где а≠0 , записывается следующим образом: 1. ввести значения коэффициентов a и b ; 2. найти дискриминант по формуле D = b 2 — 4·a·c ; 3. если дискриминант D > 0 , то уравнение имеет два корня :
| x b D | , x b D | ||||
| 1 | 2 a | 2 | 2 a | ||
4. если дискриминант D = 0 , то уравнение имеет один корень x b 2 a 5. если дискриминант D < 0 , то уравнение не имеет корней ; 6. вывести полученный результат. 1.1. Блок-схема алгоритма Благодаря своей наглядности данный способ записи алгоритмов получил наибольшее распространение.
При построении блок-схемы алгоритм изображается геометрическими фигурами (блоками), связанными линиями (направление потока информации) со стрелками. Внутри блоков записывается последовательность действий. В таблице 1 приведены виды и назначение основных блоков, применяемых для составления блок-схемы алгоритма. Таблица 1. Виды и назначение основных блоков
| Наименование | 0бозначение | Функции блока | |
| блока | блока | ||
| выполнение действий, | изменяющих | ||
| процесс | значение, форму представления или | ||
| расположение данных | |||
| ввод-вывод | ввод или вывод данных | ||
| выбор | направления | выполнения | |
| условие | алгоритма в зависимости от заданного в | ||
| блоке условия | |||
| предопределенный | вызов подпрограммы | ||
| процесс | |||
| Наименование | 0бозначение | Функции блока | |
| блока | блока | ||
| пуск-останов | начало или конец описания алгоритма | ||
| цикл с параметром; внутри блока | |||
| цикл с параметром | указывается | изменение | параметра |
| (переменной цикла), например , i=1,10 | |||
| внутристраничный | переход между блоками в пределах | ||
| соединитель | данной страницы | ||
| межстраничный | переход | между | блоками, |
| соединитель | расположенными на разных листах | ||
| комментарий | пояснение действий, указанных в блоке | ||
Правила оформления блок-схем: в пределах одной схемы блоки изображают одинаковых размеров ; все блоки нумеруются (номер ставится в верхнем левом углу блока с разрывом линии); линии , соединяющие блоки и указывающие последовательность связей между ними, проводятся параллельно линиям рамки; стрелка в конце линии не ставится , если линия направлена слева направо или сверху вниз ; из блока « условие » могут выходить две линии , из других блоков — только одна линия ; если схема занимает более одного листа , то в случае разрыва линии используется межстраничный соединитель ; внутри каждого соединителя указывается номер блока (откуда или куда направлена соединительная линия). Внутри межстраничного соединителя в первой строке указывается номер листа , во второй — номер блока куда или откуда передается управление. В зависимости от поставленной задачи выделяют три основных вида алгоритмов : линейный;
разветвляющийся; циклический. Линейным называется алгоритм, в котором все действия, указанные в блоках, выполняются по порядку их следования. Пример блок-схемы алгоритма вычисления площадей прямоугольника и квадрата (рис. 1.1). Рис.
1.1 Блок-схема линейного алгоритма Разветвляющимся называют алгоритм, в котором в зависимости от значения условия (выполняется или не выполняется) изменяется последовательность выполнения действий алгоритма. Пример блок-схемы алгоритма определения принадлежности точки с координатами (x, y) номеру сектора (рис. 1.2).
Рис. 1.2 Блок-схема разветвляющегося алгоритма Циклическим называется алгоритм, в котором некоторая последовательность действий повторяется определенное количество раз. Тело цикла – действия, выполняемые в цикле. Циклические алгоритмы могут быть: с предусловием – условие, при котором выполняется тело цикла, задается в начале цикла (рис.
1.3); с постусловием – условие, при котором выполняется тело цикла, задается в конце цикла (рис. 1.4); с параметром — в начале цикла задается правило изменения его параметра (рис. 1.5).
| Рис. 1.4 Цикл с | Рис. 1.5 Цикл с | |
| Рис. 1.3 Цикл с предусловием | постусловием | параметром |
Пример блок-схемы циклического алгоритма нахождения НОД (наибольшего общего делителя) двух значений a и b. Правило нахождения НОД (a, b) формулируется следующим образом: 1. определяется наибольшее из значений a и b — max (a, b); 2. из наибольшего значения вычитается оставшееся значение; 3. п.п. 1 и 2 повторяются до тех пор, пока значения a и b не станут равными. Полученное значение будет НОД (a, b).
| Решение : | ||
| Предположим, что a=20 и b=15. | ||
| Тогда: | ||
| max (a, b) = max (20, 15) = 20 | → a=20-15=5 | b=15 |
| max (a, b) = max (5, 15) = 15 | → a=5 | b=15-5=10 |
| max (a, b) = max (5, 10) = 10 | → a=5 | b=10-5=5 |
a = b => НОД (a, b) =5 Составим блок-схему алгоритма нахождения НОД (a, b) (рис. 1.6):
Рис. 1.6 Блок-схема алгоритма нахождения НОД (a, b). Для реализации алгоритма на компьютере необходимо описать его на языке программирования.
Источник: studfile.net
Примеры построения алгоритмов и их реализации на компьютере. Основные алгоритмические конструкции и их описание средствами языков программирования
Цели занятия: Усвоить понятия: алгоритм как фундаментальное понятие информатики, свойства алгоритмов, основные типы алгоритмов, изучить способы представления алгоритмов , научиться составлять алгоритмы в виде блок – схем, псевдокодов и на языке Паскаль .
Оборудование, программное обеспечение: ПК, ОС Windows
Методические рекомендации
Алгоритм — точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.
Основные свойства алгоритмов следующие:
Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.
Дискpетность (прерывность, раздельность) — т.е. алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).
Опpеделенность — т.е. каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.
Pезультативность (или конечность). Это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов.
Массовость. Это означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.
На практике наиболее распространены следующие формы представления алгоритмов:
— словесная (записи на естественном языке);
— графическая (изображения из графических символов);
— псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
— программная (тексты на языках программирования).
Решение любой задачи на ЭВМ можно разбить на следующие этапы: разработка алгоритма решения задачи, составление программы решения задачи на алгоритмическом языке, ввод программы в ЭВМ, отладка программы (исправление ошибок), выполнение программы на ПК, анализ полученных результатов.
Первый этап решения задачи состоит в разработке алгоритма.
Алгоритм может быть описан одним из трех способов:
· словесным (пример в начале раздела);
· графическим (виде специальной блок-схемы);
· с помощью специальных языков программирования.
Графическая форма записи, называемая также схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Графическая запись является более компактной и наглядной по сравнению со словесной. В схеме алгоритма каждому типу действий соответствует геометрическая фигура. Фигуры соединяются линиями переходов, определяющими очередность выполнения действий.
Графическая форма записи, называемая также структурной схемой или блок-схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
В дальнейшем мы будем использовать блок-схемы алгоритмов. Они позволяют представить алгоритмы в более наглядном виде, это дает возможность анализировать их работу, искать ошибки в их реализации и т.д. В блок-схемах всегда есть начало и конец, обозначаемые эллипсами, между ними — последовательность шагов алгоритма, соединенных стрелками.
Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно.
Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.
Блок «модификация» используется для организации циклических конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.
Блок «предопределенный процесс» используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам.
Блок-схема – распространенный тип схем, описывающий алгоритмы или процессы, изображая шаги в виде блоков различной формы, соединенных между собой стрелками.
1. Линейный алгоритм – это такой алгоритм, в котором все операции выполняются последовательно одна за другой.
2. Алгоритмы разветвленной структуры применяются, когда в зависимости от некоторого условия необходимо выполнить либо одно, либо другое действие.
3. Алгоритмы циклической структуры .
Циклом называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла.
Циклические алгоритмы подразделяют на алгоритмы с предусловием, постусловием и алгоритмы с конечным числом повторов. В алгоритмах с предусловием сначала выполняется проверка условия окончания цикла и затем, в зависимости от результата проверки, выполняется (или не выполняется) так называемое тело цикла.
Линейные алгоритмы
Линейный алгоритм – это алгоритм, в котором блоки выполняются последовательно сверху вниз от начала до конца.
На рисунке приведен пример блок-схемы линейного алгоритма вычисления периметра Р и площади S квадрата со стороной длины A.
Пример записи алгоритма в виде блок-схемы, псевдокодов и на языке Паскаль Вычислить среднее геометрическое чисел а и b .
Задание №1. Построить линейный алгоритм вычисления площади прямоугольника S=a · b. Записать алгоритмы в виде блок-схемы, в виде псевдокодов на алгоритмическом языке , а также на языке Паскаль.
Задание №2. Построить линейный алгоритм вычисления значения У по формуле
У=(7Х+4)(2Х-2) при Х=3.Составьте алгоритм самостоятельно, выделяя каждое действие как отдельный шаг. Записать алгоритмы в виде блок-схемы, в виде псевдокодов на алгоритмическом языке , а также на языке Паскаль.
Сделайте вывод о проделанной работе.
Контрольные вопросы:
1. Поясните понятие «алгоритм».
2. В чем состоит особенность описания алгоритмов с помощью структурной схемы и конструкций алгоритмического языка?
3. Перечислите типовые алгоритмические конструкции и объясните их назначение.
1. Информатика и ИКТ: учебник для начального и среднего профессионального образования. Цветкова Н.С., Великович Л.С. – Академия, 2011 г.
2. Информатика и ИКТ. Практикум для профессий и специальностей технического и социально-экономического профилей. Н. Е. Астафьева, С. А. Гаврилова, под ред. М.С. Цветковой, Академия, 2012г.
Источник: znanio.ru