:14:49(C) KaravaevaEL, 2008 Алгоритмизация Автор – Караваева Е.Л.

2 Понятие алгоритма Алгоритм – это строгая и четкая последовательность действий, выполнение которых приводит к определенному результату. Требования к алгоритмам 1) Ориентированность на конкретного исполнителя. 2) Понятность для исполнителя (алгоритм составляется в соответствии с системой команд исполнителя). 3) Точность (каждая команда должна определять однозначное действие исполнителя). 4) Конечность (наличие конца алгоритма через конечное число шагов). 5) Результативность (получение нужного результата по окончанию алгоритма). 6) Массовость (применимость для широкого класса задач). 7) Формальность исполнения (во время исполнения алгоритма исполнитель не должен задумываться над сутью выполняемых действий).

3 Способы записи алгоритмов 1. Словесный (описание алгоритма с помощью слов русского языка). Пример. Алгоритм включения компьютера. Подойти к компьютеру. Включить монитор. Включить системный блок. 2. Запись на алгоритмическом языке Пример. Алгоритм нахождения минимального из двух введенных чисел. Начало Ввод числа х Ввод числа у Если х<у То Вывод х Иначе Вывод у Все Конец

4 Способы записи алгоритмов 3. Блок-схема (Графическое представление алгоритма) (будет рассмотрен ниже) 4. Программа (запись алгоритма на языке программирования) Пример. Определение четности введенного числа. На языке BASIC: INPUT Введите целое число; X A$=четное IF X MOD 2<>0 THEN A$=не+A$ PRINT Введенное число, A$

5 Блок-схемы Блок-схемы являются одним из графических способов представления алгоритмов. Блок-схема состоит из блоков, соединенных линиями. Чаще всего используются блоки следующих типов: - выполнение операции; - выбор направления выполнения алгоритма в зависимости от выполнения условия; - ввод/вывод данных; - начало и конец алгоритма.

6 Алгоритмические конструкции Группа шагов алгоритма, выполняемых последовательно друг за другом без каких-либо условий, называется линейной последовательностью. На рис.1. изображена линейная последовательность, состоящая из двух шагов. Ветвление представляет собой алгоритмическую конструкцию, в которой выполнение того или иного шага зависит от истинности условия. Говорят, что конструкция «ветвление» записана в полной форме, если в ней присутствуют команды как для случая истинного условия, так и для его ложности. На рис.2 приведена блок-схема ветвления в полной форме. Конструкция ветвления в полной форме реализуется следующим образом. Если условие истинно, то выполняется действие 1, если условие ложно, то выполняется действие 2.

7 Алгоритмические конструкции Если в ветвлении присутствуют действия только для истинности или только для случая ложности условия, то говорят, что она записана в неполной (в сокращенной) форме. На рис. 3 приведены две блок- схемы ветвления в сокращенной форме. Конструкция ветвления в сокращенной форме реализуется следующим образом. Если выбрано направление, в котором отсутствует действие, то конструкция ветвления не выполняется и управление получает конструкция, следующая за ветвлением.

8 Алгоритмические конструкции Цикл представляет собой алгоритмическую конструкцию, в которой многократно выполняется одна и та же последовательность шагов, называемая телом цикла. Каждое однократное исполнение цикла называется итерацией. Если тело цикла будет выполнено N раз, говорят, что произведено N итераций. Различают два вида циклов: циклы с заранее известным числом повторений и циклы с заранее неизвестным числом повторений. Цикл с заранее известным числом повторений называют циклом с параметром. Блок-схема цикла с параметром помещена на рис.4.

9 Алгоритмические конструкции В циклах с заранее неизвестным числом повторений для того, чтобы определить момент прекращения выполнения тела цикла, используется условие цикла. Если при истинности условия цикл продолжается, то такое условие называется условием продолжения цикла. Если при истинности условия цикл завершается, то такое условие называется условием завершения цикла. В этом случае цикл продолжается до тех пор, пока условие не станет истинным. Различают циклы с проверкой условия перед выполнением очередной итерации и циклы с проверкой условия после выполнения очередной итерации. Первые называются циклами с предусловием (рис. 5), вторые – с постусловием (рис. 6).

10 Алгоритмические конструкции Алгоритмическая конструкция называется вложенной, если она содержится внутри другой алгоритмической конструкции. На рис. 7 команда ветвления вложена в цикл.

11 Задание 1. (Задание А8 демоверсии 2004 г.) Алгоритмическая конструкция какого типа изображена на фрагменте блок-схемы (см. рис. 8): 1) линейная; 2) циклическая; 3) разветвляющаяся; 4) вспомогательная. Решение. На рис. 8 изображен ромб, внутри которого записано условие, и две исходящие из него стрелки. Фрагмент условия представляет собой блок ветвления в полной форме. Ответ: 3.

12 Задание 2. (Задание А6 демоверсии 2005 г.) 1) команду ветвления в сокращенной форме, в которую вложена команда ветвления в полной форме; 2) две команды ветвления в полной форме, одна из которых вложена в другую; 3) две команды ветвления в сокращенной форме, одна из которых вложена в другую; 4) команду ветвления в полной форме, в которую вложена команда ветвления в сокращенной форме. Фрагмент блок-схемы (см. рис. 9) представляет алгоритм, который содержит команды ветвления: Решение. Обе команды ветвления, входящие в блок-схему на рис. 9, - полные, при чем одна из них вложена в другую. Поэтому верным будет вариант ответа 2. Ответ: 2.

13 Задание 3. (Задания А29 демоверсии 2005 г., А6 демоверсии 2006 г.) Определите значение целочисленной переменной х после выполнения следующего фрагмента блок-схемы (см. рис.10) 1) 1; 2) 5; 3) 10; 4) 15. Решение. В блок-схеме присутствует повторяющаяся последовательность действий (цикл). Для того, чтобы не ошибиться при выполнении блок-схемы, составим таблицу (см. Таблицу 1), в которую будем заносить значения переменных и результаты проверки условий на каждом шаге.

14 Задание 3. Таким образом, переменная х после выполнения данного фрагмента программы приняла значение 5, что соответствует ответу под номером 2. Ответ: 2.

15 Задания для самостоятельного решения 1. Определите значение переменной b после выполнения следующего фрагмента алгоритма (см. рис.11): 1) 6; 2) 5; 3) 3; 4) 4.

16 Задания для самостоятельного решения 2. Определите значение переменной a после выполнения алгоритма (см. рис.12): 1) 5; 2) 11; 3) 23; 4) 47.

17 Задания для самостоятельного решения 3. Определите значение переменной s после выполнения фрагмента алгоритма (см. Рис. 13).

18 Исполнение фрагментов программ В условии задачи приводятся эквивалентные тексты программ на трех алгоритмических языках. Задание необходимо выполнить на одном из этих языков. Для исполнения программы удобно составить таблицу. Пример: Определите значение переменных x, y, t после выполнения фрагмента программы. Бейсик ПаскальАлгоритмический x = 5 y = 7 t = x x = y MOD x y = t x := 5; y := 7; t := x; x := y mod x; y := t; x := 5; y := 7; t := x; x := mod (y,x); y := t; 1)x=2, y=5, t=5 2)x=7, y=5, t= 5 3)x=2, y=2, t=2 4)x=5, y=5, t=5 Решение: Составим и заполним таблицу Шаг Значение х после шага Значение у после шага Значение t после шага x=55 не определено y=757 не определено t=x575 x=y MOD x275 y=t255 Ответ: 1.

19 Задания для самостоятельного решения 4. Определите значение целочисленных переменных x, y и t после выполнения фрагмента программы: 1) x=4; y=1; t=0; 2) x=0; y=5; t=4; 3) x=0; y=4; t=5; 4) x=4; y=1; t=5.

20 Задания для самостоятельного решения 5. Определите значение целочисленных переменных b и c после выполнения фрагмента программы: 1) b=3; c=7; 2) b=7; c=3; 3) b=3; c=4; 4) b=4; c=3.

21 Задания для самостоятельного решения 6. Определите значение целочисленных переменных a и b после выполнения фрагмента программы: 1) a=7; b=21; 2) a=7; b=7; 3) a=7; b=14; 4) a=3; b=21.

22 Ответы к заданиям для самостоятельного решения Задани е Ответ