Построение диалоговых алгоритмов

Квант 1986, №11 с. 40, 41, 42, 48 Тег 3UBX

Кандидат технических наук
В. А. КАИМИН

Эта заметка предназначена в первую очередь десятиклассикам, изучающим курс «Основы информационных и вычислительных технологий», но будет полезна и всем тем, кто имеет дело с персональными ЭВМ.

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

Диалоговые программы в зависимости от назначения можно подразделить на игровые, учебные, деловые и инструментальные. Игровые программы служат для развлечения в свободное от работы или учебы время. Учебные программы применяются для обучения школьников или студентов. Деловые программы используются для решения производственных задач, накопления и обработки информации. Инструментальные программы используются для создания новых программ.

В основе любых диалоговых программ лежат определенные правила и алгоритмы ведения диалога. Обязательными правилами для ведения любого диалога являются:

сообщи («Добрый день»
запрос («Ваш имя», имя)
вывод («2·2=», x, «?»)

В команде « сообщи» указывается стандартная фраза, сообщаемая партнеру по диалогу; в приведенном примере — это фраза «Добрый день». В команде « запрос» содержится два аргумента: первый аргумент — фраза-запрос, которая передается партнеру, а второй аргумента — это имя переменной, куда будет записан ответ (фраза или число, в зависимости от типа переменной). Команды типа «вывод» может содержать один или несколько аргументов — это либо фразы, либо имена переменных, из которых обращается сообщение — «вывод». Эти три команды мы прибавим к алгоритмическому языку из учебника. Приведем пример построения диалогового алгоритма. (Для экономии места здесь и ниже часть заголовка программы опущена.)

алг знакомство
нач
« сообщи («Добрый день»
запрос («Ваш имя =», имя)
вывод («Рад познакомиться», имя!»)
кон

Пример диалог:

В качестве следующего примера рассмотрим простейший диалоговый алгоритм для игры «угадай-ка». В игре участуют два лица: первого действующего лица загадывает некоторое целое число x в интервале от 1 до 100, а второе пытается угадать его, указыва числа: p₁, p₂,…. В ответ на предъявление числа первого лица сообщает:

«отлично», «мало» или «много» в зависимости от соответствий между указанным и задуманным числами. Игры заканчиваются словами «молодец», «умница» сразу после отладывания задуманного числа.

Алгоритм ведения диалога для первого лица (им будет ЭВМ) и пример диалога приводается ниже. В алгоритме используется специализная функция «x := случайное (a, b)», которая дает некоторое случайное целое число между a и b.

алггра: угадай-ка
нач
x: = случайное (1, 100)
собщи («угадай число»)
собщи («от 1 до 100»)
запрос («число ==», p)
пока p≠x
ни
если p<x,
то сообщи («мало»)
инчае сообщи («много»)
все
запрос («число ==», p)
ки
собщи («отлично»)
собщи («молодец, умница»)
кон
Пример диалога (загадано x=67):

Угадай число
от 1 до 100
число = ? 50
мало
число = ? 75
много

число=? 62
мало
число=? 67
отлично
молодец, умница

Второе лицо может подбирать числа-потезы многоимещи способами. Лучший способ гарантирует угадаивание чисел для данного диапазона от 1 до 100 за 7 шагов. В основе этого способа лежит принцип деления интерала пополам (см. «Квант» № 10, с. 49).

Составление алгоритмов ведения диалога и конструкрование диалоговых программ для ЭВМ можно системати-zировать (ср. «Квант» № 10, с. 47). Дополнительным этапом при систематическом конструкровании диалоговых алгоритмов и программ является предварительное составление сценария диалога.

Сценарий ведения диалога — это описание совокупности всех сообщений, которые предоставляются партнеру по диалогу, и системы реакций в ответ на его сообщения. Для единого описания совокупности сообщений в информаτικе используется специализная, но не сложная система обозначений. Рассмотрим ее на примере описания сценария «игра: угадай-ка».

Сценарий «игра: угадай-ка»

Здесь p — целое число

Здесь в красный кругок обведен переменный элемент текста (собщения второго лица). В красную рамку помещена переменная часть текста, описывающая ответы первого лица на очередное число-гипотезу. В фигурых скобках справа указывются ответы, которые выбираются в зависимости от определенных условий (сравнения загаданного и указываемых чисел). В фигурых скобках следа указывются части текстов, которые повторяются (здесь — это повторения «запрос — ответ» при угадаивании чисел).

Составление алгоритмов и программ с предварительным описанием сценария позволяет заранее продумать понятность, логичную связность и тактичность в ведении диалога.

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

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

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

Задча: Бросание мяча в корзину
Дано:
L — расстояние до корзины (м)
V₀ — начальная скорость (м/с)
α₀ — угол бросания (эрад)
D — диаметр корзины (м)
Требуется: попал — признак попадания r — остаток расстояния (м)
Связь:
r = |L - l| (остаток расстояния)
попал = {r < D/2} (условие попадания)
l = V₀ · t (дальность полета)
0 = V₀ · t - gt²/2 (условие попадания)
V₀ = V₀ · cos(α₀ · π/180) (горизонтальная скорость (t = 0))
V₀ = V₀ · sin(α₀ · π/180) (вертикальная скорость (t = 0))
g = 9,81 (ускорение свободного падения)

При
{D > 0 (положительность ширины корзины)
V₀ > 0 (положительность скорости)
0° < α₀ < 90° (допустимость угла)
Метод
попал = ||L - l| < D/2 (условие попадания)
r = |L - l| (остаток расстояния)
l = v₀² · sin(2α₀ · π/180)/g (дальность полета)
g = 9,81 (ускорение свободного падения)

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

Сценарий «Игра с мячом»

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

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

алг «бросание мячей в корзину»
начlint игра
вещL, D
сообщи («бросание мячей в корзину»)
D := случайное (0.1; 0.5)
вывод (диаметр корзины =>; D)
игра:=да
пока игра:=да
ни
L:=случайное (10; 250)
вывод («расстояние до корзины=>; L)
бросание мяча в корзину
запрос («попраем еще? [да/нет]», игра)
кii
сообщи («спасибо за игру»)
кон

(Окончание см. на с. 48.)

получаем ответ: искомая площад равна $(7\sqrt{3}-\pi)/3$ .

Конечно, приведенные шесть задач далеко не исчерпывают все типы задачи на координатной плоскости, предлагавшихся (в последние 10 лет) на вступительных экзаменах в МФТИ. Мы постарались разобрать наиболее однозначную раздела — задач на касательные к графикам функций — по той причине, что совсем недавно в «Кванте» была опублкована большая статья, посвященная именно таким задачам (см. «Квант», 1986, № 3, с. 51). Чтоы у читателей составилось более полное представление, мы предлагаем им самостояльно решить следующее утражение:

1 (1984 г.). Через точку $M$ (5; 6) проведена касательная к параболе $y=6x^2/25$ , пересекающая ось абсцисс в точке $N$ , а ось ordинат в точке $P$ . Найдите радиус окружности, вписанной в треугольник $NOP$ ( $O$ — начало координат).

2 (1979 г.). К параболе $y=\frac{1}{2}x^2+\frac{5}{2}$ в двух ее точках проведены касательные, пересекающие в точке $A$ и пересекающие ось абсцисс в точках $B$ и $C$ . Треугольник $ABC$ — равноведенный, и его угол $ABC$ равен $2\pi/3$ . Найдите площад этого треугольника.

3 (1978 г.). На координатной плоскости даны две прямые $y=-x$ и $y=5x-6$ . Найдите: 1) значения $a$ и $b$ , при которых обе данные прямые касаются параболе $y=x^2+ax+b$ ; 2) координаты точек касания.

4 (1982 г.). В точках $A$ и $B$ парабoles $y=x^2-3x+1$ проведены касательные, угловой коэффициент одной из касательных равен 1.

Построение диалоговых алгоритмов

(Начало см. на с. 40.)

алг. «бросание мяча в корзину»
apr. веш $L, D$
нач лит попал
веш $v0, a0, l$
попал:=нет
пока попал:=нет
нищ
запрос («угол бросания», $a0$ )
запрос («начальная скорость», $v0$ )
выбор
при $v0\leqslant0$
попал:=нет
вывод («странаная скорость»)
при $a0\leqslant0$ или $a0\geqslant90$
попал:=нет
вывод («страный угол»)
инчете

расчет попаданий
выбор
при попал:=да
вывод («молодец, попал»)
при $l<L$
вывод («недолет», $r$ , «метров»)
при $l>L$
вывод («перелет», $r$ , «метров»)
все
все
кц
кон
алг. «расчет попаданий»
apr. веш $D, L, v0, a0$
рез: лит попал
веш $r$
нач веш $g, l$
$g:=9,81$
$l:=(v0)^2\cdot\sin(2\cdot a0\cdot\pi/180)/g$
$r:=L-l$
если $r<D/2$
то попал:=да
инчете попал:=нет
все
кон