Этюды для программистов

Указания исполнителю. Теоретически нельзя удовлетворить требованию, чтобы любые два лабиринта (даже при одинаковых m и n) были различны, поскольку существует лишь конечное число лабиринтов любого наперед заданного размера, а программу можно вызвать большее число раз. Однако число лабиринтов какого-нибудь размера очень велико, и поэтому вероятность повторения лабиринта можно сделать очень маленькой. Практически это достигается, если программа будет производить «случайный» выбор различных вариантов, опираясь на какое-либо доступное ей, но неуправляемое значение (обычно берут дату и время вызова программы). Варианты, между которыми выбирает программа, это, например, положение входа и выхода и положение хотя бы нескольких внутренних разрушаемых стенок. При отладке разумно будет отключить механизм случайного выбора, чтобы изменения результата работы вызывались только изменениями самой программы.

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

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

Длительность исполнения. Одному исполнителю на 3 недели.

9. Познай самого себя, или Программа, печатающая собственный исходный текст

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

Тема. Напишите программу, печатающую копию собственного исходного текста. Вывод не должен содержать «управляющих» карт или другой информации, зависящей от системы. Печатается только то, что перфорируется для компилятора. Однако ваша программа ничего не должна вводить; ей не следует опираться на системные «штучки», например на знание того, что конкретный компилятор оставляет копию исходной программы в непомеченном COMMON-блоке. Проследите, чтобы программа давала одинаковый результат независимо от места и времени выполнения.

Указания исполнителю. Не поддавайтесь отчаянию и страху, даже если тринадцатая попытка оказалась неудачной! Подобные программы называются интроспективными, и существует теорема, в которой утверждается, что интроспективную программу можно написать на любом «достаточно мощном» языке. Все обычные языки программирования — достаточно мощные. Для решения требуется лишь взглянуть на язык под соответствующим углом зрения. Программа, вероятно, займет не более 30–40 строк.

Инструментовка. Годится любой язык.

Длительность исполнения. Одному исполнителю на 1 неделю.

Литература

Брэтли, Милло (Bratley P., Millo J.). Computer Recreations Self-Reproducing Automata. Software — Practice and Experience, 2, pp. 397–400, 1972.

Эту статью нужно читать только в крайнем случае, поскольку в ней представлено полное решение задачи.

Роджерс (Rogers H., Jr.). Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, NY, 1972. [Имеется перевод: Роджерс X. Теория рекурсивных функций и эффективная вычислимость. — М.: Мир, 1972.]

Чтение этого превосходного введения в теорию рекурсивных функций требует усердия, но вы будете вознаграждены полнотой и ясностью полученной картины. Главы 1–3 образуют достаточный фундамент; результаты об интроспекции содержатся в параграфах 11.1, 11.2 и 11.4.

10. Не прячьте ваши денежки, или Расчет дохода от вложенного капитала