По индукции? Почему бы и нет? Напишите мне, если получится…
Головоломка 19.
Не пренебрегайте крохами информации, которые можно извлечь из текста программы. Вполне правдоподобна гипотеза, что eps — параметр, характеризующий точность, маленький и потому вещественный. Следовательно, p и q, и — вследствие этого — a и b имеют хорошие шансы оказаться вещественными. Примите это как гипотезу, касающуюся типа данных и результата.
Вы не можете исследовать плоскость a, b, чтобы увидеть, что же именно вычисляет эта программа. Но можно сделать несколько простых замечаний. Пусть f(a, b) — значение, вычисляемое программой.
Вы без особых усилий сумеете показать, что
f(a, b) = f(b, a),
f(ac, bc) = cf(a, b)
и вследствие этого
f(a, b) = bf(a/b, 1).
Ho g(x) = f(x, 1) — функция только одного аргумента. Можно ограничиться областью x ≥ 1. Я написал программу, вычисляющую g (простой и очевидный вариант предыдущей программы), а затем вычислил g для
x = 1, 2, 3, …, 10,
x = 1.1, 1.2, 1.3, …, 1.9.
Природа функции g становится очевидной, если исходить из этой таблицы. Уразумев, что именно нужно доказать, мы справимся с этим без труда.
3. Игры без стратегии
Игра 6.
Единственная задача: считать белые шашки. На самом деле, черные можно получить, сравнивая шашку на шашкой в тайной комбинации и в комбинации, предложенной игроком.
Для подсчета белых шашек у вас есть много возможностей.
1. Во время подсчета черных шашек удалите из тайной комбинации и из комбинации, предложенной игроком, находящиеся в соответствии элементы (имеющие одинаковые значения и одинаковые места). Затем для каждого из элементов, оставшихся в предложенной комбинации, посмотрите, участвует ли он в тайной комбинации, и если да, то учтите его белой шашкой и удалите его из тайной комбинации.
Этот метод требует, чтобы вы создали копию тайной комбинации, Это стоит не слишком дорого…
2. Для каждого из возможных значений шашек (6, если есть 6 цветов) подсчитайте число шашек этого цвета в тайной комбинации и в предложенной комбинации. Меньшее из этих двух чисел равно сумме белых и черных шашек, отвечающих этому цвету (почему?).
Так как вы нуждаетесь в подсчете по цветам шашек тайной комбинации и так как эти величины не меняются в течение партии, то вам может оказаться полезным сделать этот подсчет до запрашивания первой комбинации игрока, а затем сохранять его в виде таблицы…
Игра 7.
Для программирования нет совершенно никаких трудностей. Действительно, от вас требуется принять только одно решение; как вы представите игру в вашей программе?
У вас много возможностей.
1. Никакого внутреннего представления игры. Скорость движения машин и интервалы между машинами суть постоянные величины, которые вы можете поместить в таблицу или каждый раз пересчитывать.
Вы можете задать себе с помощью маленькой таблицы положение крайней левой машины на каждой строке. Все остальное можно отсюда вывести. Но вам придется проделать немало вычислений к моменту вывода на экран.
2. Можно сохранять каждую строку в памяти в виде цепочки символов (за исключением, быть может, первых символов, крайних слева). Тогда вывод на экран очень прост. Передвижение машин влево можно получить, удаляя заданное число символов в начале цепочки и добавляя столько же символов справа, соблюдая условия правильного расположения стрелок на правильных местах.
Вам не нужно экономить ни время вычисления, ни объем памяти. Выберите решение, которое, как вам кажется, проще всего реализовать…
Игра 8.
Перемещение шадока почти не составляет проблемы: вы читаете данную в ответ цепочку символов. Если она содержит П, то абсцисса шадока увеличивается на 1, и т. д.
Перемещение многочисленных гиби немного более сложно. Для каждого из гиби нужно найти ближайший к нему цветок. Если у вас есть таблица, задающая положения цветов, то вы ее полностью перебираете и отыскиваете ближайший. Если у вас такой таблицы нет, то нужно вертеться кругами вокруг каждого из гиби, чтобы найти ближайший цветок. Первое решение кажется лучшим.