Разработка алгоритма решения задачи

На рис. 8 показан укрупненный алгоритм решения поставленной задачи. На рис. 9 - 12 показаны основные шаги поэтапной детализации основного алгоритма.

   

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

Входы в детализирующие блок-схемы и выходы из них показаны окружностями с номерами блоков — источников информации и получателей результатов.

Значком & на рис. 11 обозначена логическая операция И.

Пример 3

П оскольку тестирование вручную алгоритма решения задачи о шахматном коне было бы достаточно громоздким, рассмотрим технологию тестирования  на примере алгоритма Евклида (рис. 14).

Для тестирования вручную следует оставить достаточно свободного места справа от блок-схемы. Контрольный пример не должен быть слишком сложным - это затрудняет тестирование, но и не быть тривиальным - это может привести к случайному совпадению с правильным решением. В первом столбце таблицы справа от блок-схемы, записываются переменные или условия, значения которых могут изменяться. Начиная со второго столбца сверху-вниз записываются результаты выполнения алгоритма. Начало нового цикла соответствует добавлению нового столбца таблицы. Исполнитель (разработчик алгоритма) должен выполнять команды формально, строго придерживаясь предписаний в блок-схеме. 

Задание

Разработать алгоритм и программу решения задачи, Задачу выбрать в разделе «Варианты заданий к работе» согласно вашему варианту. Оформить отчет о работе.

Порядок выполнения

1. Внимательно ознакомиться с теоретическими сведениями, приведенными в лабораторной работе;

2. Выбрать задание из раздела «Варианты заданий к работе», с номером равным вашему варианту;

3. Последовательность решения задачи (оформляется в рукописном виде):

• Произвести словесную формулировку задачи;

Пример: Вычислить наибольший общий делитель (НОД) двух натуральных чисел A и B, используя алгоритм Евклида.

• Формализовать поставленную задачу, указав, что дано в задаче и что нужно найти;

Пример:

Дано: A, B.

Найти: НОД.

• Составить контрольный пример для тестирования задачи;

Пример: A = 35; B = 14; НОД = 7.

• Произвести словесное описание алгоритма;

Пример:

1. Ввод А и В;

2. Если А = В, то Переход к 7, иначе Переход к 3;

3. Если А > В, то Переход к 4, иначе Переход к 5;

4. А = А – В;

5. В = В – А;

6. Переход к 2;

7. Вывод «НОД=А».

Нарисовать блок-схему алгоритма решения задачи;

Пример:

• Нарисовать таблицу с тестом алгоритма справа от блок-схемы. Таблица составляется согласно следующим правилам:

1. Строки располагаются напротив соответствующих операций в блок-схеме;

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

3. Остальные столбцы должны содержать значения переменных или результат логического выражения для каждой случая выполнения данной операции в блок-схеме;

Пример:

	A B A=B A>B B A НОД	35 14 нет да 21
			нет да 7	нет нет 7	да
					7