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

АЛГОРИТМИЧЕСКАЯ КОНСТРУКЦИЯ СЛЕДОВАНИЕ

ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

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

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

Для записи любого алгоритма достаточно трёх основных алгоритмических конструкций:

• следования,
• ветвления,
• Повторения.

( Э. Дейкстра )

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

Следование

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

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

Действие 1

Действие 2

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

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

Начало

Столовую ложку сушёных плодов

шиповника измельчить в ступке

Залить стаканом кипячёной воды

Кипятить 10 минут на слабом огне

Охладить

Процедить

Конец

Линейный алгоритм для исполнителя Робот

СКИ исполнителя Робот: вверх , вниз , влево , вправо и закрасить .

алг узор

нач

закрасить

вправо

вправо

закрасить

вниз

влево

закрасить

вверх

влево

кон

Вычисления по алгоритму

Алгоритм

Шаг алгоритма

Переменные

x

1

y

2

s

3

4

5

х:= 2

у:=х*х

у:=у*у

х:=у*х

s:=x+y

2

-

-

4

2

-

-

2

16

16

-

32

48

16

32

Ответ : s = 48

Целочисленная арифметика

С помощью операции div вычисляется целое частное, с помощью операции mod - остаток.

7 mod 3 = 1

7 div 3 = 2

7 : 3 = 2 (ост.1)

8 div 3 = 2

8 : 3 = 2 (ост.2)

8 mod 3 = 2

10: 3 = 3 (ост.1)

10 div 3 = 3

10 mod 3 = 1

13 div 4 = 3

13 mod 4 = 1

13 : 4 = 3 (ост.1)

11 : 4 = 2 (ост.3)

11 div 4 = 2

11 mod 4 = 3

8 : 3 = 2 (ост.2)

8 div 3 = 2

8 mod 3 = 2

Алгоритм работы кассира

Алгоритм работы кассира, выдающего покупателю сдачу ( s ) наименьшим количеством банкнот по 500 ( k 500), 100 ( k 100), 50 ( k 50) и 10 ( k 10) рублей.

k500:=s div 500

s:=s mod 500

k100:=s div 100

s:=s mod 100

k50:=s div 50

s:=s mod 50

k10:=s div 10

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

Самое главное

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

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

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

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

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

Приведите пример линейного алгоритма из

повседневной жизни.

Запишите линейный алгоритм, исполняя который Робот

нарисует на клетчатом поле следующий узор и

вернётся в исходное положение:

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

Какое значение получит переменная у после

выполнения фрагмента алгоритма?

х:=1

у:=2*x

у:=у+3

у:=у*х

y:=у+4

y:=y*х

y:=y+5

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

Для заданного количества суток ( tfh ) требуется

определить количество часов ( h ), минут ( m ) и секунд ( c ).

Известно, что 1 миля = 7 вёрст, 1 верста = 500 саженей,

1 сажень = 3 аршина, 1 аршин = 28 дюймов,

1 дюйм = 25,4 мм.

Пользуясь этой информацией, составьте линейный

алгоритм перевода расстояния Х миль в километры.

Исходное данное - целое трёхзначное число x .

Выполните для x = 125 следующий алгоритм.

a:=x div 100

b:=x mod 100 div 10

c:=x mod 10

s:=a+b+с.

Чем является результат s этого алгоритма?

Определите значение целочисленных переменных x и

y после выполнения фрагмента алгоритма.

x:=336

У:=8

x:=x div y

y:=х mod у

a1:=1/x

a2:=a1/x

a3:=a2/x

a4:=a3/x

y:=a1+a2

y:=y+a3

y:=y+a4

*

Опорный конспект

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

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

Действие 1

Действие 2

Источники информации

• http://www.cs.utexas.edu/~EWD/EWDwww.jpg - фото Эдсгер Вибе Дейкстра
• http://school-collection.edu.ru/catalog/res/0df0356b-6cff-4f5b-a74e-08122a0ebdf8/? – демонстрация линейного алгоритма «Деление дробей»
• http://www.forchel.ru/uploads/posts/2011-01/1295413504_parovoz2.jpg - поезд
• http://cs9448.vkontakte.ru/u14338764/109925135/y_79d1b2d1.jpg - поезд 1
• http://i.allday.ru/uploads/posts/thumbs/1206872135_028_202.jpg - шиповник
• http://novosibirsk.i-mne.com/img/p/641-789-thickbox.jpg - отвар шиповника
• http://img.gazeta.ru/files3/579/3418579/nornikell.jpg - кассир магазина
• http://p-p.com.ua/-/uploads/articles/022/555/original-8ea90590c78112df3329a77d01428acf.jpg - деньги России