Расчетно-графическая работа по теме «Алгоритмизация»

Требования. Задание оформляется на отдельных листах по следующему плану:

1. Титульный лист.

2. Теоретическая часть (список вопросов, которые нужно раскрыть см.ниже).

3. Практическая часть

   1. Формулировка задания.

   2. Анализ задачи:

      1. входные данные;

      2. результат;

      3. формулы.

   3. Проектирование алгоритма (блок-схема);

   4. Тестирование алгоритма.

   5. Вывод по задаче.

Список теоретических вопросов

1. Каково происхождение слова «алгоритм»?

2. Приведите определение алгоритма.

3. Что такое исполнитель? Приведите примеры.

4. Из каких элементов состоят алгоритмы?

5. Охарактеризуйте способы представления алгоритмов.

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

7. Что называется «алгоритмическим языком»?

8. В чем состоит свойство дискретности алгоритма?

9. Что означает свойство результативности алгоритма?

10. Что означает «массовость алгоритма»?

11. Каковы основные алгоритмические конструкции?

12. Какие элементы графических схем представления алгоритмов используются для отображения основных алгоритмических конструкций?

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

Пример выполнения практического задания:

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

Вычисление длины гипотенузы по катетам

2. Формулировка задания. Даны два вещественных числа, являющихся величинами катетов некоторого прямоугольного треугольника. Вычислить длину гипотенузы этого треугольника.

3. Анализ задачи.

3.1. Входные данные. Входными данными являются длины катетов x и y.

3.2. Результат. Результатом работы алгоритма является вычисленное значение гипотенузы z.

3.3. Формулы. Будем вычислять гипотенузу по формуле Пифагора.

4. Проектирование алгоритма.

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

2. Детализируем главный алгоритм. Для этого: напишем входные данные и результат в явном виде.

5. Тестирование алгоритма.

Осталось протестировать этот алгоритм вычисления гипотенузы. Расставим на алгоритме контрольные точки A, B, C (см. рис. 2). Контрольные точки ставятся везде, где вводятся или изменяются данные, т. е. после каждого ввода и каждого действия алгоритма (на блок-схеме контрольные точки ставятся после всех параллелограммов и прямоугольников, кроме вывода данных).

Исполнитель начинает выполнять алгоритм с его начала. При движении по алгоритму его активная точка проходит сначала контрольную точку A, затем B, и наконец C.

Зададим входные данные. Пусть катет x = 3, а катет y = 4. Тогда, по формуле Пифагора, гипотенуза такого прямоугольного треугольника должна быть z = 5. Разберем работу алгоритма, представленного на рис. 2. Для этого составим таблицу 1 из значений данных в контрольных точках.

Таблица 1. Тестирование алгоритма вычисления гипотенузы по катетам

Контрольная точка	Значения данных
A	x = 3, y = 4
B	x = 3, y = 4, z = 5
C	x = 3, y = 4, z = 5

6. Вывод. Алгоритм вычислил значение гипотенузы z=5, что совпадает с расчетным значением. Поскольку алгоритм простой, то, скорее всего, он работает правильно. Для большей уверенности в правильной работе алгоритма желательно проверить его еще на нескольких более сложных тестах.

Пример 2. Алгоритм ветвления

2. Формулировка задания. Даны два вещественных числа а, b (а≠b). Найти наибольшее среди них.

3. Анализ задачи.

3.1. Входные данные. Из условия задачи следует, что входными данными являются два вещественных числа a и b.

3.2. Результат. Результатом работы алгоритма является вывод значения равного наибольшему из двух чисел.

3.3. Формулы. Чтобы найти наибольшее из двух вещественных чисел необходимо сравнить их.

4.Проектирование алгоритма.

Детализируем общую блок-схему (см. рис. 1): запишем входные данные в явном виде.

5.Тестирование алгоритма.

При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 3). При движении по алгоритму активная точка исполнителя проходит не все контрольные точки!

Тест 1. Зададим значения двух переменных a = 4, b = 3. Протестируем алгоритм и запишем значения переменных в контрольных точках (таблица 2). Полученная последовательность контрольных точек показывает, по каким ветвям выбора проходит исполнитель: точка С пропущена.

Таблица 2 Тестирование алгоритма нахождения наибольшего из значений (а>b)

Контрольная точка	Значения данных
A	a = 4, b = 3
условие	4>3 – истина (да)
B	a = 4, b = 3, c = 4
D	a = 4, b = 3, c = 4

Итак, мы убедились, что алгоритм вычислил правильное значение и вывел правильный результат. Но в случае рассматриваемой задачи одного теста не достаточно. Мы не знаем, правильно ли будет работать алгоритм, если входные данные будут иными.

Тест 2. Зададим значения двух переменных a = 3, b = 5. Протестируем алгоритм и запишем значения переменных в контрольных точках; получим таблицу 3.

Таблица 3 Тестирование алгоритма нахождения наибольшего из значений (a<b)

Контрольная точка	Значения данных
A	a = 3, b = 5
условие	3>5 – ложь (нет)
С	a = 3, b = 5, c = 5
D	a = 3, b = 5, c = 5

Теперь система тестов полна, и в том, что алгоритм работает правильно, гораздо больше уверенности.

Пример 3. Циклические операторы

Сумма натурального ряда

2. Формулировка задания. Найти сумму первых n натуральных чисел.

Решим данную задачу тремя способами используя «цикл с параметром», «цикл-пока» и «цикл-до».

3. Анализ задачи.

3.3. Формулы. Нужно найти сумму n чисел

1 + 2 + 3 + … + n. (1)

3.1. Входные данные. Из суммы (1) следует, что входным данным является количество первых натуральных чисел n.

3.2. Результат. Результатом работы алгоритма является вывод суммы (1).

4. Проектирование алгоритма.

Детализируем общую блок-схему (см рис. 1):

1) напишем входные данные в явном виде;

2) выведем сообщение о величине суммы;

Заметим, что текущее слагаемое суммы (1) имеет вид i. Тогда сумму можно накопить в сумматоре, если:

1) присвоить ему начальное значение S = 0;

2) прибавлять к сумматору в цикле переменную i, изменяя ее от 1 до n.

Способ 1. Алгоритм с использованием структуры «цикл-пока»

Результат проектирования представлен на рис. 4.

5.Тестирование алгоритма.

При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 4). Зададим количество суммируемых первых натуральных чисел n = 4. Мы должны получить значение суммы первых пяти натуральных чисел S = 10. Протестируем алгоритм и запишем значения переменных в контрольных точках в таблицу 4.

Таблица 4. Тестирование алгоритма нахождения суммы ряда (структура «цикл-пока»)

Контрольная точка	Значения данных
A	n = 4
B	n = 4, S=0, i=1
условие	1<=4 - истина (да)
С	n = 4, S=1, i=2
условие	2<=4 - истина (да)
С	n = 4, S=3, i=3
условие	3<=4 - истина (да)
С	n = 4, S=6, i=4
условие	4<=4 - истина (да)
С	n = 4, S=10, i=5
условие	5<=4 - ложь (нет)
D	n = 4, S=10, i=5

Способ 2. Алгоритм с использованием структуры «цикл-до»

Результат проектирования представлен на рис. 4.

5.Тестирование алгоритма.

При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 5). Зададим количество суммируемых первых натуральных чисел n = 4. Мы должны получить значение суммы первых пяти натуральных чисел S = 10. Протестируем алгоритм и запишем значения переменных в контрольных точках в таблицу 5.

Таблица 5. Тестирование алгоритма нахождения суммы ряда (структура «цикл-до»)

Контрольная точка	Значения данных
A	n = 4
B	n = 4, S=0, i=1
С	n = 4, S=1, i=2
условие	2>4 - ложь (нет)
С	n = 4, S=3, i=3
условие	3>4 - ложь (нет)
С	n = 4, S=6, i=4
условие	4>4 - ложь (нет)
С	n = 4, S=10, i=5
условие	5>4 - истина (да)
D	n = 4, S=10, i=5

Способ 3. Алгоритм с использованием структуры «цикл с параметром»

Результат проектирования представлен на рис. 6.

5.Тестирование алгоритма.

При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 6). Зададим количество суммируемых первых натуральных чисел n = 4. Мы должны получить значение суммы первых пяти натуральных чисел S = 10. Протестируем алгоритм и запишем значения переменных в контрольных точках в таблицу 6.

Таблица 6. Тестирование алгоритма нахождения суммы ряда (структура «цикл с параметром»)

Контрольная точка	Значения данных
A	n = 4
B	n = 4, S=0
С	n = 4, i=1, S=1
С	n = 4, i=2, S=3
С	n = 4, i=3, S=6
С	n = 4, i=4, S=10
D	n = 4, i=4, S=10