Виртуальный кабинет информатики и ИКТ Горловского лицея № 88 "Мечта"
menu

Урок 16. Основные алгоритмические конструкции. Следование

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

Ключевые слова: 

• следование 
• ветвление 
• повторение 
• линейные алгоритмы 
• разветвляющиеся алгоритмы 
• циклические алгоритмы 

Человеку в жизни приходится решать множество различных задач. Решение каждой из них описывается своим алгоритмом, и разнообразие этих алгоритмов очень велико. Вместе с тем для записи любого алгоритма достаточно трёх основных алгоритмических конструкций (структур): следования, ветвления, повторения. Это положение выдвинул и доказал Э. Дейкстра в 70-х гг. прошлого века.

 

Эдсгер Вибе Дейкстра (1930-2002) — выдающийся нидерландский учёный, идеи которого оказали огромное влияние на развитие компьютерной индустрии.

2.4.1. Следование

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

Графическое представление алгоритмической конструкции «следование» приведено на рис. 2.8.

Рис. 2.8. Алгоритмическая конструкция «следование»

Пример 1. Линейный алгоритм приготовления отвара шиповника.

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

Пример 2. У исполнителя Робот есть четыре команды перемещения (вверх, вниз, влево и вправо), при выполнении каждой из них Робот перемещается на одну клетку в соответствующем направлении. По команде закрасить Робот закрашивает клетку, в которой он находится. Запишем линейный алгоритм, исполняя который Робот нарисует на клетчатом поле следующий узор и вернётся в исходное положение, обозначенное звёздочкой:

Пример 3. Дан фрагмент линейного алгоритма:

х:=2 
у:=х*х 
У:=У*У 
х:=у*х 
s:=x+y

Выясним, какое значение получит переменная s после выполнения этого фрагмента алгоритма. Для этого составим таблицу значений переменных, задействованных в алгоритме:

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

Пример 4. Некоторый исполнитель может выполнять над целыми числами кроме операций сложения, вычитания, умножения и деления ещё две операции: с помощью операции div вычисляется целое частное, с помощью операции mod — остаток.

Например: 5 div 2 = 2; 5 mod 2 = 1; 2 div 5 = 0; 2 mod 5 = 2.

Покажем, как с помощью этих операций можно реализовать алгоритм работы кассира, выдающего покупателю сдачу (s) наименьшим количеством банкнот по 500 (k500), 100 (k100), 50 (k50) и 10 (k10) рублей.

Исполните алгоритм для s = 745 и s = 1864. Составьте соответствующие таблицы значений переменных.

Ознакомьтесь с имеющимся в Единой коллекции цифровых образовательных ресурсов модулем для коллективной работы «Линейные алгоритмы» (217039). Совместно с друзьями постарайтесь составить алгоритмы для имеющихся в модуле задач. Пройдите тестирование.

 

Вопросы и задания

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

2. Какие алгоритмы называются линейными?

3. Приведите пример линейного алгоритма:

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

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

5. По алгоритму восстановите формулу.

а1:=1/х 
а2:=а1/х 
аЗ:=а2/х 
а4:=аЗ/х 
у:=а1+а2 
у:=у+аЗ 
у:=у+а4

6. Какое значение получит переменная у после выполнения алгоритма?

х:=1 
у:=2*х 
у:=у+3 
у:=у*х 
у:=у+4 
у:=у*х 
у:=у+5

Восстановите формулу вычисления у для произвольного значения X.

7. Для заданного количества суток (tƒh) требуется определить количество часов (h), минут (m) и секунд (с).

8. Известно, что 1 миля = 7 вёрст, 1 верста = 500 саженей, 1 сажень = 3 аршина, 1 аршин = 28 дюймов, 1 дюйм = 25,4 мм. Пользуясь этой информацией, составьте линейный алгоритм перевода расстояния X миль в километры.

9. Исходное данное — целое трёхзначное число х. Выполните для х = 125 следующий алгоритм.

а:=х div 100 
b:=x mod 100 div 10 
с: =х mod 10 
s:=a+b+c

Какой смысл имеет результат s этого алгоритма?

10. Определите значение целочисленных переменных x и y после выполнения алгоритма.

х:=336 
y: =8 
х:=х div у 
у:=х mod у
 

Электронное приложение к уроку

liniya 

   
  Презентации, плакаты, текстовые файлы Вернуться к материалам урока Ресурсы ЭОР  

 

liniya 

Cкачать материалы урока

 Презентация «Основные алгоритмические конструкции. Следование»

 Презентация «Основные алгоритмические конструкции. Следование» (Open Document Format)

Ссылки на ресурсы ЕК ЦОР

Свободное программное обеспечение: