25. Алгоритм и его свойства. Способы записи алгоритмов
Понятие алгоритма — одно из самых фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. К реализации определенных алгоритмов сводятся процессы управления в различных системах, что делает понятие алгоритма близким к кибернетике.
Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике — теории алгоритмов. Особенность положения, однако, состоит в том, что при решении практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, и тем более при использовании на практике информационных технологий, можно, как правило, не опираться на высокую формализацию данного понятия, и поэтому представляется целесообразным познакомиться с алгоритмами и алгоритмизацией на основе содержательного толкования сущности понятия алгоритма и рассмотрения основных его свойств. При таком подходе алгоритмизация более выступает в основном как набор определенных практических приемов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Можно провести аналогию между этим обстоятельством и рассмотренным выше подходом к измерению информации: тонкие математические построения при «кибернетическом» подходе не очень нужны при использовании гораздо более простого «объемного» подхода при практической работе с компьютером.
Само слово «алгоритм» происходит от algorithmi — латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.
Алгоритм — это определенным образом организованная последовательность действий, за конечное число шагов приводящая к решению задачи.
Свойства алгоритмов:
Алгоритм должен быть составлен таким образом, чтобы исполнитель, в расчете на которого он создается, мог однозначно и точно следовать командам алгоритма и эффективно получать определенный результат. Это накладывает на записи алгоритмов целый ряд обязательных требований, суть которых вытекает, вообще говоря, уже из приведенного выше неформального толкования понятия алгоритма. Сформируем эти требования в виде перечня свойств, которым должны удовлетворять алгоритмы, адресуемые заданному исполнителю.
1. Одно из первоначальных требований, которое предъявляется к алгоритму, состоит в том, что описываемый процесс должен быть разбит на последовательность отдельных шагов. Возникающая в результате такого разбиения запись представляет собой упорядоченную совокупность четко отделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Только выполнив требования одного предписания, можно приступить к выполнению следующего. Дискретная структура алгоритмической записи может, например, подчеркиваться сквозной нумерацией отдельных команд алгоритма, хотя это требование не является обязательным. Рассмотренное свойство алгоритмов называют дискретность.
2. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие не может. Известно, что у каждого исполнителя имеется своя система команд. Очевидно, что, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем называть понятностью.
3. Будучи понятным, алгоритм не должен все же содержать предписаний, смысл которых может восприниматься неоднозначно. Это означает, что одна и та же команда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результат.
В данном случае речь фактически идет о том, что запись алгоритма должна быть настолько четкой, полной и продуманной в деталях, чтобы у исполнителя никогда не могло возникнуть потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма. Говоря иначе, алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Отмеченное свойства алгоритмов называют определенностью или детерминированностью.
4. Обязательное требование к алгоритмам — результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный ответ на вопрос задачи (либо вывод о том, что решения не существует).
5. Наиболее распространены алгоритмы, обеспечивающие решение не одной исключительной задачи, а некоторого класса задач данного типа. Это свойство алгоритма называют массовостью. В простейшем случае массовость обеспечивает возможность использования различных значений исходных данных.
Способы записи алгоритма
Основными изобразительными средствами алгоритмов являются следующие способы их записи:
— словесный;
— формульно-словесный;
— блок-схемный;
— псевдокод;
— структурные диаграммы;
— языки программирования.
Словесный способ – это содержание этапов вычислений задается на естественном языке в произвольной форме с требуемой детализацией.
Формульно-словесный способ — это задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями.
Блок-схемный способ — это графическое изображение логической структуры алгоритма, в котором каждый этап процесса переработки данных представляется в виде геометрических фигур (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций.
В приведенной ниже табл.16 представлены основные блоки, используемые при построении алгоритма в блок-схемной форме.
Таблица 16. Графические изображения блок-схем
Доказано, что любую программу можно написать, используя комбинации трех управляющих структур:
— следования, или последовательности операторов;
— развилки, или условного оператора;
— повторения или оператора цикла.
Программа, составленная из канонических структур, будет называться регулярной программой, т.е. иметь 1 вход и 1 выход, каждый оператор в программе может быть достигнут при входе через ее начало (нет недостижимых операторов и бесконечных циклов). Управление в такой программе передается сверху вниз. Снабженные комментариями, такие программы хорошо читабельны.
| < Предыдущая | Следующая > |
|---|
automationlab.ru
Свойства и способы записи алгоритмов
В информатикe понятиe алгоритмов считаeтся базовым. Имeнно этот мeтод являeтся общим в программировании и модeлировании. Для того чтобы понять структуру инструкций, нeобходимо узнать их свойства и то, для чeго они примeняются. В статьe опишeм способы записи алгоритмов в информатикe, их варианты создания, такжe постараeмся разобраться, почeму они так важны для программирования.
Общиe свeдeния
Алгоритмы считаются объeктом изучeния дисциплины, которая тeсно пeрeплeтаeтся с матeматикой и информатикой. Большe того, эти способы записи примыкают к такой наукe, как логика. Данныe инструкции позволяют разрабатывать мeтоды для рeализации задач, а на практикe помогают такжe работать с информационными тeхнологиями. Таким образом, алгоритмизация выступаeт в качeствe набора опрeдeлeнных приeмов, которыe способны при помощи особых навыков функционировать с языковыми срeдствами.
Само слово «алгоритм» происходит от латинской формы имeни матeматика IX вeка аль-Хорeзми. Он стал пeрвым, кто смог составить особeнности работы с арифмeтичeскими дeйствиями. Изначально инструкциями считались обычныe правила выполнeния сложeния, вычитания, умножeния, дeлeния. Сeйчас жe алгоритм – это опрeдeлeнный способ дeйствия, который при помощи установлeнного количeства шагов приводит к полному рeшeнию поставлeнной задачи.
Свойства алгоритмов
Алгоритм должeн быть составлeн таким образом, чтобы пользоватeль или другоe выполняющee устройство полностью eго понимали. Всe шаги должны быть поняты однозначно, только в таком случаe, слeдуя всeм командам, можно получить эффeктивный рeзультат. Поэтому на алгоритмы и их запись вводятся опрeдeлeнныe трeбования. Их суть в том, чтобы всe дeйствия были истолкованы вeрно. Имeнно эти трeбования называются свойствами.
Свойство № 1
Пeрвоначальноe трeбованиe к алгоритму заключаeтся в том, что каждый шаг должeн выполняться отдeльно и послeдоватeльно. Такая запись должна быть полностью разбита на блоки, прeдставлять собой упорядочeнную совокупность прeдписаний, команд и опeраторов. Инструкция должна образовывать дискрeтную структуру. Это дeлаeтся для того, чтобы каждый отдeльный шаг выполнялся строго послe завeршeния прeдыдущeго. Такоe свойство называeтся дискрeтностью. Как правило, на письмe всe шаги записываются при помощи сквозной нумeрации, однако это трeбованиe нe обязатeльно.
Свойство № 2
Всe алгоритмы, которыe используются на практикe, ориeнтированы на опрeдeлeнного исполнитeля. Имeнно поэтому инструкция должна составляться конкрeтно для нeго самого. Соотвeтствeнно нужно примeрно прeдставлять, какиe команды будут понятны тому, для кого алгоритм написан, а какиe для нeго нeоднозначны. Каждый исполнитeль (им можeт быть чeловeк, компьютер и другая тeхника) обладаeт своeй систeмой команд. Соотвeтствeнно нeобходимо использовать только тe опeраторы, которыe имeются в eго памяти. Это свойство называeтся понятностью.
Свойство № 3
Каждый шаг должeн быть полностью понятным, нe восприниматься нeоднозначно. Таким образом, каждая из записeй алгоритма должна правильно пониматься любым исполнитeлeм. Соотвeтствeнно послe совeршeния каждой из них и выполнeния прeдписанной инструкции различной тeхникой рeзультат нe должeн измeняться. В данном пунктe рeчь идeт о том, что запись алгоритма – максимально точный, чeткий, полный и полностью дeтализированный шаг. Это дeлаeтся для того, чтобы исполнитeлю нe трeбовалось принимать какиe-либо рeшeния. Он должeн правильно понимать, что от нeго трeбуeтся. Такжe при составлeнии алгоритма нужно продумывать всe таким образом, чтобы исполнитeль понимал послeдоватeльность шагов. Всe должно быть прeдeльно ясно. Это свойство называeтся дeтeрминированностью.
Виды алгоритмов по способу записи
Как можно записывать алгоритмы? Есть наиболee популярныe способы. Рeчь идeт о словeсном, формально-словeсном, блок-схeмном, диаграммном мeтодах. А такжe о псeвдокодe и языках программирования. Рассмотрим нeкоторыe из видов записи алгоритмов.
Словeсный способ
Словeсный способ являeтся наиболee понятным для обычного чeловeка. Благодаря алгоритму, записанному в таком видe, каждый шаг можeт понять любой исполнитeль. Этот способ задаeтся при помощи eстeствeнного языка в произвольной формe.
Формально-словeсный способ
Это форма записи алгоритмов, которая прeдставляeт собой инструкцию. Она обязатeльно включаeт в сeбя матeматичeскиe символы. Присутствуeт словeсноe объяснeниe. Это позволяeт увeличить спeктр рeшаeмых задач.
Блок-схeмы
Блок-схeмный способ прeдставляeт собой графичeскоe изображeниe алгоритма. Нужно отмeтить, что их расшифровка являeтся eдиной для всeх. Каждый этап описанного процeсса имeeт свою фигуру либо блок, имя графичeского изображeния поясняeт, что нeобходимо дeлать исполнитeлю.
Языки программирования
Болee трудной формой записи алгоритмов для многих людeй являeтся запись инструкции в видe программы. В данном случаe используются языки программирования. Для того чтобы составить алгоритм на одном из них, нeобходимо знать соотвeтствующиe команды и имeть навыки.
Псeвдокод
Псeвдокод являeтся систeмой различных обозначeний, которыe нeобходимы для eдиной записи всeх алгоритмов. Он занимаeт промeжуточноe мeсто мeжду такими мeтодами, как eстeствeнный и формальный. Он максимально близок к пeрвому, однако в данном способe записи алгоритмов могут использоваться различныe конструкции и матeматичeскиe обозначeния. В такую форму инструкции нe принято вводить синтаксичeскиe правила, которыe присущи формальным мeтодам записи. Это позволяeт максимально облeгчить eго проeктированиe. В псeвдокодe часто используются нeбольшиe конструкции, которыe относятся к формальным языкам. Это даeт возможность пeрeходить от записи на описываeмом мeтодe на другиe варианты составлeния инструкции. Болee того, в таком способe записи алгоритмов имeются спeциальныe служeбныe слова, смысл которых используeтся в чeтко опрeдeлeнных ситуациях.
xroom.su
Эти задачи решались при помощи алгоритмов, дайте определение — алгоритм — Посмотрите на экран и скажите, данная последовательность является алгоритмом? (слайд 5) Инструкция получения кипятка.
— Как должна выглядеть последовательность, чтобы её можно было назвать алгоритмом? -Сколько свойств алгоритма вы знаете? Назовите их, пожалуйста Слайд 6 Я предлагаю вам выполнить следующее задание: вспомните эти свойства и сопоставьте их названиям соответствующую на ваш взгляд формулировку, посмотрев задание на экране. Вам необходимо поставить в соответствие свойство с пояснением. Каждый заполняет свой лист самооценки, а затем, когда вся группа будет готова, поднимаете руку Дополнительный бонус получает команда, быстрее справившаяся с заданием.(слайд 7) Свойства алгоритма
— Давайте посмотрим на ключ к заданию «Свойства алгоритма» (показать ответы) слайд 7 и поставим баллы за это задание по критериям в свои оценочные листы. | Учащиеся дают понятие — Эта последовательность действий не является алгоритмом. Нарушена последовательность действий. | Коммуникативные (умение выражать мысли) Регулятивные (планирование, целеполагание) Логические УУД(построение логической цепи) |
compedu.ru
Алгоритм. Способы записи алгоритма. | Сообщество учителей информатики
Задачи урока:
образовательные:
- создать условия для формирования первичного представления об алгоритме, его исполнении;
- познакомить учащихся с понятиями “алгоритм” и способах записи алгоритма;
развивающие:
- развивать алгоритмическое мышление;
- развивать познавательный интерес, логическое мышление;
- развитие умения планировать свою деятельность;
- развивать память, внимание;
- формировать интерес к изучению предмета;
воспитательные:
- воспитывать чувство коллективизма;
- воспитание активности;
План урока:
1. организационный момент;
2. вопросы по домашнему заданию;
3. объяснение нового материала;
4. обобщение и систематизация знаний;
5. компьютерный практикум;
6. домашнее задание;
7. подведение итогов урока.
Оборудование урока:
- мультимедийный проектор;
- демонстрация “Алгоритм”;
- ПК каждому учащемуся
Ход урока
1. Организационный момент
Учитель: Здравствуйте, мои пытливые умы! Эпиграфом к сегодняшнему уроку послужат слова (слайд 1):
«Не нужно нам владеть клинком,
Не ищем славы громкой.
Тот побеждает, кто знаком
С искусством мыслить тонким»
Тему сегодняшнего урока вы узнаете, если разгадаете ребус.
Ученики разгадывают ребус на экране проектора (слайд 2)
Учитель: Я бы хотела, чтобы вы повернули голову направо, насколько сможете, и запомнили место на стене, куда дотягивается ваш взгляд. Запомнили?
Теперь вернемся в исходное положение.
И сейчас снова повернемся, вправо, но постараемся посмотреть еще дальше.
И так, повернулись. Повернулись, так чтобы еще дальше посмотреть. Спасибо.
У всех получилось посмотреть во второй раз дальше?
Я и в первый раз попросила вас повернуть голову, так как только вы сможете. Но во второй раз все повернули гораздо дальше. А почему?
А получилось так потому, что перед вами стояла цель – увеличить предыдущее достижение.
Так вот, юные информатики, всегда, когда у человека есть цель, он может добиться гораздо большего.
И так, наша цель на уроке:
· повторить, что такое алгоритмы,
· где и когда мы их используем,
· зачем они нам нужны
· познакомиться со способами представления алгоритмов.
2.Вопросы по домашнему заданию.
Учитель: Вспомните, что такое алгоритм?
| Алгоритм – это определенная последовательность действий, строгое исполнение которых приводит к задуманному результату (слайд 3). |
Учитель: Приведите примеры алгоритмов в жизни.
Дети:
1. Собираюсь на рыбалку;
2. Как построить скворечник
3. Как решить задачу по математике
4. Как сделать уборку дома
5. Как испечь торт
6. Собрать корзину грибов
7. Пришить пуговицу
Учитель: При составлении алгоритма нужно быть очень внимательным, поскольку даже от одного знака может зависеть смысл всего алгоритма.
Вспомните мультфильм, в котором царь должен был подписать указ: “Казнить нельзя помиловать!” Смысл меняется только от перестановки запятой. Сравните: (слайд №4).
(На доске в произвольной последовательности расположены действия алгоритма «Сделай колобка из пластилина»).
Учитель: Ребята, можно ли, выполняя этот алгоритм, слепить колобка?
Дети: Нет, т.к. действия идут не по порядку.
Учитель: Откуда пришло к нам слово АЛГОРИТМ?
Дети: Слово «алгоритм» произошло от латинского написания слова «аль – Хорезми», под которым в средневековой Европе знали величайшего математика из города Хорезма в современном Узбекистане Мухамеда ибн Мусу, жившего в 783 – 850 гг. (слайд№5)
Учитель: Какие способы представления алгоритма вы знаете?
Дети: перечисление, рисунок, блок-схема, программа (слайд №6)
3. Объяснение нового материала
Учитель: Рассмотрим подробнее один из этих способов – блок-схему.
Запишите в тетрадь тему урока: «Блок-схема алгоритма» (слайд № 7).
Блок-схема – набор геометрических фигур, внутри которых записываются шаги алгоритма.
Чтобы правильно изобразить алгоритм в виде блок-схемы, необходимо знать обозначения ее элементов (раздает карточки). На карточках вы видите необходимые вам для работы элементы блок-схемы:
| |
шаг алгоритма (действие) | |
блок проверки заданного условия | |
ввод/вывод данных | |
| направление процесса |
(слайд №8)
Учитель: А сейчас мы с вами поиграем. Игра называется «21 палочка» (Сыграть с каждым учеником).
Учитель: Понравилось? А кто понял, почему всегда выигрывал учитель?
Теперь чтобы и вы могли выигрывать, запишем алгоритм выигрышной стратегии себе в тетради. Но оформим мы его в виде блок-схемы (слайд №9).
Учитель: Сейчас вы будете выполнять алгоритм практического задания 2.26 и 2.27 из учебника.
6. Проверка выполнения практического задания и выставление оценок.
7. Подведение итогов
Домашнее задание (слайд 10).
Наш урок подходит к концу и мне бы хотелось чтобы каждый из вас сказал свое мнение о нем.
А начать попробуйте со слов:
“Сегодня на уроке я узнал…”,
“Сегодня мне понравилось …”,
“Сегодня мне не понравилось …” (слайд № 11).
Приложение 1
Литература, использованная при подготовке к уроку:
1. Первин Ю.А., Дуванов А.А., Зайдельман Я.Н. и др. “Роботландия 96”. Информация, алгоритмы, компьютеры. Раздел 1. Пособие для учителя. – Переславль – Залесский, 1996.
2. Тимофеев О. Н.Рецепты веселой вечеринки: Игры, розыгрыши, забавы. –Ярославль: Академия развития: Академия Холдинг, 2002.
3. Журналы «Информатика и образование».
4. Подписка газет «Информатика».
www.oivt.ru
Графический способ записи алгоритмов — Мегаобучалка
Система качества
Методические указания и задания на выполнение типового расчета
«Алгоритмы и блок-схемы»
«1 семестр
< Б.2 Информатика >
| Направление подготовки | <270800 Строительство > |
| Профиль подготовки | < Городское и строительство и хозяйство > |
| Квалификация (степень) выпускника | <бакалавр > |
| Форма обучения | <очная> |
Волжский, 2012
ПОНЯТИЕ АЛГОРИТМА
Алгоритм — это одно из основных понятий математики и информатики. Более 1000 лет назад в Багдаде, крупном научном центре Востока, жил абд Джафар Мужамед ибн Муса аль-Хорезми. Ему принадлежит книга по математике, которая в течение нескольких столетий пользовалась широкой популярностью. В ней Аль-Хорезми сформулировал правила выполнения четырёх арифметических действий над многозначными числами.
При переводе на латынь имя автора переделали в Algorithmi (Алгоритми). В книге аль-Хорезми приводились методы решения разных задач. Ссылаясь на них, европейцы упоминали: «Так говорил Алгоритми…». Со временем методы решения задач стали называться алгоритмами. В дальнейшем алгоритмом стали называть описание любой последовательности действий, которую следует выполнить для решения поставленной задачи.
Алгоритм — строго упорядоченная последовательность действий, направленная на выполнение поставленной задачи.
Алгоритмы, предназначенные для выполнения компьютерами, обычно называются компьютерными программами, или просто программами. Программа содержит команды на языке, понятном компьютеру. Она сообщает компьютеру, где брать и как надо обрабатывать данные для получения желаемого результата. Все функции компьютера, любое его действие задается программой.
Программа — это алгоритм, представленный на языке, понятном компьютеру.
Свойства алгоритма
Алгоритм должен удовлетворять следующим требованиям:
1. «Понятность» для исполнителя – исполнитель алгоритма должен знать, как его выполнить.
2. «Дискретность» (прерывность, раздельность)- алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определённых ) шагов (этапов).
3. «Определённость»— каждое правило алгоритма должно быть чётким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
4. «Результативность» (или конечность) состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.
5. «Массовость» — означает, что алгоритм решения задачи разрабатывается в общем, виде, т. е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторого множества, которое называется областью применимости алгоритма. Данное свойство алгоритмов является наиболее важным.
Алгоритм считается правильным, если его выполнение всегда дает правильный результат. Соответственно алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.
Способы описания алгоритма
На практике наиболее распространены следующие формы представления алгоритмов:
· Словесный способ
· Графический способ
· Псевдокоды
· Программный способ
Словесный способ записи алгоритмов
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
ПРИМЕР 1: Задача о сортировке шариков
Имеются три урны (белая, черная и полосатая). В полосатой урне находятся белые и черные шарики. Надо из этой урны все черные шарики переложить в черную урну, а белые — в белую. Сортировка производится так: по очереди вынимаются шарики из полосатой урны и в зависимости от цвета кладутся или в черную или в белую урну.
Алгоритм:
1. взять шарик из полосатой урны;
2. если он белый, то опустить в белую урну и перейти к действию 4;
3. если он черный, то опустить в черную урну и перейти к действию 4;
4. если полосатая урна не пуста, то перейти к действию 1;
конец.
Словесный способ не имеет широкого распространения, так как такие описания:
· строго не формализуемы;
· страдают многословностью записей;
· допускают неоднозначность толкования отдельных предписаний.
Графический способ записи алгоритмов
Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т. п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. В таблице приведены наиболее часто употребляемые символы.
Псевдокоды
Псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и другое).
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
В псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они, как правило, выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций. Примером псевдокода является «школьный алгоритмический язык».
Общий вид алгоритма:
megaobuchalka.ru
Способы описания алгоритмов — Информатика, информационные технологии
Существуют несколько способов описания алгоритма: словесное, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Запись алгоритма осуществляется в произвольной форме, никаких правил не существует.
Псевдокод – описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основные этапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема – описание структуры алгоритма с помощью геометрических фигур с линиями – связями, показывающими порядок выполнения отдельных инструкций. В блок – схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Основные конструкции, использующиеся для построения блок – схем.
— начало/конец алгоритма
— процесс, предназначенный для описания отдельных
действий
ввод/вывод с неопределенного носителя
Нет Да — проверка условия
— — предопределенный процесс, предназначенный для
— обращения к подпрограмме.
Лекция 5.2. Блок-схемы алгоритма
Алгоритмы решения задач
Логическая структура алгоритма решения любой задачи может быть выражена комбинацией трех базовых структур: следования, ветвления и цикла (это содержание теоремы Бема – Якопини).
Линейная структура (следование) самая важная из структур. Она означает, что действия могут быть выполнены друг за другом (рис. 5.2.1.).
Вход Выход
Прямоугольники могут представлять как одну единственную команду, так и множество операторов, необходимых для выполнения сложной обработки данных.
Пример 5.2.1.
Опишем алгоритм сложения двух чисел на псевдокоде и в виде блок-схемы (рис. 5.2.2.).
1. Псевдокод:
2. Ввод двух чисел a, b
3. Вычисляем сумму S = a + b
4. Вывод S
5. Конец.
Рис. 5.2.2. Блок — схема к примеру 5.2.1.
Ветвление (развилка) – это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка условия, а затем выбирается один из путей (рис. 5.2.3). Если условие имеет значение «Истина», то выполняется «Действие А». Если условие имеет значение «Ложь», выполняется «Действие В». Эта структура называется, также «Если – ТО – ИНАЧЕ» или «развилка». Каждый путь (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран. Может оказаться, что для одного из результатов проверки ничего выполнять не надо. В этом случае можно применить только один обрабатывающий блок (рис. 5.2.4).
Вход
Ложь (НЕТ) Истина (ДА)
Выход
Рис. 5.2.3. Полное ветвление
Вход
ДА НЕТ
Рис. 5.2.4. Структура «непол-
ное ветвление»
Выход
Такая структура называется «неполным ветвлением» или «неполной развилкой».
Пример 5.2.2.
Вывести значение наибольшего числа из двух чисел (рис. 5.2.5).
Псевдокод:
1. Ввод двух чисел a, b
2. ЕСЛИ ab, ТО «выводим a»,
ИНАЧЕ «выводим b»
3.
Конец.
НЕТ ДА
Рис. 5.2.5. Блок – схема к примеру 5.2.2.
Цикл (или повторение) предусматривает повторное выполнение некоторого набора команд алгоритма. Циклы позволяют записать длинные последовательности операций обработки данных с помощью небольшого числа повторяющихся команд. Различают два типа циклов: «цикл с предусловием» и «цикл с постусловием».
Цикл с предусловием («Пока») (рис. 5.2.6).
Истина Выход
Ложь
Рис. 5.2.6. Структура цикла «Пока».
Цикл начинается с проверки логического выражения. Если оно истинно, то выполняется тело цикла, затем все повторяется, пока логическое выражение сохраняет значение «истина». Как только оно становится ложным, выполнение операций прекращается и управление передается дальше. Особенностью цикла с предусловием является то, что если изначально логическое выражение имеет значение «ложь», то тело цикла не выполнится ни разу.
Пример 5.2.3.
Вычислить сумму 100 чисел (рис. 5.2.7).
Псевдокод:
1. НАЧ
2. I =1; S = 0
3. ПОКА i
НЦ
4. Ввести ai
5. S = S + ai
6. i = i + 1
КЦ
7. Вывод S
8.
Конец.
НЕТ
ДА
Рис. 5.2.7. Блок – схема к примеру 5.2.3 с циклом «Пока»
Цикл с постусловием («До»).
В отличие от цикла с предусловием, тело цикла с постусловием всегда будет выполнено хотя бы один раз, после чего проверяется условие. В этой конструкции тело цикла будет повторяться до тех пор, пока значение логического выражения ложно. Как только оно становится истинным, выполнение тела цикла прекращается (рис. 5.2.8).
Вход Истина
Ложь Выход
Рис. 5.2.8. Структура «цикла с постусловием».
Пример 5.2.4.
Вывести максимальное значение из 100 натуральных чисел (рис. 5.2.9).
Псевдокод:
1. Начало
2.
Ввести a1
3. max = a1; i = 2
4. НЦ
a. Ввести ai
b. ЕСЛИ maxai ТО max = ai
c. i = i + 1
5. ДО I100;
6. КЦ
7. Вывести max.
8. Конец.
Истина
Ложь Истина
Рис. 5.2.9. Блок – схема к примеру 5.2.4. с циклом «До»
Базовые алгоритмические структуры можно комбинировать одну с другой – как путем организации их следования, так и путем создания суперпозиций (вложений одной структуры в другую). Используя описанные структуры, можно полностью исключить использование каких-либо еще операторов условного и безусловного перехода, что является важным признаком структурного программирования. Приведем несколько примеров (рис. 5.2.10, 5.2.11, 5.2.12, 5.2.13).
—
+
— +
Рис. 5.2.10. Алгоритм типа «развилка, вложенная в цикл, с предусловием», для нахождения суммы положительных чисел и N возможных
— +
—
+
Рис. 5.2.11. Алгоритм типа «цикл, с предусловием, вложенный в неполную развилку»
— +
Рис. 5.2.12. Алгоритм типа «неполная развилка, вложенная в пол-
— + ную развилку».
Вопросы для самоконтроля
1. Дайте определение алгоритма и поясните его.
2. Какие формы представления алгоритма вы знаете?
3. В чем особенности графического представления алгоритма?
4. Назовите основные (базовые) алгоритмические структуры?
5. Перечислите свойства алгоритмов и объясните, чем они определены.
Статьи к прочтению:
Алгоритм
Похожие статьи:
Способы представления алгоритмов
1. Словесный. Такое описание алгоритма состоит из словесного перечня действий в виде предложений. Например, вычислить C= А-В, если А=В A + B , если A…
Способы описания алгоритмов.
Для записи алгоритмов используют различные способы в зависимости от предназначения алгоритма. Рассмотрим следующие способы описания алгоритма:…
csaa.ru
