|
** Новогодний конкурс интроспективных программ **
|
Каждый из нас лишь выиграет, создавая время от времени "игрушечные"
программы с заданными искусственными ограничениями, заставляющими нас до
предела напрягать свои способности. ...
Искусство решения мини задач на пределе своих возможностей оттачивает
наше умение для реальных задач.
Д. Кнут 1
|
Наверное, нет такого программиста, который бы не слышал о знаменитой задаче, сформулированной еще Винером. Смысл этой задачи состоит в написании программы, при работе которой на устройстве вывода появляется полная копия ее исходного текста. Причем любые обращения к файлам с исходными текстами или использование всевозможных системных штучек (например, знание некоего адреса сегмента памяти, где может храниться исходный текст исполняемой программы) запрещены. Такая программа называется интроспективной. Чаще всего при описании этого "орешка" ссылаются на известную книгу Чарльза Уэзерелла [2]. Хорошо известна и теорема (см., например, [3]) о том, что практически любой язык программирования позволяет написать такую программу.
"Компьютерра" в прошлом году уже обращалась к теме интроспективных программ. В своей статье "Квин-программы, или: 1 LIST" ("КТ" ##381, 382) Константин Кноп привел с десяток решений на различных языках программирования. Мы же поставим вопрос несколько иначе: требуется написать не любую, а как можно более короткую интроспективную программу!
Чтобы уравнять всех участников нашего конкурса, ниже будет определен некий простой язык программирования PIBAS, который содержит все необходимые средства для написания интроспективной программы. Этот язык, равно как и сама задача, был предложен участникам четвертьфинальных соревнований центрального региона России, проводившихся в Рыбинске в рамках студенческого командного чемпионата мира по программирования сезона 2002/2003 года .
Итак, мы предлагаем читателям написать как можно более короткую (по числу символов) интроспективную программу на языке PIBAS.
Программа признается верной, если при ее исполнении будет осуществлен вывод строки, совпадающей с исходным текстом исполняемой программы.
Лучшее решение будет опубликовано на страницах журнала.
Описание языка PIBAS
- Программа на языке PIBAS состоит из одного или нескольких операторов, разделенных символом ";" (точка с запятой). Программа записывается в одну строку, длина которой не превышает 32 тысячи символов.
- В языке имеются два вида операторов: оператор присваивания значения строковой переменной и оператор вывода строкового выражения.
- Оператор присваивание имеет вид: <строковая переменная>=<строковое выражение>.
- Строковая переменная задается одиночной заглавной латинской буквой.
- Строковое выражение - это либо строковая переменная, либо строковая константа, либо функция вырезания подстроки, либо конкатенация строковых выражений через символ "+" (плюс).
- Строковая константа - это строка любых печатных символов, заключенная в двойные (""") или одинарные ("'") кавычки за исключением кавычки того вида, которая используется для ее ограничения.
Примеры: 'Rybinsk', "O key!", "I don't know solution".
- Функция вырезания подстроки имеет вид: $(<строковая переменная>,<положительное число без знака>,<положительное число без знака>).
Первым параметром задается строковая переменная, из значения которой производится вырезка. Второй параметр задает номер начального символа вырезаемой подстроки, а третий параметр задает длину этой подстроки. Нумерация символов внутри строки начинается с единицы.
- Оператор вывода имеет вид: ?<строковое выражение>.
Суммарная длина всех выведенных строк не должна превышать 32 тысячи символов.
Примеры
Программа на языке PIBAS |
Результат работы |
?" Hello, "+'World!' |
Hello, World! |
A='World, Hello!';?$(A,8,5);?", ";B=$(A,1,5)+'!';?B |
Hello, World! |
Чтобы проверить свое решение, читатели могут либо скачать с сайта
pic200x.chat.ru
интерпретатор (автор Михаил Копачев) языка PIBAS,
либо воспользоваться тестирующей оболочкой на сайте
acm.timus.ru, где
под номерами 1224-1232 размещены задачи рыбинского четвертьфинала, либо
написать свой интерпретатор.
Решения принимаются до 25 декабря включительно по адресу
vpinaev@mail.ru
с пометкой в теме письма "Introspective program".
Список литературы
1. Лекции лауреатов премии Тьюринга: Пер. с англ./Под ред. Р. Эшенхёрста. - М.: Мир, 1993.
2. Уэзерелл Ч. Этюды для программистов. - М.: Мир, 1982.
3. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -М.: МЦНМО, 1999.
Скачать архив с программами
|
|