Здесь речь идет совсем о другом. Эта задача была предложена как одна из четырех тем на конкурсе программирования в АФСЕТ несколько лет назад. Вам дана прямоугольная решетка для кроссворда. Найдите белый (т. е. не содержащий вычеркнутых черных клеток) прямоугольник наибольшей площади, вписанный в решетку (квадрат есть частный случай прямоугольника).

На рис. 34 есть прямоугольник площади 8 в левом нижнем углу и есть квадрат площади 9. Это — хороший ответ. Программа, которую вы должны составить, должна читать размеры сетки (число строк и столбцов), затем— координаты черных полей и, наконец, давать прямоугольник наибольшей площади, например, указанием координат двух противоположных вершин.

Для программистов на конкурсе АФСЕТ это не было легкой задачей. Она оказалась едва ли не наиболее трудной задачей, будучи единственной задачей, доставившей мне затруднения (см. головоломку 22, другое упражнение на том же конкурсе). Один из соревнующихся достиг цели, решительно пренебрегая эффективностью. Вы-то не очень ограничены временем (по крайней мере временем размышления или временем программирования). Попытайтесь составить программу, время вычисления которой не слишком быстро растет вместе с размером сетки.

Головоломка 38. Математическая композиция.

Ж.-К. Байиф [BAI], французский язык которого очень отточен, представил эту головоломку под названием «арифметическая композиция» в своей книге, из которой в ее и заимствую, Композиция состоит из четырех вопросов, связанных с вычислением площади. Один из вопросов относится к полной поверхности куба, сторона которого измеряется целым числом метров, Вот ответы учеников на различные вопросы:

Альбер	8	16	12	16
Бернар	12	16	12	18
Клод	12	18	12	18
Дени	16	18	12	20
Эрнест	8	16	10	16
Фернан	12	12	12	22
Гюстав	16	18	12	20
Анри	8	16	10	16
Исидор	16	12	12	20
Жюль	20	12	12	20

(Это — величины площадей в квадратных метрах, предложенные учениками.) Преподаватель ставит 5 за верный ответ и 0 за неверный ответ. Один-единственный из учеников получил 0. Кто оказался первым? Вне всякого сомнения, вы можете сказать больше. Эта головоломка кажется мне особенно подходящей для ее решения на компьютере…

?? Головоломка 39. Другая головоломка Давида Гриса.

Пусть дан вектор, образованный n целыми числами. Подпоследовательностью этого вектора называется набор элементов, в котором индексы идут подряд. Найти подпоследовательность с максимальной суммой. Если вы предпочитаете другую формулировку, то найдите индексы i, j, для которых величина

a_i + a_i+1 + … + a_j−1 + a_j

максимальна. Внимание: время вычисления не должно расти намного быстрее, чем n, когда n увеличивается…

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

И никаких циклов в этом цикле! В ответе вы получаете искомые индексы. Озадачивающе, не так ли? Я потерял на это немало времени. И тем не менее, какое простое решение!

Как вы находите?

Часть II. Первая помощь

1. Случайные числа

Упражнение 2.

Нужно изучить поведение дробной части (x + a)⁸, когда x меняется от 0 до 1. Нарисуйте, хотя бы приближенно, кривую, представляющую эту функцию. Рассмотрите интервал на оси x, в котором значение функции меняется от некоторого целого числа до следующего за ним. Отметьте на кривой точку, в которой ордината равна этому целому, увеличенному на 0,5. Она разбивает область изменения x на два интервала. Равны ли между собой эти две половинки? Если одна из них больше другой — и если это одна и та же половинка для всех интервалов — то у вас больше шансов получать числа, меньшие (или большие, вам будет видно самим), чем 0,5.

Но что касается выбора a, то напомним, что следует избегать соотношения

дробная_часть ((x + a)⁸) = x,

иначе вы вместо случайной последовательности получите постоянную последовательность. Проверьте числа x = 0, x = 0,5 и x = 1.

Упражнение 4.

Вы располагаете генератором случайных чисел, дающим число, содержащееся между 0 и 1, и вы хотите получить случайным образом число между 1 и 6, включая границы. Тогда остается сказать, что вам нужно различать 6 случаев и приписать каждому из случаев значение одного из этих целых чисел.

Почему не разделить интервал (0, 1) на 6 частей?

Или еще по-другому: почему бы не умножить выше случайное число на 6. Тогда оно окажется в интервале (0, 6), исключая 6. Если вы возьмете целую часть результата, то вы получите целое число от 0 до 5, включая границы, с равными вероятностями для каждого числа… Завершить следует вам, я уже сказал слишком много!

Игра 1.

Если вы знаете, как сделать предыдущее упражнение, то это для вас уже не задача. Нужно подделать кости, иначе говоря — сделать так, чтобы одна из граней выпадала чаще остальных. Это должно означать, таким образом, что вместо того, чтобы делить интервал (0, 1) на 6 равных Частей, нужно взять 5 частей равных между собой, а шестую побольше. Легко! Наиболее простое решение состоит в умножении случайного числа на целое, большее 6, и в присвоении новых значений грани,_; которую вы решили предпочесть.

Элементарно, мой дорогой Ватсон!

Игра 2.

Х.-К. Байи упростил задачу, указав две возможные стратегии:

— бросать кость до тех пор, пока не будет достигнута некоторая намеченная заранее сумма (по крайней мере если игрок не будет остановлен по дороге выбрасыванием единицы);

— бросать кость определенное число раз, намеченное заранее.