Все типы алгоритмов. Типы алгоритмов. Какие бывают алгоритмы

Программирование - это записывание чего-то с использованием чужого малознакомого языка. С развитием этой области знания разработчики пошли еще дальше и научились записывать "что-то", даже не понимая, как оно звучит на русском языке. Новички учатся писать код сразу на C++ или php, используя множество библиотек, и толком даже не понимают, как то, что они создают, звучит на их родном языке. Алгоритмизация занимается разъяснением и доведением до понятного этого "что-то".

Алгоритмизация

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

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

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

Понятие алгоритма

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

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

1. Выбрать способ решения.
2. Изучить все детали выбранного способа.
3. Объяснить первые два пункта будущему исполнителю на понятном ему языке.

Затем можно будет давать исполнителю задания на решение квадратного уравнения. И если первые два шага просты и понятны - все способы решения описаны в соответствующей литературе, то третий шаг представляет сложность.

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

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

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

Основные свойства алгоритма

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

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

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

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

Возможности компьютера

Для правильного создания алгоритмов под компьютеры важно понимать их возможности. Рассмотрим сначала величины, с которыми работает ЭВМ. В общем случае их можно разделить на числовые и текстовые, постоянные и переменные.

Под постоянными числами понимаются все числа: 3,15, 100, 10 5 , их особенностью является неизменность в течение всей работы программы. Переменные величины меняют свое значение в ходе выполнения кода и обозначаются, как правило, буквами: x, y, max, min и т. д.

Текстовые переменные аналогично числовым бывают постоянными или переменными. В первом случае это просто текст: "хорошо", "a и b" и пр. Во втором - такое же символьное обозначение, как и числовых переменных: name, city и т. п. Отличие между ними заключается главным образом в выделяемой памяти компьютера под хранение такой переменной.

Операции, которые способен выполнять компьютер:

1. Считывать данные с устройств ввода (клавиатура, мышь, файлы).
2. Вычисление значений с использованием математические функции: сложение, вычитание, sin, cos, ln и т. д. - в каждом языке программирования свой набор встроенных функций.
3. Вывод данных (на экран, на бумагу, в сетевой интерфейс).
4. Переход между этапами выполнения программы.
5. Сравнение двух величин (больше, меньше, равно).

Это основные операции, которые могут выполняться большинством языков программирования.

Способы описания алгоритмов

Словесный. Это самый простой способ. Его примером может служить кулинарный рецепт. Допускается использование простых математических формул.

Графический. Описание с помощью схем. Это особый способ записи алгоритмов с использованием своего рода общепринятого алгоритмического языка - фигур и блоков, имеющих определенное значение: прямоугольник - простой действие, наклонный параллелограмм - ввод/вывод, ромб - условие и т. д.

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

алг заработная плата (int ST, real ZP) арг ST рез ZP начало если ST < 5 то zp = 150 иначе если ST <= 15 то ZP = 180 иначе ZP = 180 + (ST - 15)*10 конец

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

Виды алгоритмов

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

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

Это базовые виды. Стоит также отметить, что в ряде литературы выделяется еще и четвертый вид - рекурсивный. Но особого обозначения в схематической записи он не имеет и реализуется через базовые.

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

Принципы алгоритмизации

1. Определить исходные данные.
2. Выбрать способ решения.
3. Разбить выбранные способ на шаги исходя из возможностей компьютера (языка программирования).
4. Выполнить алгоритм в виде схемы, определив четкий порядок шагов.
5. Вывод результатов вычислений.
6. Обозначить переход к выходу схемы.

Отладка алгоритма

Человек допускает ошибки, и это факт. Главным параметром любого алгоритма должна быть правильность его работы. Отладка - это процесс выявления и исправления ошибок алгоритма. Для этого берется определенный набор исходных данных, называемых тестовыми. Они представляют собой, как правило, всевозможные типы исходных данных. Например, если на ввод подается число, то алгоритм следует проверить на корректную работу с учетом: положительных, отрицательных, целых и вещественных чисел, нулевые значения и т. п.

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

Линейные алгоритмы

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

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

Разветвляющиеся алгоритмы

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

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

Циклический алгоритм

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

1. Присваивание начального значения переменных. Без выполнения этого условия цикл, скорее всего, не сможет работать или будет совершать ошибки.
2. Блок вычисления результатов. Это основное тело цикла.
3. Проверка условия окончания циклического процесса. Если забыть указать условие, при котором следует завершить цикл, алгоритм будет выполняться бесконечно.
4. Изменение переменных. Этот блок вступает в силу после проверки условия окончания, если оно было ложным. Если забыть про этот блок, то цикл будет вечно выполнять одно действие и никогда не завершится. Поэтому важно, чтобы переменные претерпевали какие-либо изменения на каждой итерации цикла.

Существует несколько видов циклических алгоритмов: с постусловием, предусловием и параметром.

Построим циклический алгоритм на примере нахождения факториала числа N.

Другие типы алгоритмов

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

• Механические алгоритмы. Например, работа двигателя внутреннего сгорания или сборочного конвейера.
• Вероятностные алгоритмы. Их работа основана на теории вероятности и математической статистике.
• Эвристические алгоритмы. Используют практические соображения в своей работе, без строгого математического обоснования.
• Генетические алгоритмы. Применяют биологические идеи в своей работе.

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

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

Вообще, выполнение команд по алгоритму чем-то напоминает настольные игры, в которых участники по очереди бросают кубики и ходят по полям. Причем на полях могут быть комментарии в стиле: «Вернитесь на 2 клетки назад» или «Пройдите на 5 клеток вперед»

Более сложной моделью выполнения алгоритма является известная игра «Монополия» или «Менеджер»

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

В зависимости от порядка выполнения команд можно выделить три типа алгоритмов:

Линейные алгоритмы;

Алгоритмы с ветвлениями;

Алгоритмы с повторениями.

«Монополия»

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

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

Согласно официальным источникам – компании Parker Brothers, с 1935 года и по сей день выпускающей «Монополию», – легендарная настольная игра появилась на свет следующим образом. В 1934 году безработный инженер Чарльз Дарроу предложил вышеуказанной конторе выпустить придуманную им игру о торговле недвижимостью.

Обнаружив в настольной игре 52 дизайнерские ошибки, братья Паркеры отказали изобретателю. Тот с чисто американской предприимчивостью отправился в типографию, заказал 5 тысяч экземпляров игры и довольно быстро их распродал. Осознав, что прибыль утекает прямо у них из-под носа, Parker Brothers спешно приобрели права на «Монополию», и уже в следующем году она стала самой продаваемой настольной игрой в США, а Дарроу – живым воплощением американской мечты.

Однако вместе с тем известны и более ранние игры, поразительно напоминающие «Монополию». Выходит, Дарроу просто оказался первым, кто подсуетился и получил патент на «народную» забаву? И да, и нет. Расследования последних лет проливают свет на тайну происхождения «Монополии».

Во второй половине позапрошлого века в Соединенных Штатах жил и работал политэкономист Генри Джордж. Он предлагал заменить все поборы одним-единственным налогом – на землю. Проникшись его идеями, в январе 1904 года Мэги получает патент на настольную игру The Landlord’s Game, которая и правилами, и внешним видом напоминает нынешнюю «Монополию». Считается, что «Игра владельца земли» обладала двумя вариантами правил: сыграв партию по действующим законам налогообложения, игроки переходили к модели, предложенной Джорджем, – и якобы убеждались в ее необходимых преимуществах. Таким образом, игра была не развлечением, но инструментом идеологической борьбы.

До массового производства дело не дошло, зато The Landlord’s Game постепенно распространилась по Северной Америке в кустарных копиях. Всплеск интереса к настольной игре пришелся на годы Великой депрессии: тысячи безработных были рады вообразить себя денежными мешками хотя бы за игровым столом. Появление предприимчивого человека вроде Чарльза Дарроу стало делом нескольких месяцев – и он появился, на многие десятилетия присвоив славу единоличного изобретателя «Монополии».

Нашлись, конечно, и те, кто счел должным урвать кусок у правообладателей. Нелицензионные «Монополии» наводнили Китай. И в нашей стране выпускались и выпускаются стройные ряды клонов – «Маклер», «Кооператив», «Менеджер»

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

Линейные алгоритмы

Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.

Например, линейным является следующий алгоритм замены перегоревшей лампочки:

1. выключить выключатель света;

2. выкрутить перегоревшую лампочку;

3. вкрутить новую лампочку;

4. включить выключатель, чтобы проверить, что лампочка горит.

Алгоритмы с ветвлениями

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

Логику принятия решения можно описать так:

ЕСЛИ <условие>, ТО <действия 1>,

ИНАЧЕ <действия 2>

ЕСЛИ будут деньги, ТО купи хлеба, ИНАЧЕ не покупай.

ЕСЛИ будешь сегодня в центре, ТО набери меня, ИНАЧЕ не набирай.

ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.

В некоторых случаях <действия 2> могут отсутствовать. Это может быть связано как с его очевидностью (как, например, в первом примере – понятно, что если у тебя нет денег, то хлеба ты купить просто не сможешь), так и с отсутствием необходимости в нем.

ЕСЛИ <условие>, ТО <действия 1>

ЕСЛИ назвался груздем, ТО полезай в кузов.

ЕСЛИ хочешь быть здоров, ТО закаляйся.

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

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

Необходимые и достаточные условия

Мы уже обсуждали с вами, что существуют необходимые и достаточные условия.

Примером необходимого условия может служить такое:

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

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

Примером достаточного условия может стать такое:

Для того чтобы стало прохладнее, достаточно включить кондиционер.

Это условие является достаточным: если включить кондиционер, то действительно станет прохладнее. Однако это условие не является необходимым, ведь для достижения той де цели можно включить вентилятор, открыть окно и т. п.

Конечно же, существуют необходимые и достаточные условия одновременно (такие условия называются равносильными). Например:

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

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

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

Алгоритмы с повторениями

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

Например, если вам необходимо перебрать ящик с яблоками, чтобы отделить гнилые от спелых, то нам необходимо повторять следующие действия:

1. Взять яблоко.

2. Посмотреть, не гнилое ли оно.

3. Если гнилое – выбросить, если нет – переложить в другой ящик.

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

Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением).

Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием.

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

Рассмотрим алгоритм работы будильника на телефоне, который должен зазвонить в 8:00 утра, а затем звонить через каждые 10 минут, до тех пор пока его не выключат.

В этом случае его блок-схема выглядит так: (блок-схему (рис. 9.) см. в конце конспекта)

На этом уроке мы обсудили три типа алгоритмов – линейные алгоритмы, алгоритмы с ветвлениями и алгоритмы с повторениями.

На следующем уроке мы на практике обсудим составление алгоритмов.

Решето Эратосфена

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

Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число. Остальные числа называются составными. При этом число 1 не является ни простым, ни составным.

Примеры простых чисел: 2, 3, 5, 7.

Примеры составных чисел: 4, 6, 8.

В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа п:

1. выписать все натуральные числа от 1 до n;

2. вычеркнуть 1;

3. подчеркнуть наименьшее из неотмеченных чисел;

4. вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге числу;

5. если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые числа – простые.

Это циклический алгоритм. При его выполнении повторение шагов 3–5 происходит, пока в исходном списке остаются неотмеченные числа.

Рассмотрим результат этого алгоритма. Выпишем все простые числа от 1 до 25.

Выпишем числа от 1 до 25.

Вычеркнем 1. Теперь подчеркнем двойку. Вычеркнем все четные числа.

Так как не все числа отмечены, то подчеркиваем 3. Теперь вычеркиваем все числа, которые делятся на 3.

Так как не все числа отмечены, то подчеркиваем 5. Теперь вычеркиваем число 25.

Так как не все числа отмечены, то подчеркиваем 7.

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

Вычеркнуть ничего нельзя, но не все числа отмечены, поэтому подчеркиваем 13. Снова нельзя ничего вычеркнуть – подчеркиваем 17, затем 19 и 23.

Теперь все числа отмечены.

Получаем простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23.

Литература

1. Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2012.

2. Босова Л.Л. Информатика: Рабочая тетрадь для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2010.

3. Босова Л.Л., Босова А.Ю. Уроки информатики в 5-6 классах: Методическое пособие. – М.: БИНОМ. Лаборатория знаний, 2010.

Аннотация: Алгоритм является базовым понятием для тех, кто хочет начать программировать на любом языке программирования. Любая задача может быть формализована алгоритмически. Чтобы понять, с чего начать, рассмотрим основные виды алгоритмов. Цель данной лекции – ознакомить студентов с понятием алгоритма; показать, что такая абстрактная вещь как алгоритм окружает нас в повседневной жизни.

Пример псевдокода:

алг Нахождение частного двух чисел начало вывод ("задайте делимое и делитель") ввод (делимое, делитель) если делитель ≠ 0 то частное = делимое / делитель вывод(частное) иначе вывод("нет решения") кон алг Нахождение частного двух чисел

В данном примере используется три переменные: делимое, делитель и частное. Делимое и делитель задаются исполнителем произвольными числами. Частное считается лишь в том случае, если делитель не равен нулю.

Графическая реализация алгоритма представляет собой блок-схему. Блок-схема состоит из блоков определенной формы, соединенных стрелками. Ответ при этом получает человек, который выполняет команды согласно блок-схеме. Более подробно о блок-схемах будет рассказано в Лекции 2.

Программная реализация алгоритма – это компьютерная программа, написанная на каком-либо алгоритмическом языке программирования, например: С++, Pascal, Basic и т.д. Программа состоит из команд определенного языка программирования. Отметим, что одна и та же блок-схема может быть реализована на разных языках программирования. Ответ при этом получает ЭВМ, а не человек. Более подробно о составлении программ на языке программирования С++ смотреть Лекцию 3.

Различают три основных вида алгоритмов:

1. линейный алгоритм,
2. разветвляющийся алгоритм,
3. циклический алгоритм.

Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.

Самый простой пример реализации линейного алгоритма – путь из университета домой.

Словесный способ записи данного алгоритма:

1. выйти из университета на остановку;
2. подождать нужный автобус;
3. сесть на нужный автобус;
4. оплатить проезд;
5. выйти на требуемой остановке;
6. дойти до дома.

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

Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

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

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

Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.

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

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

Составьте алгоритм по нахождению корней квадратного уравнения через дискриминант. Используйте разветвляющийся алгоритм. Реализуйте его псевдокодом.

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

• Следование . Предполагает последовательное выполнение команд сверху вниз. Если алгоритм состоит только из структур следования, то он является линейным.
• Ветвление . Выполнение программы идет по одной из двух, нескольких или множества ветвей. Выбор ветви зависит от условия на входе ветвления и поступивших сюда данных.
• Цикл . Предполагает возможность многократного повторения определенных действий. Количество повторений зависит от условия цикла.
• Функция (подпрограмма) . Команды, отделенные от основной программы, выполняются лишь в случае их вызова из основной программы (из любого ее места). Одна и та же функция может вызываться из основной программы сколь угодно раз.

Описание различных алгоритмических структур на языке блок-схем

Ветвление if
Это самый простой тип ветвления. Если результат вычисления выражения-условия возвращает true (правда), то выполнение алгоритма идет по ветке «Да», в которую включены дополнительные выражения-действия. Если условие возвращает false (ложь), то выполнение алгоритма идет по ветке «нет», т.е продолжает выполняться основная ветка программы.

Ветвление if-else
Если выражение-условие возвращает true (правда), то выполнение алгоритма идет по ветке «Да», если условие не выполняется (false), то выполнение идет по ветке «Нет». При любом результате выражения-условия нельзя вернуться в основную ветку программы, минуя дополнительные действия.

Ветвление if-elif-else
Количество условий может быть различно. Если выполняется первое, то после выполнения действий, программа переходит к основной ветке, не проверяя дальнейшие условия. Если первое условие возвращает ложь, то проверяется второе условие. Если второе условие возвращает правду, то выполняются действия, включенные в вторую ветку конструкции. Последнее условие проверяется лишь в том случае, если ни одно до него не дало в результате true. Данную алгоритмическую конструкцию (if – elif – else) не следует путать с алгоритмической конструкцией «Выбор».

Цикл while
Пока условие выполняется (результат логического выражения дает true), будут выполняться действия тела цикла. После очередного выполнения вложенных действий условие снова проверяется. Для того чтобы выполнение алгоритма не зациклилось, в теле цикла (помимо прочих действий) должно быть выражение, в результате выполнения которого будет изменяться переменная, используемая в условии. Тело цикла может ни разу не выполнится, если условие с самого начала давало false.

Цикл do
В этом цикле первый раз условие проверяется лишь после выполнения действий тела цикла. Если условие возвращает true, то выражения-действия повторяются снова. Каким бы ни было условие, тело данного цикла хотя бы раз, но выполнится.

Цикл for
Данный цикл также называют циклом «Для» (for). В его заголовке указывается три параметра: начальное значение переменной (от), конечно значение (до) и ее изменение с помощью арифметической операции на каждом «обороте» цикла (шаг).