НТВ плюс 

Алгоритмы. Понятие и виды алгоритма. Блок-схемы. Алгоритмические структуры (типы алгоритмов)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Понятие

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

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

    Свойства

    Прежде чем рассматривать в информатике, необходимо выяснить их основные свойства.

    Среди основных свойств алгоритмов необходимо выделить следующие:

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

    Способы записи

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

    1. Словестный.
    2. Формульно-словестный.
    3. Графический.
    4. Язык алгоритма.

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

    Основные виды

    Выделяют три основных схемы:

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

    Линейный

    Наиболее простым в информатике считается Он предполагает последовательность выполнения действий. Приведем наиболее простой пример алгоритма такого вида. Назовем его «Сбор в школу».

    1. Встаем, когда звенит будильник.

    2. Умываемся.

    3. Чистим зубы.

    4. Делаем зарядку.

    5. Одеваемся.

    6. Кушаем.

    7. Обуваемся и идем в школу.

    8. Конец алгоритма.

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

    Рассматривая виды алгоритмов в информатике, нельзя не вспомнить о разветвляющейся структуре. Данный вид предполагает наличие условия, при котором в случае его выполнения действия выполняются в одном порядке, а в случае невыполнения - в другом.

    Например, возьмем следующую ситуацию - переход дороги пешеходом.

    1. Подходим к светофору.

    2. Смотрим на сигнал светофора.

    3. Он должен быть зеленым (это условие).

    4. Если условие выполняется, мы переходим дорогу.

    4.1 Если нет - ждем, пока загорится зеленый.

    4.2 Переходим дорогу.

    5. Конец алгоритма.

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

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

    Возьмем простой пример. Если ряд чисел от 1 до 100. Нам необходимо найти все то есть те, которые делятся на единицу и себя. Назовем алгоритм «Простые числа».

    1. Берем число 1.

    2. Проверяем, меньше ли оно 100.

    3. Если да, проверяем простое ли это число.

    4. Если условие выполняется, записываем его.

    5. Берем число 2.

    6. Проверяем, меньше ли оно 100.

    7. Проверяем, простое ли оно.

    …. Берем число 8.

    Проверяем, меньше ли оно 100.

    Проверяем, простое ли число.

    Нет, пропускаем его.

    Берем число 9.

    Таким образом перебираем все числа, до 100.

    Как видите, шаги 1 - 4 будут повторяться некоторое число раз.

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

    Другие варианты

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

    Обозначения в блок-схеме

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

    1. Начало и конец алгоритма записываются в овальной рамке.
    2. Каждая команда фиксируется в прямоугольнике.
    3. Условие прописывается в ромбе.
    4. Все части алгоритма соединяются при помощи стрелок.

    Выводы

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

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

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

    Вообще, выполнение команд по алгоритму чем-то напоминает настольные игры, в которых участники по очереди бросают кубики и ходят по полям. Причем на полях могут быть комментарии в стиле: «Вернитесь на 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.

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

    · словесная (записи на естественном языке);

    · графическая (изображения из графических символов);

    · псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

    · программная (тексты на языках программирования).

    Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

    Алгоритм может быть следующим:

    · задать два числа;

    · если числа равны, то взять любое из них в качестве ответа и остановиться, в

    противном случае продолжить выполнение алгоритма;

    · определить большее из чисел;

    · заменить большее из чисел разностью большего и меньшего из чисел;

    · повторить алгоритм с шага 2.

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

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

    · такие описания строго не формализуемы;

    · страдают многословностью записей;

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

    Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

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

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

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

    1)Блок начало-конец

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

    2) Блок действия

    Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания: a = 10*b + c


    3) Логический блок

    Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).

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

    Типы алгоритмов

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

    Линейный алгоритм - набор команд (указаний), выполняемых последовательно во времени друг за другом.

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

    Цель: Ознакомить студентов с основами алгоритмизации.

    Учебные вопросы:

    1. Алгоритм и его свойства. Способы записи алгоритмов.

    2. Основные типы алгоритмов. Блок-схемы типовых алгоритмов.

    Изучив данную тему, студент должен:

    Знать:

    · свойства алгоритма;

    · блоки для построения схем;

    · основные типы алгоритмов;

    Уметь :

    · строить алгоритмы по условию задачи;

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

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

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

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

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

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

    Алгоритм может быть представлен различными способами, в частности:

    1) словесно (вербальное описание);

    2) таблично;

    3) в виде блок-схемы;

    4) на алгоритмическом языке.

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

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

    Предпочтительнее до записи на алгоритмическом языке представить алгоритм в виде блок-схемы. Для построения алгоритма в виде блок-схемы необходимо знать назначении каждого из блоков. В таблице 13. приводятся типы блоков и их назначение.

    Таблица 13

    Назначение блока

    Комментарий

    {блоку соответствует оператор}

    Начало или конец

    блок-схемы

    Ввод или вывод данных

    ввода / вывода

    Процесс (в частности вычислительный)

    присваивания

    Модификатор цикла

    5.2. Основные типы алгоритмов

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

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

    Линейный алгоритм является наиболее простым. В нём предполагается последовательное выполнение операций. В этом алгоритме не предусмотрены проверки условий или повторений.

    Пример: Вычислить функцию z= (х-у)/x +y2 .

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

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

    Рис.8. Линейный алгоритм

    Назначение блоков в схеме на рис.8:

    · Блок 1 в схеме служит в качестве логического начала.

    · Блок 3 представляет арифметическое действие.

    · Блок 4 выводит результат.

    · Блок 5 в схеме служит в качестве логического завершения схемы.

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

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

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

    Пример: При выполнении условия x >0 вычисляется функция: z = ln x + y , иначе, а именно, когда х=0 или x <0 , вычисляется функция: z = x + y 2 .

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

    Решение: На рис.9 представлен разветвляющийся алгоритм, где в зависимости от условия выполнится одна из веток. В блок-схеме появился новый блок 3, который проверяет условие задачи. Остальные блоки знакомы из линейного алгоритма.

    https://pandia.ru/text/78/136/images/image008_57.gif" width="300" height="360 src=">

    Рис.9. Алгоритм ветвления

    Пример: Найти максимальное значение из трёх различных целых чисел, введенных с клавиатуры. Составить блок-схему решения задачи.

    Решение: Данный алгоритм предполагает проверку условия. Для этого выбирается любая из трёх переменных и сравнивается с другими двумя. Если она больше, то поиск максимального числа окончен. Если условие не выполняется, то сравниваются две оставшиеся переменные. Одна из них будет максимальной. Блок-схема к этой задаче представлена на рис 10.

    https://pandia.ru/text/78/136/images/image010_48.gif" width="492" height="456 src=">

    Рис. 10. Блок-схема поиска максимума

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

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

    Из циклических алгоритмов выделяют два типа:

    1) с заданным количеством циклов или со счётчиком циклов;

    2) количество циклов неизвестно.

    Пример: В цикле вычислить значение функции z=x*y при условии, что одна из переменных x меняется в каждом цикле на единицу, а другая переменная у не меняется и может быть любым целым числом. В результате выполнения цикла при начальном значении переменной х=1 можно получить таблицу умножения. Количество циклов может быть любым. Составить блок-схему решения задачи.

    Решение: В примере количество циклов задаётся. Соответственно выбирается алгоритм циклов первого типа. Алгоритм этой задачи приводится на рис. 11.

    Во втором блоке вводятся количество циклов n и любые целые числа х , y .

    В блок-схеме появился новый блок 3, в котором переменная i считает количество циклов, после каждого цикла увеличиваясь на единицу, пока счётчик не будет равен i=n . При i=n будет выполнен последний цикл.

    В третьем блоке указывается диапазон изменения счётчика цикла (от i =1 до i=n ).

    В четвёртом блоке изменяются значения переменных: z , x .

    В пятом блоке выводится результат. Четвёртый и пятый блоки повторяются в каждом цикле.

    Рис.11 . Циклический алгоритм со счётчиком циклов

    Этот тип циклических алгоритмов предпочтителен, если дано количеством циклов.

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

    Пример: Вычислить у=у- x пока y > x , если y =30 , x =4. Подсчитать количество выполненных циклов, конечное значение переменной у . В цикле вывести значение переменной у , количество выполненных циклов. Составить блок-схему решения задачи.

    Решение: В примере количество циклов неизвестно. Соответственно выбирается алгоритм циклов второго типа. Алгоритм этой задачи приводится на рис. 12.

    Условие проверяется на входе в цикл. В теле цикла выполняется два блока:

    1) у=у-х; i = i +1 ;

    2) вывод значений переменных i , y .

    Цикл выполняется до тех пор, пока выполняется условие y>x . При условии равенства этих переменных у=х или y цикл заканчивается.

    Алгоритм, представленный на рис.12, называется циклический алгоритм с предусловием , так как условие проверяется в начале цикла или на входе в цикл.> x на входе в цикл. Если условие выполняется, то переход к блоку 4, иначе на блок 6.

    В четвёртом блоке вычисляется значение переменной у i = i +1 .

    В пятом блоке выводится результат:

    · значение переменной у ,

    i .

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

    Решение: В этом случае проверяется условие на выход из цикла: y<=x . При этом условии цикл не выполняется. Условие в блок-схеме следует перенести в конец цикла, после вывода на печать. Цикл выполняется до тех пор, пока выполняется условие y>x .

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

    Во втором блоке вводятся y =30 , x =4 .

    В третьем блоке вычисляется значение переменной у , подсчитывается количество выполненных циклов i = i +1 .

    В четвёртом блоке выводится результат:

    · значение переменной у ,

    · количество выполненных циклов i .

    В пятом блоке проверяется условие y <= x на выход из цикла. Если условие выполняется, то переход к блоку 6, иначе на блок 3 и цикл повторяется.

    Рис.13 . Алгоритм цикла с постусловием

    Контрольные вопросы

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

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

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

    4. Основные блоки графического алгоритма.

    5. Линейная алгоритмическая структура. Пример.

    6. Ветвление. Пример.

    7. Циклические алгоритмические структуры. Пример.