Примеры решения задач. 1) Содержательная задача – расчет токов и напряжений в электрической цепи

Продолжение примера 1.3

Пример 1.9.

1) Содержательная задача – расчет токов и напряжений в электрической цепи.

2) Математическая модель – отношения, заданы законами Ома и Кирхгофа в виде системы линейных уравнений, определяющих электрическую сеть.

3) Задача порождения суть нахождение решения системы линейных уравнений в виде значений токов и напряжений в элементах сети.

4) Порождающая (вычисляющая) система функций, например, алгоритм Гаусса.

5) Программа – стандартная программа, например, из пакета «MatLab».

1) Содержательная задача – построить для каждого города a, b, c, d, e список городов, достижимых за не более чем два перелета.

2) Математические модели (структуры данных):

а) Таблица (матрица) (см. рис. 1.1 а)).

б) Граф (см. рис. 1.1 б)) в виде набора пар, задающих

отношения a.

3) Задача заключается в создании порождающей функции (алгоритма), входом которой является имя города, а выходом – список городов достижимых за два перелета, полученный из таблицы, или дерево достижимости 2-го порядка (см. рис. 1.1 в) по графу авиатрасс.

При проектировании программ очень важна техника программирования, которая определяется способом взаимодействия пользователя с программой в процессе решения задачи. Можно определить два стиля программ: 1) закрытая программа (кнопка «вход», кнопка «выход») 2) интерактивная программа (взаимодействие пользователя через экран). Далее приводятся примеры решения задач, использующие технику программирования «for sight». При этой технике программа проектируется «от экрана». Экран разбивается (условно) на две части: 1) «operating board», где отображается картинка (picture) для входных, промежуточных и выходных данных, 2) «control board» – где реализуется панель (может быть кнопочная) управления программой.

Задача 1. Разместить четыре «+» в квадрате, заданным системой неравенств 1£ х £ п, 1£ y £ m. Это типичная задача порождения. Вид части экрана (operating board) для п = 3, т = 3 показан на рис. 1.2 б. На части экрана (control board) три кнопки: 1) ввести параметры «п, т»; 2) высветить картинку; 3) стереть картинку. Рекомендуется табличная структура данных.

Задача 2. Справочник для авиапассажира. Справочник содержит 10 городов и позволяет задавать между городами авиатрассы (см. пример 1.3). Справочник должен производить следующие процедуры и допускать запросы:

1) ввести список имен городов (задача порождения);

2) ввести список авиатрасс и отобразить их на экране (задача порождения);

3) ответить на вопрос: «В какие города я могу попасть из города «х» менее чем за п перелетов?» (задача порождения);

4) ответить на вопрос: «Могу ли я попасть за п = п* перелетов из города «х» в город «y»?» (задача распознавания).

Структуры данных выбираются произвольно.

Задача 3. Лабиринтная задача. Блуждание Тезея по лабиринту по правилам и с нитью, данными ему Ариадной.

1) Содержательная задача – нахождение (порождение) пути в лабиринте от точки входа (вх) до точки (выхода).

2) Структура данных – множество пар залов, соединенных переходами (см. рис. 1.3 а) L = {0-1, 1-2, 2-3, 3-4, 4-5, 3-9, 9-6, 9-10, 9-11, 6-8, 6-7}. Предполагается, что переходы проходимы в любую сторону, поэтому граф переходов симметричный.

3) Функция нахождения пути состоит из комбинации трех функций на каждом шаге (когда Тезей находится в одном из залов): а) функции, порождающей все имеющиеся переходы из зала; б) распознающей функции, которая распознает свободные переходы для дальнейшего движения, в) функции, порождающей метки пройденного пути.

Последовательность (траектория) прохождения залов Тезеем кодируется так называемым кодом Тезея (Т-кодом). Для рис. 1.3а и правила правой руки для выбора зала, траектория блуждания будет

Т = 0×1×2×3×4×5×4×6×7×6×8×6×9×10×9×11×9×3×2×1×12.

На экране в «operating board» отображается пошаговое движение Тезея, результаты протягивания (сматывания) нити и отметка прохождения переходов.

а) Уравнение: y = 0.5 x + 1 б) Система неравенств: 1 £ х £ 3;

1 £ у £3.