4 Методические указания по выполнению домашней контрольной работы
Методические указания по выполнению задания № 2
Несмотря на множество задач, алгоритмы имеют три основных вида: линейный; разветвляющийся; циклический.
Любой из алгоритмов можно разбить на части или фрагменты, каждый из которых представляет один из выше названных алгоритмов. Поэтому необходимо знать структуру и принципы составления этих трех видов алгоритмов.
Принципы алгоритмизации:
выявить исходные данные, результаты, назначить им имена;
выбрать метод решения задачи;
разбить метод решения задачи на этапы с учетом возможностей ПК;
изобразить каждый этап в виде соответствующего блока алгоритма и указать стрелками порядок их выполнения;
в полученной схеме при любом варианте вычислений:
предусмотреть выдачу результатов или сообщений об их отсутствии;
обеспечить возможность, после выполнения любых операций, продвижения к блоку «останов».
Составленный алгоритм подлежит дальнейшему использованию либо человеком, либо компьютером. После чего должен был получен результат.
Суть исполнения алгоритма: исполнитель четко и аккуратно выполняет указанные операции.
Алгоритм можно использовать только в том случае, если он верен. Однако в достаточно сложных алгоритмах почти всегда содержится ошибка. Поэтому вновь составленный алгоритм подлежит отладке.
Отладка алгоритма – это процесс выявления ошибок в алгоритме и их устранения.
Для отладки выбирается некоторый набор исходных данных называемый текстовым набором. Затем задача решается дважды; первый раз по алгоритму, второй раз каким-либо другим способом. При совпадении результатов алгоритм считается верным.
В разветвляющихся алгоритмах проверку надо проводить по всем ветвям. Обычно целесообразной является проверка и на граничных условиях.
В качестве исходного набора обычно выбирают данные дающие простые результаты вычислений. Если в результате отладки какие-либо данные не сошлись, следует искать место ошибки. После этого следует повторить отладку.
Далее составляется программа по готовому алгоритму. Проводится тестирование программы, отладка.
Тест – это совокупность исходных данных вместе с ожидаемыми результатами. Набор тестов называется полным, если он позволяет активизировать все ветви алгоритма. Неизбыточным, если удаление из набора любого теста лишает его полноты.
Удачно подобранные тесты позволяют не только констатировать факт наличия ошибок, но и локализовать их, т.е. найти место в алгоритме, виновное в получении неверных результатов.
В наборе тестов выделяют три группы:
тесты, проверяющие алгоритм при корректных исходных данных самого простого вида;
тесты, проверяющие алгоритм на границе области определения, в ситуациях, которые могут произойти и на которые нужно корректно реагировать;
тесты, проверяющие алгоритм за границей области определения – ситуации, бессмысленные с точки зрения постановки задачи, но которые могут произойти из-за ошибок пользователя.
Задание. Составить алгоритм по предложенному условию: «В такси одновременно сели 3 пассажира. Когда вышел первый пассажир на счетчике было р1 рублей; когда вышел второй – р2 рублей. Сколько должен был заплатить каждый пассажир, если по окончании поездки счетчик показал р3 рублей? Плата за поездку составляет р0 рублей».
Решение.
Исходные данные: р0, р1, р2, р3.
Результат: S1, S2, S3.
(где Si – заплатил i пассажир)
Выбор метода:
Проанализируем условие задачи:
Из условия задачи следует р0, р1, р2, р3 – неотрицательные числа, причем р1р2р3.
р
1 р2 р3
р0 +
3 пас 2 пас 1 пас
Рисунок 23 – Схема условия задачи
Из схемы (рисунок 23) следует, что:
первый пассажир должен заплатить
второй
третий
Получаем формулы:
Проверим правильность вывода формул:
Пусть р0=1, р1=р2=р3=30 (т.е. вышли все вместе).
р1=р2=р3
р0+
3 пасс.
Рисунок 24– Схема условия задачи
Тогда
все заплатят
рублей.
По формулам:
; 
; 
.
Результаты совпали.
Пусть р0=1, р1=р2=30, р3=40.
Тогда первый и второй пассажиры заплатят рублей. А третий 40-30+11=21 рубль.
р
1=р2 р3
р0+
3 пас. 30 1 пас. 40
Рисунок 25 – Схема условия задачи
По формулам:
Результаты совпали.
Пусть р0=1, р1=30, р2=р3=50.
Тогда
первый пассажир заплатит
рублей. А второй и третий заплатят
рубль.
р 1 р2=р3
р0+
3 пасс. 30 2 пасс. 50
Рисунок 26 – Схема условия задачи.
По формулам:
Результаты совпали.
Пусть р0=1, р1=30, р2=50, р3=60.
Тогда
первый пассажир заплатит
рублей. Второй пассажир
рубль. Третий пассажир
рубль.
р
1 р2
р3
р0 +
3 пас 30 2 пас 50 1 пас 60
Рисунок 27– Схема условия задачи
По формулам: ;
;
.
Результаты совпали.
Графическое описание алгоритма представлено на рисунке 28.
_
+
Рисунок 28 – Алгоритм решения задачи
Таблица тестирования
Таблица 1 – Результаты тестирования алгоритма
p0 |
1 |
1 |
1 |
1 |
1 |
1 |
p1 |
3 |
3 |
3 |
3 |
0 |
-5 |
p2 |
3 |
3 |
6 |
6 |
0 |
3 |
p3 |
3 |
6 |
6 |
9 |
0 |
4 |
По алгоритму |
||||||
S1 |
2 |
2 |
2 |
2 |
1 |
данные введены некорректно |
S2 |
2 |
2 |
3.5 |
3.5 |
1 |
|
S3 |
2 |
5 |
3.5 |
6.5 |
1 |
|
Расчет другим способом |
||||||
S1 |
2 |
2 |
2 |
2 |
1 |
данные введены некорректно |
S2 |
2 |
2 |
3.5 |
3.5 |
1 |
|
S3 |
2 |
5 |
3.5 |
6.5 |
1 |
|