Информатика -продвинутый курс



         

ОСНОВНЫЕ ПРИНЦИПЫ РАЗРАБОТКИ И АНАЛИЗА АЛГОРИТМОВ - часть 3


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

Пример 1.

Технология разработки программы решения квадратного уравнения.

На рис. 3.9 проиллюстрирована пошаговая детализация процесса построения алгоритма. Заметим, что для начального шага разработки программы имеем в качеств исходных данных коэффициенты а, b, с квадратного уравнения ax2 + bx + с = 0, а на выходе - значения двух корней х 1, х2.

Пример 2.

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

Попытка быстро ответить на этот вопрос приводит к перебору всех возможн маршрутов коня. Число вариантов перебора чрезвычайно велико, и поиск нужного маршрута лучше поручить компьютеру.

Одной из эвристических стратегий алгоритма может быть следующая. Haчиная с произвольного поля i,j (на рис.3.10 i = 4,j = 4), пытаемся пойти на поле *1, если невозможно, то на поле *2; при неудаче - на поле *3 и т.д. по часовой стрелке

Рис. 3.9. Пошаговая детализация построения алгоритма

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

Итак, исходные данные задачи - произвольные начальные координаты коня i,j от 1 до 8. Результат - возможный маршрут коня из заданного поля. Удачным считается маршрут, содержащий все 64 хода, т.е. полный тур коня.

F Рис.3.10. Иллюстрация к задаче «тур шахматного коня»

Инициализация доски предполагает задание двумерного массива размером 8х8 с нулевыми элементами.


Содержание  Назад  Вперед