Приведите по два примера алгоритмов каждого вида с блок-схемами
Сделать конспект в тетради и выполнить домашнее задание
Алгоритмы и способы их описания
В настоящее время слово «алгоритм» является одним из важнейших понятий науки информатики и имеет следующее определение:.
Запишите определение алгоритма: Алгоритм - это описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Приведите примеры алгоритмов.
…
Мир алгоритмов очень разнообразен. Но, несмотря на это, можно выделить общие свойства, которыми обладает любой алгоритм:
Свойства алгоритма:
Универсальность (массовость) - применимость алгоритма к различным наборам исходных данных.
Дискретность - процесс решения задачи по алгоритму разбит на отдельные действия.
Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются.
Результативность - по завершении выполнения алгоритма обязательно получается конечный результат.
Выполнимость (эффективность) - результата алгоритма достигается за конечное число шагов.
Детерминированность (определенность) - алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.
Последовательность – порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.
|
|
|
Описание действий в алгоритме следуют последовательно друг за другом. Однако очередность выполнения этих действий может быть изменена, если в алгоритме предусмотрен анализ некоторого условия. Путем включения условий создаются алгоритмы с различной структурой, в которой можно выделить несколько типовых конструкций: линейную, разветвляющуюся и циклическую.
Предположим, что требуется составить алгоритм результата выражения: 100+15-40+20.
В этом примере мы выполняем действия в том порядке, в котором они записаны. Такие алгоритмы получили название линейных алгоритмов.
Запишите определение линейного алгоритма: Линейный алгоритм - это описание действий, которые выполняются однократно в заданном порядке.
Приведите примеры таких алгоритмов.
…
Вспомним сюжет из русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: «Направо пойдешь - коня потеряешь, налево пойдешь - сам пропадешь…». Подобная ситуация, заставляющая нас принимать решение в зависимости от некоторого условия, постоянно встречается в повседневной жизни.
Алгоритм, в котором используется условие, получил название разветвляющегося алгоритма.
|
|
|
Запишите определение разветвляющегося алгоритма: Разветвляющийся алгоритм - это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Вспомните кота из сказки А.С. Пушкина, который «идет направо - песнь заводит, налево - сказку говорит». В этом примере от значения условия зависит выполнение первого или второго действия. В таких случаях схема разветвляющегося алгоритма будет выглядеть так: «если <условие>, то … иначе …».
Такое представление алгоритма получило название полной формы. Запишите: Разветвляющийся алгоритм называется полным, если он имеет вид: «если <условие>, то … иначе …».
Но разветвляющийся алгоритм может иметь и другой вид. Например, в предложении «если выучишь урок, то получишь хорошую оценку» в зависимости от значения условия либо выполняется, либо не выполняется действие «получишь хорошую оценку».
В таких случаях схема разветвляющегося алгоритма будет иметь вид: «если <условие>, то …», и будет носить название неполной формы. Запишите: Разветвляющийся алгоритм называется неполным, если он имеет вид: «если <условие>, то …».
Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий. Например, каждый год наступают зима, весна, лето, осень.
|
|
|
Алгоритм, который содержит описание повторяющихся действий, называют циклическим. Число повторений в циклических процессах известно заранее или зависит от какого-либо условия.
Запишите определение циклического алгоритма: Циклический алгоритм - это описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Итак, любой алгоритм можно составить, используя только типовые алгоритмические конструкции. Формы же представления этих алгоритмов могут быть разными:
словесной;
графической;
программной.
Рассмотрим их:
1. Словесная форма - это форма описания алгоритма на естественном языке.
Данная форма очень удобна, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить идею.
2. Для более наглядного представления алгоритма используется графическая форма. Графическая форма - изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
|
|
|
3. При записи алгоритма в словесной и в графической форме допускается определенный произвол при изображении команд. Вместе с тем такая запись точна на столько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы – компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. Такой язык принято называть языком программирования, а форму представления алгоритма - программной.
То есть программная форма записи алгоритма – это запись на языке программирования.
Рассмотрим пример использования данных форм записи алгоритмов:
( написать алгоритм «Одеться по погоде».Если на улице температура ниже 0, то необходимо надеть шубу, иначе – куртку)
Словесная форма:
Алгоритм ПОГОДА
Начало
определить температуру воздуха
если температура ниже 0, то надеть шубу, иначе надеть куртку
Конец.
Программная форма:
program E3;
usescrt;
var t: real;
begin
clrscr;
writeln(‘введите температуру воздуха t=’);
readln(t);
if t < 0 then writeln(‘одетьшубу’) else writeln(‘одетькуртку’);
end.
Графическая форма записи:
Чтобы нам воспользоваться графическим способом, нам с вами нужны знать основные элементы блок схем.
Графическая запись с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Графическая запись алгоритма имеет ряд преимуществ: каждая операция вычислительного процесса изображается отдельной геометрической фигурой и графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Виды блоков.
Правила создания блок – схем:
1.Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводиться параллельно линиям рамки.
2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.
3.В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков.
4.Из блока (кроме логического) может выходить только одна линия.
5.Логический блок может иметь в качестве продолжения один из двух блоков, и из него выходят две линии.
6.Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.
7.Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.
Составление алгоритмов
Составить алгоритм, то есть объяснить другому, как выполнять те или иные задачи так, чтобы это было понятно каждому, - очень тяжело. Наша задача – научиться составлять алгоритмы для различных примеров, чтобы впоследствии, когда вы столкнётесь с необходимостью составлять алгоритмы для написания различных программ, это не составляло для вас особого труда.
Начнём мы с самых простых алгоритмов – линейных. Их составление, обычно, не вызывает особого труда. Однако, навыки составления таких алгоритмов чрезвычайно важны.
Пример 1. Составить алгоритм запуска программы Paint в ОС Windows 7.
Решение:
Вспомним из курса информатики порядок действий для запуска программы Paint.
Войти в меню «Пуск».
Войти в пункт «Все программы».
Войти в пункт «Стандартные».
Выбрать программу «Paint».
Данный алгоритм в виде блок-схемы имеет следующий вид:
Рассмотрим пример на составление алгоритмов с ветвлениями.
Пример 2. Составьте алгоритм для перехода дороги на светофоре.
Решение:
Возможны следующие ситуации: в тот момент, когда мы подошли к дороге горел красный или зелёный свет. Если горел зелёный свет, то можно переходить дорогу. Если же горел красный свет, то необходимо дождаться зелёного – и уже тогда переходить дорогу.
Таким образом, алгоритм имеет следующий вид:
Подойти к светофору.
Посмотреть на его свет.
Если горит зелёный, то перейти дорогу.
Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.
Блок-схема данного алгоритма имеет вид:
Рассмотрим пример на составление циклического алгоритма. Мы уже несколько раз обсуждали перевод чисел из десятичной системы в двоичную. Теперь пришло время чётко сформулировать этот алгоритм.
Напомним, что его принцип состоит в делении числа на 2 и записей остатков, получающихся при делении.
Пример 3. Составить алгоритм перевода чисел из десятичной системы в двоичную.
Решение:
То есть, алгоритм будет выглядеть так:
Если число равно 0 или 1, то это и будет его двоичное представление.
Если число больше 1, то мы делим его на 2.
Полученный остаток от деления записываем в последний разряд двоичного представления числа.
Если полученное частное равно 1, то его дописываем в первый разряд двоичного представления числа и прекращаем вычисления.
Если же полученное частное больше 1, то мы заменяем исходное число на него и возвращаемся в пункт 2).
Блок-схема этого алгоритма выглядит следующим образом:
«Чтение» алгоритмов
Пример 4. По заданной блок-схеме выполнить действия алгоритма для числа 23.
Решение:
a=23
23+5=28
28<35
28+5=33
33<35
33+5=38
38>35
76 – двузначное число
76-50=26.
Ответ: 26.…
Домашнее задание:
Приведите по два примера алгоритмов каждого вида с блок-схемами
Ответить на вопросы теста:
1. Алгоритм — это:
а) правила выполнения определенных действий;
б) ориентированный граф, указывающий порядок исполнения некоторого набора команд;
в) понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленных целей;
г) набор команд для компьютера;
д) протокол вычислительной сети.
2. Укажите наиболее полный перечень способов записи алгоритмов:
а) словесный, графический, псевдокод, программный;
б) словесный;
в) графический, программный;
г) словесный, программный;
д) псевдокод.
3. Суть такого свойства алгоритма как результативностьзаключается в том, что:
а) Алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);
б) записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;
в) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;
г) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату;
д) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.
4. Суть такого свойства алгоритма как массовость заключается в том, что:
а) алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);
б) записывая для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;
в) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;
г) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату;
д) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.
5. Суть такого свойства алгоритма как дискретность заключается в том, что:
а) алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);
б) записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;
в) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;
г) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату;
д) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.
6. Суть такого свойства алгоритма как понятность заключается в том, что:
а) алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);
б) записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;
в) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;
г) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату;
д) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.
7. Суть такого свойства алгоритма как детерминируемостьзаключается в том, что:
а) алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);
б) записывая алгоритм для конкретного исполнителя можно использовать лишь те команды, что входят в систему его команд;
в) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;
г) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату;
д) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.
8. алгоритм называется линейным:
а) если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;
б) если ход его выполнения зависит от истинности тех или иных условий;
в) если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;
г) если он представим в табличной форме;
д) если он включает в себя вспомогательный алгоритм.
9. алгоритм называется циклическим:
а) если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;
б) если ход его выполнения зависит от истинности тех или иных условий;
в) если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;
г) если он представим в табличной форме;
д) если он включает в себя вспомогательный алгоритм.
10. алгоритм включает в себя ветвление, если:
а) если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;
б) если ход его выполнения зависит от истинности тех или иных условий;
в) если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;
г) если он представим в табличной форме;
д) если он включает в себя вспомогательный алгоритм.
Дата добавления: 2021-01-20; просмотров: 1161; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!