Приятные билеты

Скоротать время в транспорте помогает рассматривание билетов. Как известно, счастливыми билетами считаются такие, у которых сумма трех левых цифр равна сумме трех правых. Сколько счастливых билетов в рулончике с миллионом билетов? Посчитать без программки и устно - прекрасная гимнастика для разминки. Теперь о приятных билетах. Это такие, у которых результат действий с тремя левыми цифрами можно приравнять результату действий с тремя правыми, причём можно использовать все операции - арифметические и алгебраические. Есть чудаки, утверждающие, что все билеты приятные… Просто надо немного подумать…

Например, вчера в трамвае попался билет с номером 739330 и я принялся отыскивать, в чем его приятность…

Минут через 20 разродился решением:

7+3-9=33^0

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

(7+3)*9=3*30

Как я мог проглядеть этот вариант?

Наверняка есть еще решения, но я, сколько не думал, ничего больше не нашел. Если кто найдет - пишите - имя нашедшего будет занесено в Доску Почета на www.arbuz.narod.ru

Фортуна в колесе

Есть только один верный способ заработать деньги на игре в рулетку - купить казино.

Речь в этой статье, конечно же, пойдет о рулетке. Я не стану рассказывать о том, сколько денег проигрывали в казино знаменитости мира сего. Мои намерения диаметрально противоположны: показать, каким образом в рулетку можно выигрывать.

На зеленом суконном поле расположены тридцать шесть номеров от 1 до 36 и один особый номер - зеро. Эти номера следуют друг за другом без видимого порядка, окрашенные поочередно в красный и черный цвет. Зеро (нуль) обычно окрашивается в зеленый цвет и не принадлежит ни к красным, ни к черным номерам. Игрок может делать ставку на номера (то есть на любой из 37 номеров) и на так называемые простые и сложные шансы. Простых шансов существует шесть: красное, черное, чет, нечет, пасс (номера от 19 до 36) и манк (номера от 1 до 18). Сложные шансы состоят в том, что ставят на два, три, четыре, шесть или двенадцать номеров. Выигрыш за простой шанс равен поставленной ставке (а за один номер - 35 ставкам). Выигрыши на сложных шансах: за два номера - 17 ставок, за три номера - 11 ставок, за четыре номера - 8 ставок, за шесть номеров - 5 ставок, за двенадцать номеров - 2 ставки. Когда выпадает зеро, ставки на простые шансы блокируются. После этого игрок может действовать двояко: либо ждать следующего раза (если выпадет простой шанс, на который была поставлена ставка, то она возвращается владельцу целиком), либо потребовать у крупье возмещения половины сделанной ставки.

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

Очевидно, что для математического анализа рулетки применима теория вероятностей - тридцать семь номеров выпадают с равной вероятностью. Если бы не было поля зеро, то у играющего были бы одинаковые шансы на выигрыш и проигрыш, а наличие зеро делает рулетку игрой, выгодной для заведения: в случае выигрыша игрок вместе с возвращаемой ставкой получает 36 ставок, хотя в рулетке 37 номеров! Иначе говоря, математическое ожидание выигрыша для казино составляет 1/37 сделанных ставок. То есть каждый игрок, ставящий на номера, всякий раз теряет в среднем 1/37 своей ставки. Вероятность выигрыша для такого игрока равна 18/37. Эта величина, казалось бы, почти равна 1/2. Но тем, кто пренебрегает словом "почти", я напоминаю, что все казино мира зарабатывают деньги именно на разнице между 1/2 и 18/37. (При ставках на простые шансы вероятность выигрыша игрока даже чуть больше, так как в этом случае при выпадении зеро игрок теряет лишь половину своей ставки. Но все равно она меньше 1/2, и с этим ничего поделать нельзя.)

Итак, игра в рулетку без системы невыгодна, причем тем более невыгодна, чем дольше играть. А как можно играть "по системе"? Азартными игроками было придумано великое множество систем игры, явно или неявно основанных на наличии у шарика памяти. Некоторые рекомендуют ставить на проигрыш (выпало красное - поставить на черное), некоторые - ставить на выигрыш. Широко используется стратегия чередования: поочередно ставить на красное и черное или, если вам так хочется, на чет и нечет. Иногда советуют увеличивать ставки в случае выигрыша и уменьшать в случае проигрыша, иногда советуют делать прямо противоположное. Азартному игроку остается лишь выбрать, согласно какой стратегии он будет проигрывать деньги. Но перед нами стоит другая задача - нам нужно выиграть в рулетку. Поэтому давайте обратим внимание на стратегию Д'Аламбера.

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

Стратегия Д'Аламбера была бы беспроигрышной, если бы игрок обладал бесконечным капиталом, а ставки не были бы ограничены. Но, увы, у вас в кармане наверняка нет неразменного доллара, а казино строго блюдет свой интерес. Кроме того, эта стратегия неудобна тем, что приходится оперировать большими суммами, а выигрыш сравнительно мал. Тем не менее большинство из людей, использующих эту стратегию, выигрывает. Здесь нет никакого противоречия, просто возможный проигрыш гораздо больше, чем выигрыш. Если вам не повезет, то, сделав десять ставок, вы проиграете десять раз подряд, и общий проигрыш составит 1023 доллара. Но вероятность такого исхода равна примерно одной тысячной, а в остальных 999 случаях вас ждет приятный выигрыш в один доллар.

Существует еще несколько вариантов стратегии удвоения, впрочем, не слишком отличающихся друг от друга. Различаются в них только принципы увеличения ставок при проигрыше партии. Так, например, ставки могут не удваиваться, а утраиваться или учетверяться, а могут увеличиваться и таким образом: 1 доллар - 3 доллара - 6 долларов - 12 долларов и т. д. (в этом случае выигрыш, начиная со второй ставки, составит не один доллар, а два). Есть вариант, в котором начальные ставки уменьшают в случае выигрыша и увеличивают в случае проигрыша (конечно, при этом начальная ставка должна превышать минимальную). Все варианты, конечно, допускают игру и с меньшей суммой денег, нежели 1023 начальные ставки, но при этом увеличивается риск проигрыша. Кстати, вы всегда можете сдаться после седьмого проигрыша, если у вас есть иррациональное предчувствие еще большего проигрыша…

И еще о предчувствиях. Предположим, вы заранее решили сыграть сто серий по стратегии Д'Аламбера, а затем остановиться. Предположим, что вы выиграли первую серию. Так что вам мешает забыть о ней и заново начать играть сто серий? Шарик не имеет памяти, и ваша выигранная серия никак не повлияет на сто последующих. А если вы выиграли и еще одну серию? И еще одну? Получается, что задуманные сто серий начнутся с вашего проигрыша. Нет ли здесь противоречия? Поразмышляйте над этим.Написать комментарий (комментариев - нет) | Послать другу

Данетки-4

Среди всех моих статей в "Досугах" данеточная тема вызвала наибольший поток читательской почты, не прекращающийся до сих пор. Поэтому на всякий случай сообщаю, что предыдущие три статьи находятся на моей Web-страничке и доступны всем желающим. Как это ни удивительно, по-видимому, никаких других публикаций данеток на русском языке не существует. Во всяком случае, мне удалось разыскать только данеточный архив конференции relcom.rec.puzzles (http://kulichki.rambler.ru/puzzles/puzzles/selected/ danet_q.html), к которому я сам когда-то приложил руку…

Впрочем, на английском языке существуют два хорошо известных и довольно распространенных списка задач-данеток - "Classic Lateral Thinking Puzzles" Пола Слоуна (Paul Sloane) и "Situation Puzzles" Джеда Хартмана (Jed Hartman), www.cs.caltech.edu/~adam/PUZZLES/situation.qus, а еще парочка задач есть на странице www.lauras.com/brain.html. Довольно много задач из моей коллекции (если не все!) можно найти в этих списках.

Читатели "Компьютерры" в основном присылали мне те данетки, которые не попали в предыдущие статьи. К сожалению, очень многие из присланных загадок были известны мне так давно, что даже как-то неудобно о них писать. Но, наверное, надо - иначе их будут присылать вновь и вновь.

На всякий случай напоминаю: данетки (другие названия этой игры - "ситуации", "следователь", "детектив") - это коллективное соревнование в разгадывании загадок определенного типа. На мой взгляд, это идеальное развлечение для убивания времени в компании - в походе, в лесу, на пляже. Человек, загадывающий данетку, отличается от остальных членов компании тем, что знает ее ответ. Все прочие должны задавать ему вопросы, выясняя ту ситуацию, которая была загадана. При этом вопросы должны строиться так, чтобы на них можно было ответить "да", "нет" (отсюда и название игры) или "это не имеет значения".

Сейчас я очень сильно подскреб все свои сусеки и закрома, так что новая порция данеток появится очень и очень нескоро. Почти все приведенные здесь загадки, как я уже сказал, не являются новыми, а относятся к классике жанра. Большинство из них имеет ярко выраженный криминальный сюжет: нужно разгадать, как произошло убийство, несчастный случай или что-то аналогичное. По-видимому, все эти сюжеты (при определенных условиях) могли произойти на самом деле.

Загадки

1. Посреди океана стоит комфортабельная яхта, а рядом с нею плавает шесть трупов.
2. Мертвый человек найден у себя дома лежащим в луже из воды и крови.
3. Музыка смолкла, и она умерла.
4. Ветер стих, и человек умер.
5. Врач ехал в подземке и встретил однорукого. Тот выхватил пистолет и выстрелил во врача.
6. Две американки разговаривали. Одна зашла в ванную комнату, а через пять минут вышла и убила другую.
7. Мужчина отправился из Соединенных Штатов в двухнедельный круиз в Мехико. Сразу же после возвращения он поехал в следующий круиз - трехдневный, без захода в какие-либо порты. Во время обоих круизов мужчина все свое время проводил в каюте, ни с кем не общаясь. В результате он стал богаче на 250 тысяч долларов.
8. Двое немецких шпионов в 1944 году пытаются под видом возвращающихся американских туристов въехать в Соединенные Штаты. Один из них проходит пограничный контроль беспрепятственно, а другого арестовывают.
9. Человек умирает в собственном доме от жажды.
10. На тротуаре лежат куски льда и битого стекла, а трое мужчин мертвы.
11. Человек бежал по коридору с куском бумаги в руке. Свет в коридоре начал мигать. Увидев это, человек упал на колени, воздел руки вверх и воскликнул: "О, нет, господи, только не это!"
12. Женщина бросает что-то из окна и умирает.
13. Птицелов увидел птицу, а чуть позже умер.
14. Человек, не имеющий заграничного паспорта, в течение одного дня посещает тридцать разных стран. В каждой из них его встречают и провожают, причем каждую страну он покидает по собственной воле.
15. Человек лежит вблизи большого здания с дыркой в черепе.
16. На потолке спальни несколько свежих пятен человеческой крови.
17. Человек встает ночью, чтобы выпить воды. Затем он выключает свет и ложится спать. Наутро он встает, выглядывает из окна, вскрикивает и кончает жизнь самоубийством.
18. Мужчина пробует новый одеколон, подаренный ему женой ко дню рождения. После этого идет на работу, и его убивают.
19. Американцы, муж и жена, отправились в кино. Во время сеанса муж убил жену, но даже после окончания фильма это не привлекло ничьего внимания, хотя кинотеатр был полон.
20. Мистер Смит был очень доволен, что у его автомашины кончился бензин.
21. Человек сидел между двумя герметичными емкостями и в результате умер.
22. Оскальпированная женщина лежит на улице около автомобиля.
23. Речное судно утонуло из-за змеи.
24. Муж и жена ехали в автомобиле по глухой дороге. Внезапно автомобиль остановился - кончился бензин. Муж вышел из машины и сказал жене: "Я бегом вернусь на ту заправку, которая была 20 километров назад, а ты плотно закрой в машине все двери и окна и никого не пускай". Жена аккуратно выполнила эту инструкцию. Тем не менее, когда через несколько часов муж вернулся, жена была мертва, а рядом с ней в машине находился незнакомый человек.
25. Двое мертвецов сидят в кабине лицом друг к другу.

Разгадки

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

   Другой вариант: лестница была спущена, но доставала до поверхности воды только тогда, когда на яхте были люди. После того как все оказались за бортом, осадка яхты уменьшилась и лестница оказалась вне пределов досягаемости людей.

2. Самоубийца выбрал очень нестандартный способ свести счеты с жизнью: он бил себя по голове большой сосулькой до тех пор, пока не раскроил себе череп вдоль и поперек. После его смерти сосулька растаяла.
3. Она - артистка цирка, канатоходка. Ее коронный номер - ходьба по канату с завязанными глазами. Окончание музыки должно было служить ей сигналом, что путь завершен и можно сделать шаг в сторону. К сожалению, дирижер циркового оркестра (вариант: солист-скрипач) неожиданно заболел, а его сменщика забыли предупредить, поэтому он закончил мелодию раньше, чем артистка дошла до конца каната. В результате она упала с высоты и разбилась.
4. Этот человек был слепым и к тому же оказался единственным спасшимся во время кораблекрушения и попавшим на необитаемый остров. К счастью, на острове была пресная вода. Найдя однажды дорогу к воде, человек укрепил около источника выброшенный на берег корабельный колокол и после этого спокойно гулял по острову, ориентируясь по звукам колокола. Когда наступил полный штиль, ветер перестал раскачивать колокол, человек потерял ориентировку и в итоге умер от жажды.

   У этой загадки есть множество других вариантов, в которых слепой человек определяет свое местоположение по звукам колокола (или звонка), а изменение стандартной ситуации приводит его к смерти. Например, такой вариант: слепой пловец принял по ошибке звук сигнального бакена за звук своего будильника, оставленного им на берегу; вместо берега он поплыл по направлению к бакену - в открытое море.

5. Завязка этой истории была довольно давно. Трое приятелей, попав на необитаемый остров после кораблекрушения, для того чтобы выжить и дождаться спасателей, договорились о следующем: один из них (врач-хирург) будет отрезать им по очереди руки, которые они затем будут вместе съедать. К счастью, их отыскали и спасли после второй отрезанной руки, но приятели договорились, что врач тоже отрежет свою руку, из солидарности с друзьями. Спустя некоторое время один из одноруких приятелей встретил врача в подземке и увидел, что тот держится за поручни обеими руками…

   Другие варианты этой же загадки связаны с подменой руки при пересылке ее по почте (врач должен отрезать свою руку и послать ее друзьям, а вместо этого он посылает чью-то чужую руку). Обман раскрывается, например, по родимому пятну, отсутствующему на присланной руке (или по другим характерным приметам).

6. Дело происходит в доме второй (убитой) женщины. Чернокожий (простите, афро-американский) друг первой женщины был убит куклуксклановцами за несколько дней до описываемых событий. Зайдя в ванную, она случайно обнаружила среди грязного белья хозяйки униформу ку-клукс-клана, запачканную брызгами крови. Там же неподалеку валялся и пистолет…
7. Этим хитрым способом турист ввозит контрабанду из Мексики. Во время первого круиза ему принесли наркотики и кинули под дверь каюты, а он спрятал их в самой каюте внутри кондиционера. В следующем круизе у него была заказана та же самая каюта, а так как заходов в порты нет, то не было и таможенного досмотра. Вынув наркотики из тайника, он сошел на берег.
8. Дело в том, что американцы пишут календарные даты не так, как принято в Европе, а делают это в виде месяц - день - год.

   Заполняя въездные документы, оба шпиона написали даты своего рождения так, как они привыкли это делать, по-европейски. Например, "30 июля 1920 года" было записано как "30/07/20". Но один из двух шпионов родился первого января, и это его спасло.

9. Домом для человека служила яхта, в которой он совершал кругосветное путешествие. Во время плавания по океану пресная вода закончилась гораздо быстрее, чем рассчитывал хозяин.
10. Наверное, эта история известна всем как анекдот.

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

11. Бумага, которую так торопился доставить этот человек, - помилование для преступника, приговоренного к казни на электрическом стуле. Мерцание света означало, что приговор приведен в исполнение.
12. "Что-то" - бумеранг, который возвращается и попадает женщине в висок.
13. Птицелов летел на реактивном пассажирском самолете, а птицу, увиденную им, засосало в один из двигателей. В результате самолет разбился.
14. Он - курьер, разносящий обыкновенную почту (газеты, журналы) по посольствам и дипломатическим представительствам. Как известно, территория посольства считается территорией иностранной державы.
15. Его убила монетка, которую кто-то из туристов кинул вниз с крыши высокого здания - Empire State Building.
16. Хозяин спальни убил на потолке нескольких комаров.
17. Он был смотрителем маяка и ночью по ошибке выключил весь свет на маяке. Из-за этого несколько судов разбились о рифы. Утром он понял, что натворил…
18. Мужчина работает на пасеке, а пчелы всегда узнают человека по запаху и очень не любят новых (неизвестных им ранее) запахов. В итоге он был убит своими собственными пчелами.
19. Это был кинотеатр, в котором зрители смотрят фильмы, не покидая собственных автомобилей.
20. Мистер и миссис Смит сильно поругались, после чего она пошла в гараж, выключила вентиляцию, включила мотор автомобиля и заснула, надеясь на легкую смерть от удушья. Через несколько часов мистер Смит решил попросить у жены прощения и отправился на ее поиски. Если бы бензина в машине оставалось больше, было бы уже поздно.
21. Велосипедист попал в аварию (емкости - велосипедные камеры).
22. Она ехала на мотоцикле без шлема. Когда автомобиль обогнал ее, длинные волосы женщины зацепились за автомобильную антенну. В результате этой аварии волосы были выдраны из головы вместе со скальпом.
23. Змея заползла на пассажирскую прогулочную палубу, и все пассажиры метнулись на другой борт. Судно накренилось, зачерпнуло бортом воду и в итоге пошло ко дну.
24. За то время, пока муж бегал к заправке и обратно, его беременная жена родила ребенка (того самого незнакомца), но, увы, во время родов скончалась.
25. Оба они были пилотами, а их самолеты столкнулись…

Желаю всем хорошего летнего отдыха и многих приятных минут, проведенных за разгадыванием данеток.

Пишите, я постараюсь ответить на все письма.Написать комментарий (комментариев - нет) | Послать другу

Словесный бой

Не так давно меня познакомили со словесной игрой, о которой я никогда раньше не слыхал. Может, она и в самом деле новая, а может, и наоборот - хорошо забытая старая. Ведь появляются же сейчас на прилавках, как грибы после дождя, книжки типа "Игры на досуге", в которых совершенно безо всяких ссылок на копирайты печатают те игры, о которых писала "Наука и жизнь" 20-30 лет назад, а также игры, взятые из книжек классиков занимательной математики - Г. Дьюдени, С. Лойда, Л. Кэрролла, М. Гарднера…

Так или иначе, а игра эта несложная и интересная - то есть вполне достойна того, чтобы о ней рассказать. Что я и делаю.

Участвуют в "словесном бою" не менее двух человек, но лучше всего играть бОльшим составом - скажем, вчетвером или впятером. Каждый участник рисует на клетчатой бумаге квадрат 6x6. Далее все ходят по очереди. Ход состоит в том, что один из игроков называет какую-нибудь букву, после чего все игроки (и он сам в том числе) записывают эту букву в одну из пустых клеток своего квадрата. При этом желательно не показывать свой квадрат остальным игрокам (как в "морском бое"). Суть игры заключается в том, чтобы составить из называемых букв как можно больше слов, которые должны читаться в квадрате по горизонтали и по вертикали.

Пропускать ход нельзя, то есть каждая названная буква должна быть записана всеми игроками. Всего в игре делается не более 36 ходов, после чего игроки производят подсчет своих результатов. В игре должно быть сделано полное число кругов, поэтому общее число ходов должно делиться на число игроков. Например, если играют пять человек, то можно делать 25, 30 или 35 ходов (в любом случае, о продолжительности игры нужно договориться перед первым ходом).

Результаты подсчитывают так: каждое слово из N букв приносит игроку N-1 очко (иначе говоря, однобуквенные слова не считаются). Слова должны читаться либо по горизонтали (слева направо), либо по вертикали (сверху вниз). Слова, идущие в одном направлении, не должны пересекаться или содержаться одно в другом. Все слова должны быть именами существительными в единственном числе. Обычно, как и в других подобных играх, допускаются только нарицательные существительные. Но при общем согласии игроков можно употреблять и имена собственные - названия городов, книг, имена литературных героев и т. п.

Пример заполненного квадрата:

Б О Й К О Т

А Л Е Р Х С

К О П Е Р А

Ж В Е С А Д

П О Ч Т А Ф

Ы Я Ь Ь С Ю

Подсчет очков в этом примере: вертикаль - бак (2), олово (4), печь (3), охра (3), ас (1), сад (2); горизонталь - бойкот (5, а если рассматривать слоги "бой" и "кот" как два отдельных слова, то они принесли бы всего 4 очка!), опера (4), вес (2), ад (1), почта (4). Итого - 31 очко (15+16). Это неплохой результат, хотя и не предел.

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

Вариация 1 (упрощение): игра ведется не на фиксированном квадрате из 36 полей, а на всей клетчатой плоскости. При этом в идеале получается нечто вроде правильного кроссворда: каждому из игроков выгодно, чтобы записанные им буквы попадали не в одно слово, а сразу в несколько. Такой вариант игры приближает ее к классическому "скрэбблу" (известному у нас в стране также под именами "эрудит" и "крестословица").

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

Вариация 3 (изменение системы подсчета): разрешается читать слова не только сверху вниз и слева направо, но и наоборот, а также вдоль всех диагоналей (и тоже туда и обратно). Иначе говоря, слова могут читаться по восьми различным направлениям, и каждое из них приносит зачетные очки. В приведенном выше примере использование этой вариации добавит как минимум слово "вол", читаемое снизу вверх, а также слова "ток", "фат" и "сев" справа налево.

А теперь - задачки для тех поклонников игр, которые любят не только играть сами, но и программировать.

Задача 1

Представьте, что в вашем распоряжении есть файл-словарь. Напишите программу, которая умеет подсчитывать очки в уже сыгранной партии - в заполненном квадратике 6x6.

Задача 2

Теоретически в "словесный бой" можно играть и в одиночку - для этого всего лишь нужно, чтобы кто-то (например, компьютер) выдавал случайным образом очередную букву. Конечно, лучше, если при этом будет учитываться частота появления этой буквы в русских словах.

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

Задача 3

Самые интересные новые игры обычно получаются в результате скрещивания двух старых. Попробуйте скрестить "словесный бой" и "Color Lines": каждое новое слово приносит очки, после чего все составляющие его буквы исчезают и освобождают место. При этом новые буквы появляются на клетках игрового поля не по одной, а парами или даже по три сразу, после чего одна из букв может быть переставлена в другое место точно так же, как переносятся шарики в "Color Lines".

Такая игра может идти довольно долго, а заканчивается при заполнении всего поля. В результате умелый игрок может набрать очень много очков.

А теперь - самое трудное задание.

Задача 4

Напишите программу, которая играла бы в "словесный бой" по описанным выше каноническим правилам. Опять-таки, для этого нужен какой-нибудь словарь - считайте, что он у вас есть.

Можете попробовать реализовать два разных варианта игры:

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

б) все ходы берутся из текстового файла (естественно, от программы и здесь тоже требуется "честность").

Я давно хочу устроить среди читателей своеобразный чемпионат, в котором приняли бы участие написанные ими программы. Пока что дело обстоит в точности так же, как в бородатом анекдоте о Рабиновиче: он второй раз хотел поехать в Париж. До этого он никогда не был в Париже, но один раз уже хотел… Может быть, что-то изменится, если объявить, что автор лучшей программы получит бесплатную подписку на "Компьютерру"? Надо будет обсудить такую возможность с Георгием Кузнецовым…

Пишите, я постараюсь ответить на все письма.Написать комментарий (комментариев - нет) | Послать другу

Вдоль или поперек?

Генри Форд считал, что дилетанты сделали столь много в науке и вокруг нее просто потому, что они не знали, что этого сделать нельзя. Моя нынешняя цель гораздо скромнее - рассказать другим о том, в чем я плохо разбираюсь сам. Я чувствую себя даже не дилетантом, а самым что ни на есть профаном в той области, о которой взялся писать. Но так как никаких открытий не предвидится, то попробовать можно. Итак, о чем это я? О параллельных вычислениях.

Представьте себе простейшую вычислительную задачу - найти сумму нескольких чисел. Если в вашем распоряжении один компьютер, то все просто и понятно: "длина" вычисления прямо пропорциональна количеству складываемых чисел. А если компьютеров несколько? Для определенности будем считать, что у вас P компьютеров (то есть "ширина вычислений" равна P), обмен данными между ними занимает пренебрежимо малое время, а количество слагаемых равно 1000. Предположим, что каждое элементарное сложение занимает 1 единицу времени (такт). Мы будем интересоваться алгоритмом решения задачи за наименьшее число тактов на P компьютерах - это количество обозначим T_P. Очевидно, что T₁=1000: в каком порядке ни складывай исходные числа, между ними стоит 999 знаков "+", поэтому для получения результата требуется ровно 999 сложений.

Случай P=2

Второй компьютер позволяет сократить время вычисления почти вдвое. Это достигается, например так: пока первый компьютер находит сумму первых 500 чисел, второй в это же время суммирует остальные 500 чисел. После 499 тактов останется выполнить только одно действие - сложить две накопленных суммы S₁ и S₂ и получить общую сумму S=S₁+S₂. Это сложение выполняется на любом из двух компьютеров, а вторая машина в это время "отдыхает". Итак, T₂=500.

Случай P=4

Разделим весь процесс на четыре равные части. Через 249 тактов компьютеры получат суммы S₁, S₂, S₃ и S₄. За следующий такт можно найти одновременно S₁+S₂ и S₃+S₄, ну, и затем уже вычислить S₁+S₂+S₃+S₄. Итого T₄=251, но при этом в последнем такте работает только один из четырех компьютеров.

Случай P=500

Представим на секундочку, что у нас есть именно такое число компьютеров. Тогда мы можем одновременно выполнить все 500 попарных сложений, на втором шаге получить 250 сумм по 4, и т. д. Чем ближе к концу, тем меньшее число компьютеров будет загружено. На десятом шаге делается последнее сложение (T₅₀₀=10), а остальные 499 компьютеров в этот момент простаивают…

Я описал эти вычисления так подробно только потому, что из них становится понятна принципиальная особенность распараллеливания: чем "шире" идет процесс вычислений, тем он становится короче, но одновременно возрастает доля "холостого хода". В любом случае, PхT_PіT₁, и равенство достигается только в том случае, если в каждом такте вычислений задействованы все имеющиеся компьютеры. При этом рассмотренная мною задача не является чем-то исключительным, - наоборот, почти так же обстоит дело и при построении параллельных алгоритмов для решения самых разных задач.

Одним из важнейших показателей эффективности параллельного алгоритма считается "ценность" f_P=T₁/(PхT_P²) - чем она выше, тем лучше. В приведенных примерах f₁=999/999²=0,00100, f₂=0,00199, f₄=0,00396, f₅₀₀=999/(500*10²)=0,01998. Является ли 0,01998 максимально возможной ценностью? Оказывается, нет - но это уже сюжет для небольших задачек, которые я и предлагаю читателям.

Задача 1

Решите задачу суммирования для P=100 компьютеров за 16 тактов. А потом - для P=175 компьютеров за 12 тактов. ("Ценность" второго решения f₁₇₅ примерно равна 0,03964)

Задача 2

Попробуйте ответить на "обратные" вопросы: какое наименьшее число компьютеров позволяет решить задачу за 13 тактов? за 14 тактов? за 15 тактов? Можно ли решить задачу за 16 тактов, если число компьютеров меньше 100?

Задача 3

Найдите количество компьютеров, для которого "ценность" параллельного алгоритма суммирования будет наибольшей.

Перейдем теперь к другим задачам на ту же тему.

Задача 4

Проследите, как изменятся решения всех предыдущих задач (и ответы к ним), если количество суммируемых чисел увеличить в 10 раз.

Понятно, что оптимальное (в смысле ценности) число компьютеров меняется в зависимости от "объема" конкретной задачи. Но надо хорошо понимать, что наша задача - лишь модель, а в реальности при увеличении числа компьютеров сильно растет доля времени, которое непродуктивно тратится на передачу данных между компьютерами.

Задача 5

Решите заново все предыдущие задачи, считая теперь, что передача числа от одного компьютера к другому тоже занимает один такт (при этом числа могут передаваться параллельно).

Задача 6

Придумайте, как распараллелить вычисление значения многочлена:

P(x) = a₀ + a₁ x + a₂ x² +…+ a_n xⁿ.

Задача 7

Представьте, что ваш знакомый задумал число, не превышающее одного миллиона, а вам надо его угадать, задавая вопросы, на которые знакомый может отвечать "да" или "нет". Классический метод деления пополам - дихотомии - гарантирует успех за 20 попыток (2²⁰>1000000). А теперь попробуйте придумать экономный "параллельный" алгоритм: задуманное число знают P=4 разных человека, а вы можете за одну "попытку" задать каждому из них свой вопрос и получить ответ на него. Сколько попыток при этом вам хватит для отгадывания задуманного числа? А если P=5? А при P=10?

Можете присылать мне решения понравившихся задач, я постараюсь ответить на все письма читателей.Написать комментарий (комментариев - нет) | Послать другу

Все врут календари?

Уже не в первый раз за свою историю человечество на грани тысячелетий испытывает мистический страх, ожидая катаклизмов и прочих неприятностей. Так, в конце X века нашей эры Западная Европа, уже перешедшая на счет лет "от рождества Христова", ожидала конца света и страшного суда. Наши православные предки, остававшиеся при календаре "от сотворения мира" вплоть до реформ Петра Великого, подобный страх пережили в конце XV века - 1492 год был 7000-м… Только после 1 сентября 7001 года, как пишет Карамзин в "Истории Государства Российского", "суеверные успокоились, увидели, что земля стоит и небесный свод не колеблется с исходом седьмой тысячи…".

Вот и сейчас, накануне вступления в третье тысячелетие, различные аспекты календаря и его истории снова пользуются повышенным интересом общества. И дело здесь не только в компьютерной проблеме 2000 года, но и в том, что многие из нас совершенно не знают устройства того календаря, по которому мы живем.

Я уже писал об этом прошлой осенью - в статье "Мифы и размышления". Но, увы, мифов с тех пор меньше не стало. Поэтому я решил вернуться к календарной теме и рассказать о ней подробнее. Почти вся информация, использованная в статье, взята из книг А. Паннекука "История астрономии" и И. А. Климишина "Календарь и хронология".

Юлий Цезарь и Дионисий Малый

Наш календарь ведет свою историю из Древнего Египта. Именно там Гай Юлий Цезарь познакомился с солнечным календарем, после чего твердо решил провести в Риме календарную реформу. В основе предложенной им системы лежит солнечный год, длительность которого принята равной 365,25 суток. А так как в календарном году бывает только целое число суток, то предписывалось считать в трех из каждых четырех годов по 365 дней, а в четвертом - 366. Эта же реформа Цезаря упорядочивала число дней в месяцах: во всех нечетных месяцах должен был быть 31 день, а в четных (кроме февраля невисокосного года) - 30. В невисокосном феврале было 29 дней.

Счет дней по юлианскому календарю начался с 1 января 45 года до н. э., а сам Цезарь пережил свое детище всего на год с небольшим. В ознаменование его заслуг месяц Квинтилис был переименован в Юлиус - нынешний июль. А дальше началось самое интересное. По непонятной причине високосные годы первое время устраивались не каждые четыре, а каждые три года! К 9 году до н. э. прошло 12 високосных лет вместо девяти положенных. Эту ошибку заметил и повелел исправить римский император Август. В знак признания его больших военных заслуг, а также в благодарность за исправление римский сенат переименовал месяц Секстилис в Августус. Одновременно при этом месяц Августус был удлинен на один день (за счет все того же февраля), а чтобы три длинных месяца не шли подряд, сентябрь (то бишь Септембер) и ноябрь (Новембер) были сделаны короткими, а Октобер (октябрь) и Децембер (декабрь) - длинными. (Меня часто интересовало, почему большевики в 1918 году, следуя примеру Французской республики, не переименовали все месяцы календаря как-нибудь по-пролетарски? Возможно, тогда мы с вами стали бы свидетелями переименований месяцев в честь юбилеев партийных вождей.)

Так или иначе, но от Цезаря до введения современного летосчисления прошло еще почти шесть сотен лет. Первым, кто решил отказаться от счета лет, связанного с римскими императорами ("эры Диоклетиана") и перейти к отсчету "от рождества Христова", был монах Дионисий Малый. При этом он никак не обосновал тот факт, что начало своей эры он отнес именно на то, а не на другое место в хронологии. Наиболее разумное предположение, объясняющее это, таково: Дионисий считал, что Иисус Христос воскрес 25 марта, на 31-м году жизни. Расчеты пасхалий, проделанные Дионисием, показали, что год, в котором Пасха приходится на 25 марта, - 279-й год эры Диоклетиана. Зная, что даты Пасхи повторяются каждые 532 года, и прибавив к 532-м еще предполагаемый возраст Христа, Дионисий Малый и "привязал" начало эры от рождества Христова, просто приравняв 279 год эры Диоклетиана 563-му году "от Р. Х.". (Кстати, Дионисий начинал счет дней в году с "магической даты" 25 марта, так что датой рождения Христа он считал 25 декабря 1 года введенной им эры.)

С хронологией Дионисия согласились далеко не все и далеко не сразу. Время от времени делались попытки уточнить дату рождения Христа, пользуясь астрономическими данными, разбросанными в различных местах Нового Завета. Можно с уверенностью сказать, что хронология "от рождества Христова" победила только потому, что вместе с нею Дионисий предложил очень удобную и простую систему расчета дат Пасхи, в то время как ранее составление пасхальных таблиц было очень трудным делом. Впрочем, об этом пойдет речь ниже.

Папа Григорий XIII

К сожалению, простота юлианского календаря неизбежно становилась и причиной его недостатков. Главным среди них было несоответствие продолжительности "истинного" года и календарного. Дело в том, что тропический год - время обращения Земли вокруг Солнца - длится не 365,25 суток, а чуть меньше, примерно 365,2422. Следовательно, юлианский календарь каждый год накапливает ошибку примерно в 0,0078 суток, а ошибка в целые сутки набегает за 128 лет.

За 16 веков, прошедших с введения юлианского календаря до 1582 года, точка весеннего равноденствия "убежала" с 21 марта на 11 марта. Поэтому папа Григорий XIII в феврале 1582 года издал специальную буллу о календарной реформе. Эта булла предписывала изъять из календаря 1582 года все дни от 5 октября до 14 октября включительно, а впредь исправить календарную систему так, чтобы из каждых 400 лет было не 100 високосных, а всего 97. Этот календарь получил название григорианского и сохранился по сей день.

В соответствии с волей папы Григория годы 1700-й, 1800-й и 1900-й были невисокосными и состояли из 365 дней. Ближайший "круглый" год - 2000-й - снова будет високосным, а за ним снова последуют три невисокосных - 2100-й, 2200-й и 2300-й.

Надо сказать, что и такой календарь небезупречен: ведь 97/400 тоже не равны дробной части тропического солнечного года. Но, в отличие от прежнего календаря, ошибка в сутки теперь накапливается не за 128, а за 3250 лет. Иными словами, на наш век точности этого календаря вполне хватит.

Кроме того, сама продолжительность года тоже немного меняется. Ныне принято считать, что вращение Земли вокруг своей оси постепенно замедляется, а продолжительность суток - увеличивается. Соответственно уменьшается число суток, укладывающихся в одном году. Этот эффект задается приближенной формулой Саймона Ньюкома:

1 год = 365,24219879 - 0,0000000614*(# года - 1900). В частности, григорианский календарь был бы совсем точным примерно 5000 лет назад, а с каждым годом его погрешность чуть-чуть растет…

Карл Фридрих Гаусс

"Король математиков" XIX века внес огромный вклад не только в чистую математику, но и в огромное число приложений, от геодезии и картографии и до азартных игр. В частности, он предложил формулы для непосредственного определения датировок весеннего равноденствия и христианской Пасхи. Я приведу алгоритм расчета православной Пасхи, основанный на формулах Гаусса, as is - безо всяких объяснений и обоснований.

Номер года нужно разделить на 19, 4 и 7 и получить при этом остатки от деления (а, b и c соответственно). Далее, d = (19a + 15) mod 30 (остаток от деления 19a + 15 на 30), а e = (2b + 4c + 6d + 6) mod 7.

Пасха будет либо в марте, либо в апреле (все даты получаются по старому, то есть юлианскому, стилю!) в зависимости от величины d + e. Если d + e не больше 9, то дата Пасхи - 22 + d + e марта, в противном случае Пасха приходится на d + e - 9 апреля. Формулы предусматривают два исключения:

Пасха с 26 апреля всегда должна быть перенесена на 19 апреля, а при d = 28 и e = 6 - с 25 апреля на 18 апреля. Таким образом, Пасха всегда происходит между 22 марта и 25 апреля.

Пишите письма, заходите на WWW-страничку.Написать комментарий (комментариев - нет) | Послать другу

Ним-игры

Игра "Ним" известна, наверное, всякому, кто читал книги Мартина Гарднера. Но я уверен, что смысл "магического ним-правила" понимают далеко не все. А впрочем, многие ведь и Гарднера не читали или успели крепко подзабыть, так что я начну с самого начала.

Представьте, что перед вами и вашим партнером по игре на столе лежит несколько кучек камешков. Правила игры разрешают забрать за один ход любое количество камешков - но только из одной кучки. Выигрывает тот из двух игроков, кто забирает со стола последний камешек.

Для нима существует стратегия, которая сводится к применению уже упомянутого выше "магического правила". Давайте разберем это правило и всю стратегию на примере.

Пусть изначально есть три кучки (A, B и C) в которых находится соответственно 5, 9 и 11 камешков. "Правило" предписывает сделать следующее:

1. Представить каждое из чисел в двоичной системе: 5=4+1, 9=8+1, 11=8+2+1.
2. Вычеркнуть все встретившиеся пары равных слагаемых, в данном случае - пару восьмерок и пару единиц.
3. Сложить оставшиеся степени двойки (4+2+1=7). В результате получается так называемая ним-сумма для данной позиции. Если ним-сумма равна нулю, то такая позиция называется "безопасной", а если отлична от нуля - то "опасной".
4. Если позиция опасна, то нужно сделать ход, переводящий ее в безопасную позицию. Если исходная позиция безопасна - то право первого хода надо уступить сопернику.

Ход игры, когда один из партнеров применяет это правило, сводится к тому, что игроки по очереди получают опасные и безопасные позиции. Так как конечная позиция (0 камешков во всех кучках) имеет нулевую ним-сумму, то она безопасна, а значит, в нее сделаете ход именно вы, а не ваш партнер.

Согласитесь, в этом правиле есть какая-то магия и даже числовая мистика! Откуда берутся степени двойки? Почему есть уверенность, что из любой опасной позиции есть ход в безопасную, а для безопасных позиций такого хода нет?

Сначала разберемся с ходом. Как следует из правила, ход должен быть сделан так, чтобы в результате каждая степень двойки входила в оставшиеся кучки четное число раз (в данном случае - либо дважды, либо вообще ни разу). В приведенном выше примере в ним-сумму не входила восьмерка, поэтому после хода в кучках B и C должно остаться не менее 8 камешков. Это означает, что если забирать камешки из этих кучек, то возможны всего четыре хода:

• оставить в кучке B 8 камешков (взять 1)
• оставить в кучке C 8 камешков (взять 3)
• оставить в кучке C 9 камешков (взять 2)
• оставить в кучке C 10 камешков (взять 1)

Но все такие ходы оставляют в ним-сумме четверку, а поэтому получающиеся позиции не будут безопасными. Следовательно, надо делать ход, забирая какие-то камешки из кучки A. Легко заметить, что, оставив в ней 2 камешка (то есть забрав три), мы получим безопасную позицию: A=2, B=8+1, C=8+2+1.

Совершенно аналогичным образом нужный ход можно найти и в общем случае. Для этого нужно вычислить двоичные дополнения каждого количества камешков до их ним-суммы (для знатоков программирования это - то же самое, что результат побитовой логической операции XOR: для каждого двоичного разряда 0 XOR 0 и 1 XOR 1 равны 0, а 0 XOR 1 равен 1. Хотя бы для одной кучки такое дополнение будет меньше, чем исходное число камешков в этой кучке. Ход делается именно в этой кучке. Для нашего примера 11 XOR 7 = 12, 9 XOR 7 = 14 и 5 XOR 7 = 2. Так как 12>11 и 14>11, то единственный возможный ход - это оставить два камешка в кучке A, что мы и сделали. Заметим, что и сама ним-сумма - это результат той же операции XOR: 7 = 5 XOR 9 XOR 11.

Пришло самое время дать некоторую пищу для мозгов.

Задача 1

Почему результат операции XOR с несколькими числами не зависит от порядка, в котором выполняются операции?

Задача 2

Почему хотя бы для одного из количеств камешков в кучках двоичное дополнение до ним-суммы будет меньше, чем само это количество? Выполняется ли то же свойство для четырех (или другого четного числа) кучек?

А теперь попробуем посмотреть на другую игру.

В игре "удаление цифр" (о которой я писал год назад в статье "Пять игр Джона Конуэя", "Компьютерра" #198) вначале выписывается какое-нибудь большое число, например 314159. Каждым ходом игрок может либо уменьшить какую-либо цифру (не равную нулю), либо стереть любой нуль и вместе с ним все цифры, стоящие правее его. Например, первый игрок мог уменьшить своим ходом четверку до нуля, а второй - стереть этот нуль и вместе с ним весь кусок 0159, то есть оставить только 31. Игра продолжается до тех пор, пока с доски не стерты все цифры, а игрок, вынужденный стереть последнюю цифру, проигрывает.

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

Для начала назначим числу 0 ним-сумму, равную нулю, числу 1 - сумму 1 и так далее до девятки. Первый нетривиальный случай - число 10. Из него можно получить либо 1 (стерев 0), либо 0 (уменьшив 1 до нуля). Но это значит, что 10 ничем не отличается от числа 2! Поэтому я сопоставлю десятке ним-сумму, равную 2, и двинемся дальше.

До сих пор все числа были "опасными" - из них можно было получить 0 первым же ходом. Число 11 - первое безопасное число: из него можно получить либо 1, либо 10, но 0 получить уже нельзя. Следовательно, его ним-суммой будет 0. Из 12 можно получить либо 02, либо 10, либо 11. Так как ним-суммы этих чисел равны 2 и 0, а единица среди них не встречается, то ним-сумму для числа 12 положим равной 1. И точно так же будем идти дальше, пользуясь еще одним "магическим правилом": значением ним-суммы для числа N делаем наименьшее из чисел, не встречающихся среди тех ним-сумм, которые можно получить из числа N по правилам игры "удаление цифр".

Задача 3

Как вы думаете, почему для этой хитроумной операции я использую термин "ним-сумма", который в обыкновенном ниме определялся совершенно иначе?

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

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

Задача 4

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

Пишите письма, заходите на WWW-страничку.Написать комментарий (комментариев - нет) | Послать другу

Около шахмат

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

Одна из тем, которые я всегда старался максимально подробно разжевать своим бывшим ученикам, - переборные алгоритмы. Обычно я их иллюстрировал разнообразными околошахматными задачами. Когда-то для такого "перекоса" в изучении этой темы были самые серьезные мотивы: если плохо написать перебор, то самая пустяковая программа работала бы несколько часов. Сейчас персоналки стали гораздо шустрее, да и многозадачность сильно выручает, так что мои любимые задания перешли в разряд любительских упражнений. Иными словами - в материалы для рубрики "Досуги".

Сюжет 1

Сколькими способами можно расставить 8 ферзей на шахматной доске так, чтобы они не били друг друга?

Легенда приписывает формулировку и решение этой задачи "королю математиков" Гауссу. Именно он первым перебрал все способы - их оказалось 92. Любопытно, что и сейчас авторы учебников очень любят демонстрировать метод бектрекинга (перебора с возвратом) именно на этой задаче. Так что желающим предлагается попробовать свои силы. Это не так сложно, как кажется.

Но есть и продолжение сюжета: а сколько существует способов, принципиально отличающихся друг от друга, то есть не переходящих один в другой при поворотах и отражениях? Я не сомневаюсь, что каждый из вас смог бы ответить на этот вопрос, внимательно изучив 92 картинки-решения. А не слабо научить это делать программу? Можете считать, что "картинки" у вас уже есть.

Не очень сложно доказать, что если N не делится ни на 2, ни на 3, то задача о расстановке ферзей для доски NxN всегда имеет хотя бы одно решение. Поэтому естественным обобщением сюжета будет найти число решений для досок с произвольным N>4.

Наконец, вот еще малоисследованный вариант той же задачи: сколько ферзей можно поместить на кубическую доску NxNxN так, чтобы они не били друг друга? Будем считать, что ферзи в пространстве бьют не только по вертикалям и диагоналям в каждой плоскости, но и вдоль диагоналей куба.

Сюжет 2

Какое наименьшее число ферзей можно расставить на шахматной доске так, чтобы они держали под контролем все поля доски?

Эта задача (известная под названием "задача о доминировании ферзей") тоже хорошо известна, и ответ в ней - 5. Вариантов расположения существует довольно много, а вот сколько именно? А если опять-таки рассматривать варианты с точностью до поворотов и симметрий? А для произвольного размера доски? Например, для доски 11x11 тоже хватает пяти ферзей, а для доски 35x35 хватает 19 ферзей. (А вот хватит ли восемнадцати - вроде бы неизвестно). А как обстоит дело для трехмерных досок?

Вместо ферзя можно брать и другие фигуры (слона, коня, ладью, короля). Для каждой из них можно посчитать "число независимости" и "число доминирования", а также количество решений в каждом случае. Иногда этот результат можно получить чисто теоретически, без перебора, иногда перебор все-таки необходим. Более-менее полная сводка результатов приведена в книге Евгения Гика "Математика на шахматной доске", а также в некоторых других книгах и статьях того же автора.

Сюжет 3

Как обойти конем шахматную доску, не побывав ни на каком поле дважды и вернувшись в исходную клетку?

Совершенно заслуженно выражение "ход конем" означает в русском языке очень хитроумный и нетривиальный замысел. Вот и задача обхода доски является довольно крепким орешком, на котором обламывают зубы даже некоторые профессионалы. Нет, конечно, найти какой-то один обход не так сложно. Например, легко можно нарисовать на бумаге маршрут обхода конем доски 4x4, а потом разорвать 4 этих маршрута вблизи центра доски и склеить из них один маршрут. Есть и другой известный способ: сначала обойти "кайму" доски шириной в две клетки, а потом - центральные 16 клеток.

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

Вот как раз в этой задаче полный перебор всех вариантов недоступен даже для нынешних компьютеров, так что приходится искать иные пути. Собственно, хорошие идеи давно известны. Например, известно такое правило: конь всегда должен перескакивать на клетку, для которой количество возможных ходов с нее является наименьшим. А если таких клеток несколько? Однозначного рецепта, как видите, нет…

Сюжет 4

Шахматный король путешествует из одного угла доски MxN в противоположный. При этом он может пройти не по всем клеткам, но ни на какую клетку не должен становиться дважды.

Это еще одна известнейшая задача об обходе доски. Число решений (не самопересекающихся королевских маршрутов) очень быстро растет с ростом размеров доски. Например, на доске 3x3 их всего 12, для доски 4x4 их уже 184, а для 4x8 - 163496. Попробуйте написать программу, которая решала бы задачу о нахождении а) всех таких маршрутов; б) только их количества.

Сюжет 5

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

Попробуйте поиграть в такую игру, для начала можно взять даже не все восемь пешек, а всего по четыре или даже по три с каждой стороны. Если эта игра вам понравится и не покажется сильно простой, попробуйте написать программу, которая будет играть (грамотно играть, а не просто двигать пешки!) за одну из сторон. Когда напишете - присылайте мне, и мы попробуем устроить турнир таких программ.

Пишите письма, заходите на WWW-страничку.Написать комментарий (комментариев - нет) | Послать другу

Тьюрмиты

Совмещать приятное с полезным, хоть и не всегда, но порой удается. Например, совсем недавно я совместил подготовку статьи в "Досуги" с участием в замечательном конкурсе тьюрмитных рисунков. Что из этого вышло - судить не мне.

"Тьюрмит - это существо, вылезшее из разбитой машины Тьюринга, после того как Грегори Тэрк уронил ее со своего стола. С тех пор тьюрмиты распространились довольно широко, однако по-прежнему остаются мало исследованными созданиями. Живут тьюрмиты на бесконечной плоскости, разделенной на квадратные клетки. Чем они питаются, неизвестно. Живой тьюрмит постоянно движется по плоскости, он не может оставаться в покое".

Это вовсе не цитата из фантастического романа, а отрывок из учебного пособия по занимательной тьюрмитологии. Само это пособие, а также все остальные материалы, относящиеся к уже упомянутому конкурсу рисунков, помещены на сервере Университета города Переславля (http://up.botik.ru/~inform/thurmits/index.html). Автор текста (а также главный организатор конкурса) - программист и преподаватель этого университета Евгений Лилитко (crgames@ks.botik.ru). К слову, увлечение подобными вещами у Евгения очень давнее: еще десять лет тому назад он написал программу, которая стала чемпионом мира по "Бою в памяти". (Для тех, кто никогда не слышал о "Бое в памяти", могу сказать только, что это борьба двух программ-вирусов на ограниченном участке машинной памяти по заранее оговоренным правилам. Игра эта очень интересна и требует более подробного рассказа. Возможно, когда-нибудь в другой раз…)

Я возвращаюсь к тьюрмитам. Если попытаться кратко изложить суть, то она сводится вот к чему: тьюрмит всегда работает по программе, заложенной в его "мозг". Входной язык этой программы - не процедурный (как C++), а скорее декларативный (как, например, Пролог). В каждый момент времени выполняется одна из строк программы, а какая именно - зависит от "ситуации". Точнее - от цвета клетки, в которой тьюрмит находится, и от той строки, которая выполнялась перед этим. Результатом выполнения этой строки будет следующее:

1. тьюрмит покрасит ту клетку, на которой он стоит, в некоторый (заданный в этой строке) цвет;
2. затем он либо сдвинется прямо относительно своего текущего направления движения, либо свернет налево, либо повернет направо;
3. тьюрмит узнает, какую строку программы он должен выполнить следующей.

Если такой строки в тексте не обнаружится, тьюрмит "умирает".

Пока такие строки находятся, тьюрмит живет вечно - а точнее, до тех пор, когда хозяин компьютера не прервет выполнение программы.

На экране при этом появляются замысловатые рисунки, красота и сложность которых зависят только от фантазии (и умения программировать!) автора тьюрмитной программы.

Кстати, синтаксис всех строк таких программ очень прост:

буква; текущий цвет; новый цвет; код поворота; новая буква.

Под буквой здесь понимается любая буква, а также цифра или другой символ, цвета кодируются числами от 0 до 15, а поворотов бывает всего три: -1="налево", 0="прямо", 1="направо".

Например, строка

A 0 15 1 A

означает, что после попадания на черное (цвет 0) поле в строке, обозначенной буквой A, тьюрмит перекрасит его в белый цвет (15), повернет направо и будет искать следующую строку для выполнения. Эта строка должна начинаться буквой A, а следом за этой буквой должен стоять цвет клетки, на которую тьюрмит попал.

Отмечу, что начальный цвет всего поля - черный, а тьюрмит при рождении находится "в состоянии A". Таким образом, первой будет выполнена та строка программы, которая начинается с "A 0".

Задача 1

Определите, что будет нарисовано тьюрмитом, если вся его программа состоит из одной приведенной выше строки - "A 0 15 1 A". А если эта программа будет иметь вид "A 0 15 0 A"?

Задача 2

А теперь разберитесь в чуть более сложной программе:

A 0 2 0 B

B 0 2 0 C

C 0 2 1 A

Задача 3

И, наконец, последнее упражнение на освоение тьюрмитной азбуки: определите, что будет рисовать тьюрмит с программой

A 0 15 1 A

A 15 15 0 A

Ответы к задачам

1. Тьюрмит обойдет и закрасит белым цветом четыре соседние клетки, стоящие в вершинах квадрата. После этого он попадет на исходную клетку и умрет: ведь у него в программе нет строки для действий в ситуации "A 15".

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

2. Будет нарисован зеленый (цвет 2) квадрат со стороной 3.

3. Тьюрмит станет рисовать белую линию (точнее, двойную линию), которая будет постепенно удлиняться - по очереди то в одну, то в другую сторону.

Ну, а теперь пару слов о конкурсе. Участником его (а также членом жюри) мог стать любой житель Сети. Достаточно было зайти на соответствующую страничку, зарегистрироваться (совершенно бесплатно), скачать программу-тьюрмитник, после чего можно было садиться и писать своих тьюрмитов.

Я так и сделал.

Одной из первых моих удач была красивая "вертушка":

Ее программа совсем простая и довольно короткая:

A 0 2 0 C

A 2 0 0 B

B 2 2 1 A

B 15 2 1 A

C 2 0 -1 A

C 0 15 -1 A

C 15 2 -1 A

Хотя, конечно, эта простота обманчива - тьюрмит, рисуя вертушку, бегает по очень хитрой траектории, периодически возвращаясь от ее краев к центру, а затем убегая обратно.

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

Из простых программок, полученных, скорее всего, именно таким путем, я приведу здесь только одну. Автор назвал ее "желтый дом".

A 0 14 0 B

A 14 13 -1 A

A 13 0 1 B

B 0 13 1 A

B 13 14 -1 A

B 14 0 0 A

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

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

По-видимому (я сужу по использованию тех же 13-го и 14-го цветов), ее и "желтый дом" делал один и тот же автор. А программка и здесь очень проста:

A 0 14 0 B

B 0 14 0 C

C 0 14 0 E

E 0 14 0 F

F 0 14 0 J

J 0 13 -1 A

A 14 13 0 A

A 13 14 0 A

J 14 13 0 A

J 13 14 1 A

Для тех, кто еще не совсем разобрался: первые шесть строк рисуют квадратик, а дальше… остается всего четыре строки, и вот они-то и определяют весь остальной рисунок!

Но все эти рисуночки - просто детские забавы по сравнению с той гигантской работой, которую проделал Дмитрий Папичев. Дима просто взял и написал игру "Жизнь", о которой я недавно рассказывал (см. "Компьютерру" #243). "Жизнь" на одном-единственном тьюрмите! Я не поверил своим глазам и не верю до сих пор, но вот оно - работает, смотрите:    

Здесь в качестве начальной конфигурации выбрано "планерное ружье" (см. первый из трех рисунков). Из него каждые 30 тактов вправо и вверх вылетает планер. Долетает до границы поля и там исчезает, потому что граница поля жестко задана рамкой, внутри которой все и происходит. Весь рисунок - ружье, планер, смена поколений - рисуется одним крошечным тьюрмитом, который обегает все поле внутри рамки. На втором рисунке показано состояние ружья после пары тактов жизни (это десятки тысяч команд тьюрмита, но на экране все происходит очень быстро). А на третьем - то же ружье, уже почти готовое выстрелить (еще примерно через 20 тактов "жизни").

Чтобы рисунки были хорошо видны, мне пришлось увеличивать их в восемь раз по сравнению с остальными, так что не удивляйтесь, что все точки оказались такими крупными.

Программу для "Жизни" и, в частности, для планерного ружья я уже никак не смог бы привести здесь: она занимает около 400 строк.

Кстати, это тоже превосходный результат. Попробуйте-ка уместить программу для этой игры, написанную на любом из процедурных языков, кроме ассемблера, в 400 строк и в 5 килобайт!

Ну и напоследок еще одна задача для тех, кто заинтересовался.

Задача 4

Разберитесь, что получается на экране во время работы вот такой тьюрмитной программы:

A 0 15 1 B

A 15 1 0 B

A 1 15 1 B

B 0 0 0 A

B 15 15 0 A

B 1 1 0 A

Пишите и заходите в гости на мою страничку.Написать комментарий (комментариев - нет) | Послать другу

Конкурс "Программист месяца": сезон гастролей открыт!

Тем, кто познал изящность и красоту программистских головоломок, "научив" компьютер решать хоть одну хитрую задачу, можно позавидовать - немногим дано испытать то состояние, близкое к нирване, которое охватывает творца программы в момент, когда его детище благополучно проходит каверзные тесты. Но гораздо логичнее было бы пожалеть этих людей. Ибо миг торжества недолог - и творческий зуд опять толкает на поиски новых задач. Воистину нет покоя вставшему на эту стезю. Пока одни ищут задачи на книжных полках и в глубинах Сети, другие в то же самое время выставляют их на своих страницах и проводят самые разнообразные конкурсы. И как приятно порой бывает наткнуться на такой "оазис" в сетевой пустыне, где тебя приветливо встретят и любезно "озадачат" прямо с порога. Об одном из таких уголков, постоянно живущем сетевом конкурсе "Программист месяца" (Programmer Of The Month - POTM), и пойдет далее речь. А обнаружил я его по адресу www.cs.washington.edu/homes/corin/POTM.PAGES/.

"Зубры" программирования, вероятно, оценят разместившийся на этом сервере богатый архив с условиями задач прошлых первенств. Первоначально они проводились в недрах компании AT&T, но со временем доросли до планетарных масштабов. За пять лет участникам было предложено два с лишним десятка самых разнообразных задач. Некоторые из них за это время стали классическими и пополнили всевозможные сетевые архивы. С какими только проблемами не приходилось сталкиваться завсегдатаям конкурса! Это и программирование логических игр с несколькими участниками (бои обычно велись по олимпийской системе с выбыванием, все захватывающие результаты финальных поединков доступны здесь же, на сервере), и решение математических головоломок (в том числе знаменитой игры в "пятнадцать", а также криптарифмов, так хорошо знакомых постоянным читателям "КТ"). Особого внимания заслуживают и "тяни-толкаи" - гибриды нескольких хорошо известных задач - например, задачи обхода доски шахматным конем с "задачей коммерсанта", предложенной в POTM три года назад. Нужно признать, что за время проведения первенства уровень задач постепенно возрастал, так что будущим призерам, вероятно, придется изрядно попотеть. Зато слава обеспечена: помимо получения титула POTM и чести лицезреть свою фамилию в "галерее славы", триумфатор награждается также переходящим призом - роскошной "доской почета" от генерального спонсора - компании AT&T (см. рис. 1), на которой отныне гордо значится и его собственное имя. Правда, заморским (неамериканским) победителям, похоже, придется довольствоваться лишь ee живописным изображением в формате GIF…

_В качестве решений принимаются исходные коды программ на C/С++, Java, а также таких экзотических для российских программистов языках, как, например, Perl и Python. Тексты на Pascal и Fortran в принципе принимаются тоже, но перед компиляцией транслируются на C, что заранее дает фору "сишникам" и "джавистам".

"И почему я связался с этими вещами? - недоумевает про себя Фред Хайсинбозем (Fred Hicinbothem) - основатель и бессменный ведущий конкурса. И тут же отвечает на свой вопрос. - Очевидно, по той же самой причине, по которой вы участвуете в них, - это весело!" И его мнение разделяют около двух тысяч человек по всему свету, регулярно получающих по e-mail донесения о ходе очередного первенства. Чтобы попасть в список рассылки POTM, достаточно послать письмецо с соответствующей просьбой по адресу fah@potm.ffast.att.com. И тогда уж, будьте уверены, известие о новом конкурсе вас не минует. Если же вы настроены куда как более решительно и хотите непосредственно быть в курсе всех основных событий последнего тура, пошлите письмо по этому же адресу, набрав в качестве Subj слово "Enter".

Интересно, что в качестве второй причины своего начинания лукавый "отец-основатель" называет ни больше ни меньше как производственную необходимость: часть конкурсных заданий представляют собой самые настоящие злободневные задачи, с которыми он, ведущий программист компании AT&T с двадцатипятилетним стажем, неоднократно встречался в своей практике. Добавим к этому, что некоторые из них до сих пор, возможно, не имеют эффективного решения. С другой стороны, чем черт не шутит? Может быть, кто-то из читающих эту заметку возьмет и напишет программу, которая затмит все, когда-либо присланные на этот конкурс… Тем более что фамилий российских программистов в "галерее славы" пока что-то не наблюдается.

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

Итак, задача нынешнего, весенне-летнего первенства, достаточно нетривиальная при внешне традиционном условии, носит название "Scenic Tour", что на русский переводится как "Гастроли" (хотя, по-моему, тут больше бы подошло толкиеновское "Туда и обратно"). Суть ее сводится к нахождению оптимального циклического пути внутри квадратной сетки размером SIZEхSIZE клеток (при этом SIZE не превосходит 256), который задается последовательностью координат клеток, через которые он пролегает. Путь должен начинаться и заканчиваться в левой верхней клетке с координатами (0,0), при этом он обязательно должен включать правую нижнюю клетку с координатами (SIZE-1, SIZE-1), которая делит его на два участка - прямой и обратный. При этом из каждой клетки за один ход можно переместиться в ее "соседку" (имеющую с ней общую сторону или вершину). В каждой клетке вписано натуральное число от 0 до 255, выражающее ее "высоту". Расстояние между двумя соседними клетками определяется как модуль разности их "высот" (иначе говоря, на сколько нужно "подняться" или "опуститься", чтобы попасть в соседнюю клетку). Таким образом, длина пути между любыми двумя клетками находится как сумма расстояний между соседними клетками на каждом шаге, входящем в этот путь.

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

1. Ни одна клетка, кроме начальной, не может посещаться дважды, хотя путь может петлять и самопересекаться как угодно; выходить за границы сетки при этом категорически запрещается!
2. Отношение длин частичных путей "обратно" и "туда" должно быть максимальным; то есть выигрывает программа, нашедшая путь с максимальным значением показателя LONG_SCORE/SHORT_SCORE, где SHORT_SCORE - длина "обратного" пути между клетками (SIZE-1,SIZE-1) и (0,0), а LONG_SCORE - длина "прямого" пути между (0,0) и (SIZE-1,SIZE-1). При этом во избежание деления на нуль по крайней мере у двух этих крайних клеток "высоты" различны.
3. Путь может состоять не более чем из LIMIT ходов; при этом LIMIT не менее 4хSIZE и не более 20хSIZE (что, в свою очередь, дает нам некоторую свободу для маневра по обходу "нежелательных" клеток). В качестве примера на рис. 2 приведен удовлетворяющий условиям путь для сетки 4х4, показатель которого равен 34/8=4,25.

Для всех программ, участвующих в конкурсе, действуют также ограничения на размер исходного кода - 25 Кбайт, исполнимого кода - 1 Мбайт, а также ограничение на объем используемой динамической памяти, которое можно назвать чисто символическим, - 50 Мбайт (!). Ограничено и время расчета каждого теста: не более десяти минут на "малютке" SPARCStation, используемой для финального тестирования, что, в общем-то, тоже немало. Здесь же, на сервере, можно скачать программу-таймер для оценки того, удается ли вашей программе "уложиться" в заданное время.

Заметим, что каждую неделю на сервере POTM публикуются сводки с места событий, где фиксируются все присланные решения и результаты, показанные программами на предварительных тестах. Впрочем, еще не вечер - официальные итоги будут подведены в полночь 26 июня, после того как все присланные программы "обкатают" на тройке контрольных тестов и победитель определится по сумме полученных значений критерия. Если же (о, чудо!) эти значения у нескольких участников все-таки совпадут, то в расчет будет браться время решения. Пока же у всех участников достаточно времени, чтобы "утяжелить" свои решения каким-нибудь новым, нетривиальным алгоритмическим ходом.

Напоследок мне остается лишь пожелать удачи всем потенциальным лауреатам. Успешных вам "гастролей", эффективных алгоритмов и остроумных решений!Написать комментарий (комментариев - нет) | Послать другу

Парадокс узника

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

Сижу за решеткой в темнице сырой…

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

Через некоторое время узник обрел способность нормально размышлять. Он немедленно сделал вывод, что казнить в следующее воскресенье его не могут: ведь тогда еще в субботу вечером будет ясно, что для казни остался один-единственный возможный день. Это будет означать, что узнику стал известен день казни еще до наступления этого дня, а такого не может быть по определению - ведь начальник никогда не лжет!

"Иными словами, последний возможный день для моей казни, - думал узник, - это суббота. Но тогда если меня не казнят в пятницу утром, то к вечеру пятницы я тоже буду точно знать день, когда меня должны казнить. Однако начальник сказал, что о дне казни я узнаю лишь утром, а не накануне вечером, - значит, и в субботу меня не могут казнить тоже".

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

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

В среду утром заключенному, уже уверенному в своей безнаказанности, сообщили, что сегодня его казнят. Это явилось для него полной неожиданностью - и значит, условие начальника оказалось выполненным. Получается, что невыполнимое предписание оказалось возможным исполнить именно из-за его якобы невыполнимости! Каково?

Обсуждение первое

Один из первых же вопросов, на которые приходится отвечать: можно ли считать, что начальник сам назначает день казни? Можно сказать, что да. А можно и сказать, что это делает за него компьютер. Так и сделаем: чтобы не обсуждать стратегии поведения начальника тюрьмы, будем считать, что день казни он узнает по датчику случайных чисел. Возможные значения датчика - от 1 (понедельник) до 7 (воскресенье). Кроме того, поскольку число дней в неделе не играет особой роли, то можно сразу обобщить парадокс на случай N возможных дней казни и исследовать его при различных N.

При N=1 парадокс очень прост. Начальник говорит буквально следующее: "Вас казнят завтра, но до завтрашнего утра вы ничего об этом не узнаете". Это утверждение противоречиво само по себе, поэтому никакой информации узник из него вынести не сможет. Противоречивые утверждения не могут быть ни истинными, ни ложными. Иначе говоря, из всей информации парадокса можно сделать только один вывод: начальник тюрьмы не всегда говорит правду.

Наиболее интересно рассмотреть случай N=2. Повторим рассуждение заключенного именно в этом случае: "Меня не могут казнить во вторник, так как иначе я узнал бы об этом к вечеру понедельника. Но тогда меня должны казнить в понедельник, и я знаю об этом уже сейчас. Это противоречит утверждению начальника о том, что я не должен узнать дату казни до ее наступления". Дальше заключенный решает, что начальник солгал ему. И только утром в тот из двух дней, на который укажет компьютер, оказывается, что начальник сказал правду…

В чем здесь противоречие и в чем ошибка - в рассуждениях узника или в исходном утверждении начальника тюрьмы?

Обсуждение второе

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

Я предлагаю читателям пока подумать над этим самостоятельно. А также - над разницей между этим вариантом парадокса и тем, когда начальник сам (без помощи компьютера или какого-то другого датчика случайных чисел) назначает день казни.

А теперь - решение. Точнее, одно из возможных решений.

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

Если же понимать утверждение начальника так, как он его и формулировал - что узнику разрешается сделать предсказание только один раз (например, назвать дату своей казни до наступления понедельника), то у заключенного нет никакой возможности точно узнать эту дату заранее. Его могут казнить или в понедельник, или во вторник (или в любой другой день недели в случае N=7) - в полном соответствии с информацией, сообщенной начальником тюрьмы.

Парадокс создается именно из-за неполноты условия, а также из-за двойственности интерпретации понятия "ожидаемая дата казни".

Откажемся от компьютера

Ну, а теперь поехали по второму кругу. Представьте себе, что дату казни выбирает сам начальник тюрьмы. Тогда для N=2 рассуждения узника безупречны и, следовательно, условия задачи противоречивы. Так? А что получается для N=7 или N=1998? По-прежнему ли задача определения дня казни, поставленная начальником перед заключенным, лишена смысла? Или уже нет? И если нет, то при каком конкретном N происходит переход от первой ситуации (противоречивость и бессмысленность условия) ко второй (условие корректно, а рассуждения узника ошибочны)?

Предположим, что для N-1 задача еще противоречива, а для N - уже нет. Если бы начальник выбрал любой из дней от второго до N-го, то у него была бы всего N-1 возможность. Значит, в этом случае задача была бы противоречивой. А раз мы предположили, что это не так, то начальник должен выбрать для казни только первый день! И это уже известно узнику, что снова-таки делает задачу противоречивой…

Все ли верно в предыдущем абзаце? В чем состоит правильное объяснение парадокса в этом случае и есть ли здесь вообще парадокс?

Подумайте - это иногда бывает очень полезно.

Если вы имеете возможность читать статьи на Web, заходите ко мне на страничку, там лежат наиболее полные (и уже свободные от ошибок) версии моих статей. Хочу также поблагодарить всех читателей, заметивших ошибку в табличке 20x25 из статьи "Острова в океане". Эта ошибка исправлена в одном из последних выпусков "хвостов", а также в статье на моей homepage.Написать комментарий (комментариев - нет) | Послать другу

"Сапер": от игры к задачам

Большинство читателей, вероятно, играли в "Сапера" (он же "Minesweeper"), ведь эта игрушка входит в стандартный комплект поставки Windows. "Сапер" относится к тем простеньким играм, вроде "Tetris" или "Lines", в которые люди иной раз играют часами, чему сами же и удивляются. Это - верный признак гениальности игры. Такие игры иногда порождают целые классы занимательных задач, и "Сапер" не является исключением. Но прежде чем перейти к задачам, напомню правила игры.

Имеется прямоугольное минное поле, поделенное на закрытые клетки. Одни клетки пусты, в другие заложены мины. Любую клетку можно открыть или пометить как содержащую мину. Можно пометить и пустую клетку. Если открыть клетку с миной, то игра сразу заканчивается (сапер ошибается один раз). Открыв пустую клетку, вы увидите в ней цифру (от единицы до восьмерки), равную числу мин, находящихся в восьми клетках, которые окружают открытую вами клетку. (Если открытая пустая клетка окружена клетками, также не содержащими мин, то эти пустые клетки открываются автоматически.) Цель игры - за минимальное время правильно пометить все мины и открыть все остальные клетки.

Найти все мины на поле -цель "саперных" задач первого типа. На рисунках 1-8 изображены минные поля, некоторые клетки которых уже открыты. Попробуйте найти все мины на рисунках. Число слева над игровым полем показывает, сколько всего мин размещено на поле.

Разновидностью этого типа задач являются алгоритмические "саперные" задачи. Они отличаются тем, что, исходя из уже открытых клеток, нельзя однозначно определить расположение всех мин.

Алгоритм решения таких задач может быть простым, например:

Открыть клетку A.

Если A=2, то пометить клетку B (как содержащую мину), иначе пометить клетку С.

Но алгоритм может быть и крайне сложным, многократно разветвляющимся. Составить алгоритм нетрудно. Можно просто, как в самой игре, разыгрывать позицию, при этом лишь нужно следить за возможными разветвлениями. Но лучшим решением будет кратчайший алгоритм, а найти его, особенно в позициях, где еще много закрытых клеток, бывает очень нелегко. Тем не менее, попробуйте найти кратчайший алгоритм решения задач на рис. 9 и 10. Первая - простая, вторая уже посложнее.

Другой класс "саперных" задач - вероятностные задачи. Обычно в них требуется найти вероятность того, что в какой-либо клетке в данной позиции находится мина. При решении таких задач учитывается число и расположение уже обнаруженных мин, а также число еще закрытых клеток поля (не стану приводить общую формулу - найдите, пожалуйста, сами). Попробуйте вычислить вероятность того, что на рисунках 11-14 в клетке X находится мина.

Но бывают и другие вероятностные задачи, например: дано поле 8х8 клеток с десятью минами, открывается клетка в левом верхнем углу. Найдите вероятность того, что в этой клетке стоит единица (двойка, тройка, ноль). А когда найдете, проверьте, учитывали ли вы то, что самая первая открываемая клетка никогда не содержит мину?

Нашли? А теперь попробуйте вычислить вероятность того, что в поле размером MхN и числом мин, равным K, в угловой клетке стоит цифра R=0, 1, 2, 3. И с этим справились? Ну тогда найдите общую формулу вычисления вероятности той или иной цифры на первой открываемой клетке минного поля: дано поле MхN, К - число мин на поле, L - число клеток, смежных с открываемой.

А вот другой тип "саперных" задач: попробуйте так расставить мины на поле 8х8 (в общем случае - MхN), чтобы в каждой клетке стояла цифра от 1 до 8 (не 0). Сколько мин минимально для этого потребуется? А максимально? Сколько существует способов расстановки?

И еще один тип задач: как следует расставить десять мин на поле 8х8, чтобы сумма всех цифр, стоящих на свободных клетках, была равна, например, сорока? А пятидесяти, шестидесяти, какому-либо другому числу? Какова минимальная сумма? А максимальная? И как при этом расставить мины?

Вот еще две несложные задачи.

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

Дано поле 10х10 клеток. Открыта вся верхняя строка. Во всех клетках - единицы. Какова вероятность нахождения мины во второй сверху строке в четвертом столбце?

И наконец задание для программистов: составить программу, которая играла бы в "Сапер" и как можно реже проигрывала. Сделать это непросто, полный перебор тут не годится, надо программировать эвристики, чем больше - тем лучше.

Удачи в решении!

* * *

Дополнение Константина Кнопа

Эта статья пришла по почте и напечатана почти без исправлений, хотя у меня сильно чесались руки добавить еще несколько задач на эту же тему. Решив не вставлять их в авторский текст, я все-таки хочу их привести.

1. В игре (скажем, на поле 8х8) часто бывает так, что о некоторых клетках достоверно известно, есть там мины или нет, а о других клетках можно только догадываться. Чему равно наибольшее количество клеток, о которых нельзя ничего сказать достоверно? (Делать ходы нельзя, можно анализировать только начальную информацию.) В частности, бывает ли геймстоппер с самого начала?

2. Напишите программу для игры "Сапер вдвоем": игрок делает ходы до тех пор, пока не нарвется на мину, а затем ходит второй игрок, и так далее. Выигрывает тот, кто откроет последнюю мину.Написать комментарий (комментариев - 1) | Послать другу

Что наша "Жизнь"? - Игра!

Скажу по секрету - у этой рубрики есть несколько постоянных читателей, которые время от времени пишут мне письма: "Константин, а не напишете ли Вы в "Досугах" вот на такую-то тему?" Если тема мне кажется не очень избитой, я стараюсь просьбу выполнить. А если очень - вежливо отвечаю, что на эту тему писал еще Мартин Гарднер, а мне после него делать нечего.

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

О замечательной игре "Жизнь" Мартин Гарднер писал как минимум трижды. Эти три его статьи из математической рубрики журнала "SciAm" ("Scientific American") переведены на русский язык и вошли в книгу "Крестики-нолики" (М., "Мир", 1988). Там же приведена и библиография на английском языке.

Прежде чем рассказать о том, что же нового открыто в "Жизни" после статей Гарднера, я хочу напомнить суть и основные правила игры.

Вся игра происходит на бесконечной клетчатой доске. Сначала на ней берется какое-нибудь расположение фишек (организмов). Затем эти организмы начинают "жить" - размножаться и умирать, подчиняясь при этом строгим "генетическим законам". Таких законов в игре всего два:

1) каждая особь, у которой есть 2 или 3 соседние особи, выживает - то есть переходит в следующее поколение; все остальные особи погибают.

2) в каждой пустой клетке, у которой есть рядом 3 живые соседние клетки, в следующем поколении рождается новая особь.

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

Оказывается, что такие простые законы приводят к игре, фантастически богатой по возможностям. Многие начальные конфигурации долго эволюционируют, а затем погибают. Другие становятся "осцилляторами" - то есть периодически повторяющимися фигурами. Третьи неограниченно растут и даже размножаются, воспроизводя сами себя.

Первые опыты с "Жизнью" проводились на больших ЭВМ еще в начале 1970 годов. Это была первая компьютерная игра, убытки от которой (в виде потраченного машинного времени) оценивались миллионами долларов. Несколько групп исследователей, занимавшихся проблемами искусственного интеллекта, сразу после первых публикаций практически полностью переключились на исследование "Game of Life".

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

Shareware программу Life 1.06 (автор - Ал Хенцель) можно получить с ftp://ftp.life.anu.edu.au/pub/complex_systems/alife/life/ life16.zip, она работает под MS-DOS и является самой быстрой из всех существующих программ. Хорошая программа Winlife (под Windows) написана Джоном Харпером, ftp://ftp.digital.com/pub/games/winlife.zip (в этом же архиве есть довольно много интересных картинок). Еще большие коллекции картинок имеются на ftp://alife.santafe.edu/pub/topics/cas/software/lifep.zip и на http://ddi.digital.net/TILDEalanh/lifepw.zip; Тем, кто захочет посмотреть на "Жизнь" повнимательнее, я их очень рекомендую. Все коллекции картинок написаны на одном и том же входном языке, то есть могут быть загружены как в программу Life, так и в программу Winlife.

Существует и доступен трехмерный вариант "Жизни": ftp://life.anu.edu.au/pub/complex_systems/alife/ 3DLIFE.ZIP.

Наконец, этот перечень ресурсов будет явно неполным, если я забуду упомянуть про целый раздел каталога Yahoo!, посвященный "Жизни" и ее вариациям: www.yahoo.com/Science/Artificial_Life/ Conway_s_Game_of_Life/index.html.

Увы, я хорошо понимаю, что у многих читателей нет доступа к Интернету, в лучшем случае есть e-mail. Если вы хотите получить программу Life по электронной почте, напишите мне, и мы вместе что-нибудь придумаем.

Ну, а теперь собственно картинки - те, которых не было у Гарднера и ради которых я все это и писал.

Одной из первых открытых в "Жизни" фигурок, которые способны бесконечно перемещаться по игровому полю, был "планер". В начальной позиции - три планера, летящих навстречу друг другу. Оказывается, что после встречи планеры разрушаются, но в результате образуется большой "летающий объект", который и продолжает полет!

На этом рисунке изображена фигура, получившая название "автомат Калашникова". Два "автомата" слева и справа устроены так, что периодически стреляют навстречу друг другу, и их выстрелы в результате столкновения превращаются в планеры, которые спокойно разлетаются в разные стороны… Вот если бы все военные столкновения заканчивались так мирно!

Это - быстрорастущая "опухоль". Она растет во все стороны со скоростью, равной 1 клетке за каждые 2 хода. Уже давно было доказано, что большей скорости роста в "Жизни" существовать не может, а вот пример такой "опухоли" найден совсем недавно.

А это просто мираж. Огромная картинка за считанные ходы рассыпается как карточный домик. Сначала от нее остается всего несколько планеров, а примерно на 75-м ходу и они сталкиваются друг с другом и аннигилируют.

И десерт для гурманов: когда эта статья уже была написана, я узнал о замечательном конкурсе рисунков тьюрмитов, который проводится Университетом города Переславля (а точнее, его преподавателем Евгением Лилитко). Участвовать могут все желающие, но надо торопиться: конкурс завершится 30 апреля. Что представляют собой тьюрмиты и почему они связаны с игрой "Жизнь", вы можете узнать из информации о конкурсе - http://up.botik.ru/~inform/thurmits/. А я обещаю спустя несколько недель вернуться к этой теме и подробно рассказать о тьюрмитах и победителях конкурса.Написать комментарий (комментариев - нет) | Послать другу

Досуги

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

Небольшой пикап находится в пустыне около склада горючего, содержащего N полных бочек бензина вместимостью по 50 галлонов каждая. (Для справки: один галлон в США примерно равен 3,78 литра, а в Великобритании несколько больше - 4,55 литра.) Бак пикапа, который сейчас пуст, вмещает 10 галлонов, при этом одного галлона бензина хватает на 10 миль пути. Пикап может перевозить только одну бочку горючего (пустую или полную).

Спрашивается, как далеко можно уехать от начальной точки?

Обсуждение

Ясно, что если бочка одна, то ее хватит на 500 миль пути. А что, если бочек две (иначе говоря, есть 100 галлонов топлива)? В этом случае правильной стратегией будет такая:

1) сначала отвезти одну бочку на 100 миль, оставить ее там, залить полный бак и вернуться обратно;

2) погрузить вторую бочку и довезти ее до первой;

3) отвезти первую бочку еще на какое-то расстояние и снова вернуться ко второй бочке;

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

5) отправиться дальше - с полным запасом топлива можно проехать еще 600 миль.

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

Несложный подсчет показывает, что "какое-то расстояние" равно 100/3=33,33 мили, при этом на этапах 1) и 2) мы истратим 30 галлонов, а на этапах 3) и 4) еще 10 галлонов. Соответственно, на этапе 5) останутся как раз необходимые нам 60 галлонов (50 в бочке и 10 в баке). Всего, таким образом, можно проехать 100+100/3+600=733,33 мили.

Задача 1

Какое расстояние можно проехать, имея вначале 3 бочки (150 галлонов) бензина?

Задача 2

А четыре бочки (200 галлонов)?

Задача 3

А теперь попробуйте догадаться, какой может быть общая формула для расстояния, которое может пройти пикап, если вначале есть N бочек.

Решения задач 1-3

1. Сначала все три бочки надо перевезти на 60 миль (это требует пяти поездок туда/обратно, и на эти поездки уйдет 5х6=30 галлонов).

Потом две из трех бочек нужно два раза перевезти на 100 миль вперед (еще шесть поездок, 6х10=60 галлонов). Наконец, с запасом 60 галлонов пикап оказывается в 260 милях от точки старта, после чего делает финишный рывок на 600 миль.

2. Если идея решения предыдущей задачи понятна, то эта задача тоже не должна вызвать затруднений. Заметим, что перевозка X бочек всегда требует (2X-1) поездок, при этом для перевозки их на расстояние 10хL миль уйдет (2X-1)хL галлонов бензина. Сначала все 4 бочки надо перевезти на расстояние 200/7 (20 галлонов). Потом три бочки перевозятся в общей сложности на 120 миль вперед (еще 5 поездок, 60 галлонов), для дальнейшей перевозки оставляются уже только две бочки - их мы отвозим еще на 200 миль (снова 60 галлонов). Наконец, последние 60 галлонов снова позволяют проделать 600-мильный финишный участок. Постарайтесь понять, почему именно такое решение будет наилучшим.

3. Само собой напрашивается следующее предположение: на каждый этап, кроме самого первого, в оптимальном решении уходит ровно 60 галлонов бензина. Таких этапов ровно N-1, а на первом этапе надо израсходовать весь остальной бензин.

Например, при N=5 для первого этапа должно остаться 250-4х60=10 галлонов бензина, поэтому на этом этапе удастся проехать расстояние 100/9=11,11. А всего при этом удастся проехать расстояние (600/7 + 600/5 + 600/3 + 600/1) + 100/9.

Задача 4 (первый сюрприз)

Сразу скажу, что предположение, сделанное в решении третьей задачи, верно для N=5 и N=6, но неверно для всех больших значений N. Легко понять почему: ведь уже при N=7 вначале имеется не 6х60 галлонов, а всего лишь 7х50=350. Какой же все-таки будет лучший результат для N=7?

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

Ответ к задаче 4

Для 7 бочек (350 галлонов), по-видимому, лучшей является такая последовательность действий:

1. Перевезти 6 бочек на 500/11 (50 галлонов).

2. Перевезти 5 бочек на 600/9 (60 галлонов).

3. Перевезти 4 бочки на 600/7 (60 галлонов).

4. Перевезти 3 бочки на 600/5 (60 галлонов).

5. Перевезти 2 бочки на 600/3 (60 галлонов).

6. Проехать с 1 бочкой 600/1 (60 галлонов).

Итого: 500/11 + 600/9 + 600/7 + 600/5 + 600/3 + 600/1 = 1117,83 мили.

Теперь может показаться, что необходимая поправка к предположению уже найдена: на нескольких первых этапах надо перевозить не все бочки, а на одну бочку меньше (здесь - шесть вместо семи). При этом на каждый из этих этапов вроде бы надо расходовать всего 50 галлонов. Тогда на последние 5 этапов останется ровно 300 галлонов - как раз по 60 на каждый этап. Однако и здесь не все так гладко.

Задача 5 (второй сюрприз)

При N=8 (400 галлонов) решение задачи о пикапе, основанное на описанном только что алгоритме, позволяет проехать 1156,30 мили. А на самом деле существует лучший способ, при котором удается покрыть расстояние 1157,23 мили - почти на целую милю больше.

Попробуйте отыскать этот способ самостоятельно, не заглядывая в ответ.

Ответ к задаче 5

1. Перевезти 7 бочек на 100/3 (43,33 галлона).

2. Перевезти 6 бочек на 1700/33 (56,66 галлона).

Таким образом, вместо расстояния 500/13 + 500/11 = 83,91 мили на этих двух этапах 6 бочек перевезены на 100/3 + 1700/33 = 84,84 мили.

Вот и выигрыш в дистанции! Ну а все следующие этапы требуют по 60 галлонов бензина в обоих вариантах решения.

Послесловие

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

Возможно, все дело в том, что интересы "чистых программистов" лежат далеко от занимательных задач? Ну а поскольку читатели "Компьютерры" довольно часто просят меня давать побольше упражнений для любителей программировать, я это делаю с удовольствием и всегда надеюсь, что кто-нибудь преуспеет в их решении.

У меня появилась своя страничка в Интернете: http://come.to/knop.

Приходите в гости!Написать комментарий (комментариев - нет) | Послать другу

Картинки для разминки

Сегодня выпуск "Досугов" необычен. В нем очень много картинок. И это не случайно: я попытаюсь с одного наскока заткнуть дыру, которая существует и расширяется уже много лет. Эта дыра - практически полное отсутствие у нас (в России и вокруг нее) такого класса задачек (и в том числе механических головоломок), как "задачи из коробочки". Конечно, "пятнашки" известны всем, но на этом все и заканчивается. А на Западе такие головоломки называются Sliding Piece Puzzle и очень популярны. Механические sliding puzzles имеются почти в каждой семье, им посвящены книжки, телевизионные конкурсы и все остальные атрибуты, характеризующие то общество, у граждан которого есть не только конституционное право на отдых, но и время для этого самого отдыха.

Картинка 1.

Картинка 2.

Картинка 3.

Картинка 4.

Суть всех задачек очень хорошо иллюстрируется картинкой 1. В ее левой части - коробочка 2х3, в которой одна (черная) клетка пуста, а в остальных лежат единичные квадратики. Каждый такой квадратик можно двигать в пустую клетку (как в пятнашках), а цель передвижений - добиться ситуации, изображенной в правой части картинки. Здесь изображены два из пяти исходных квадратиков (красный и зеленый), причем они должны поменяться местами. Что будет при этом находиться в остальных клетках - значения не имеет, именно поэтому остальные клетки помечены вопросиками. Задача состоит в том, чтобы перейти от левой части к правой, причем постараться сделать это за наименьшее число ходов.

Картинка 5.

Задачка с картинки 1 очень проста, а первой интересной задачкой моей подборки является картинка 2. В ней нужно передвинуть вертикальный синий прямоугольник в противоположный угол квадрата. При этом поворачивать прямоугольники, конечно же, нельзя, - только сдвигать.

Картинка 6.

Задача с картинки 3 является первой из серии "классических": создателем этой головоломки является то ли С. Лойд, то ли Г. Э. Дьюдени (эти два знаменитых головоломщика очень часто спорили друг с другом о приоритете). Удивительно, но при всей простоте ее условия решить ее очень непросто. Впрочем, это же относится и к большинству следующих задач. Несколько из них тоже можно смело отнести к классике жанра: см. картинки 4, 5, 6 и 7.

Картинка 7.

Картинка 8.

Картинка 9.

В классических головоломках этого типа есть несколько стандартных ограничений: размеры поля 4х5, причем свободными являются только две клетки, а остальные заполняются квадратом 2х2, пятью прямоугольниками 2х1 и четырьмя маленькими квадратиками. Как правило, нужно перенести большой квадрат симметрично относительно его начального положения. Почти удовлетворяет всем этим свойствам картинка 8 - в ней синий квадрат нужно вытащить из окружения остальных фигурок. Должен сразу сказать, что она очень сложная: я сумел ее решить только после того, как сумел затащить синий квадрат в правый нижний угол, переставить остальные фигурки, снова вытащить квадрат из этого угла вверх, снова сделать сложную перестановку фигурок. Только потом квадрат снова можно перемещать в правый нижний угол и уже оттуда - на место. Может, кто-то обнаружит более короткое решение? Мне было бы очень интересно…

Картинка 9 показывает, как можно самому придумывать новые "коробочки". Получилась она так: я взял картинку 5 и удлинил на 2 клетки вниз. А потом заметил, что маленькие квадратики можно легко переставить в самый низ картинки. Решение этой задачи аналогично решению ее прототипа, но длиннее.

Картинка 10.

Картинки 10 и 11 - задачи, придуманные в Японии в последние несколько лет. Японцы вообще очень любят подобную гимнастику ума. Может, в этой черте их национального характера и надо искать истоки "японского экономического чуда"?

Картинка 11.

В задаче с картинки 11 требуется собрать из двух уголков прямоугольник 2х3 в правом верхнем углу. При этом есть даже два варианта - один изображен на картинке, а во втором этот прямоугольник расположен вертикально.

Картинка 12.

А последняя задачка - небольшая шутка. Это хорошо известная задача о расхождении кораблей в канале. Два желтых "корабля" надо отправить влево, а два красных - вправо. Но все дело в том, что традиционным способом это можно сделать только за 36 ходов (ходом считается перемещение на 1 клетку). А кратчайшее решение - 32 хода. Найдете? Желаю успехов. Пишите мне, как обычно, по адресу kk@knop.spb.ru . Да, чуть не забыл. Программку, которая позволит вам прорешать некоторые (не все!) из этих задач, можно найти в Интернете: www.damtp.cam.ac.uk/user/aykc1/comp/newslide.html

Она написана под Windows 95, но сравнительно невелика по объему (50 килобайт архива) и проста в обращении.Написать комментарий (комментариев - нет) | Послать другу

Острова в океане

На одной из первых олимпиад школьников по программированию предлагалась такая задача:

Океан изображен (закодирован) матрицей NxN. Каждый остров - это "звездочка" в матрице. Задача состоит в построении карты островов только по кодированной информации о горизонтальном и вертикальном расположении островов. Чтобы проиллюстрировать этот код, рассмотрим такую "карту":

Числа слева от каждой строки показывают порядок и размеры групп островов в этих строках. Например, "1 2" в первой строке означает, что в этой строке находится группа из одного острова, за которой идет группа из двух островов с океаном произвольной длины слева и справа от каждой группы островов. Аналогичным образом последовательность "1 1 1" над первым столбцом означает, что в этом столбце находится три группы с одним островом в каждой, и т. д.

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

Покажем, как это можно сделать для уже нарисованной выше карты. Например, можно начать с заполнения четвертого столбца.Так как там стоят числа "2 3", то в этом столбце располагаются ровно пять островов: два сверху, потом океан, потом еще три острова. Но так как высота столбца равна 6, то океан занимает в этом столбце ровно одну клетку. Таким образом, четвертый столбец уже заполнен. Дальше аналогично заполняется, скажем, пятая строка. Карта постепенно прорисовывается и приобретает такой вид:

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

Я не буду лишать читателей удовольствия самим закончить решение этой головоломки. Но все дело в том, что задача "острова в океане" - это не начало истории, а ее середина. А начало ей положил еще на пару лет раньше японец Нишио Тецуя (Tetsuya Nishio). Именно он является автором этого замечательного типа головоломок. Впервые такие задачки - Нишио назвал их paint-by-numbers - были предложены им на международном конкурсе решателей головоломок, состоявшемся в 1990 году. При этом участники состязались между собой на скорость решения серии таких задач (и естественно, на правильность). Головоломки понравились многим - и очень быстро завоевали себе место на страницах самых разных изданий, посвященных головоломкам и занимательным задачам. Печатались они и у нас - в газете "Поле Чудес" - под названием "японские кроссворды".

Вот еще две задачи из серии paint-by-numbers. Первая - 10x10, вторая - 20x25. И, как обычно, предлагаю к ним в качестве добавки сверхзадачу для любителей поупражняться в программировании. Добавка, впрочем, уже сформулирована: надо написать программу, которая сможет самостоятельно решать задачи типа "островов в океане" для больших карт. (Обратите внимание, что при картах размера 50x50 полный перебор вариантов уже потребует очень большого машинного времени, так что этот путь мне представляется тупиковым. А вот если попробовать применять различные эвристики, наподобие тех, которые использует человек при решении такой задачи, поиск решения может быть существенно упрощен и сокращен.) Желаю успехов! Пишите мне, как всегда, на kk@knop.spb.ru

Написать комментарий (комментариев - нет) | Послать другу

И снова о кубике

Наши постоянные читатели наверняка помнят, что почти год назад ("Компьютерра" ##14 и 15 за 1997 год) я уже писал о кубике Рубика. Как ни удивительно, эта когда-то суперпопулярная, а ныне полузабытая головоломка так и не открыла исследователям всех своих тайн, и находятся все новые и новые любители повозиться с кубиком, которые и делают в этой области пусть небольшие, но самые настоящие открытия.

В тех номерах я рассказывал о нескольких направлениях, в которых энтузиасты кубика ведут поиск, - в частности, о так называемом алгоритме Бога и о создании компьютерных программ, способных за небольшое число ходов (поворотов граней) собирать кубик, то есть из любого допустимого положения приводить его в начальное. Оказалось, что я несколько опередил события - именно в прошедшем 1997 году исследователи существенно продвинулись в этом направлении. В частности, сегодня каждый обладатель компьютера с Windows может совершенно свободно сгрузить из Интернета и запустить у себя на машине программу Cube Explorer, которая собирает кубик практически из любого положения не больше чем за 24 хода.

С помощью этой программы можно самому задавать различные узоры на кубике (причем иметь механическую головоломку вовсе не обязательно - вполне достаточно ее изображения на экране). А потом программа расщелкивает ваши узоры как орехи. Начинает с решения, содержащего 26 ходов, затем быстренько находит 25, 23, 20, 18, немного притормаживает, обнаруживает 15 и - после длительного перебора - 14 ходов. Кто сказал, что компьютер бывает умным только против Каспарова? Это неправда. Каждый компьютер имеет такого хозяина, который его заслуживает.

Рисунок 1.

Вот один из примеров того, как Cube Explorer расправляется с очень сложными задачами. На первом рисунке изображен "крест третьего порядка". Это совсем не тот крест, который многие собирают с закрытыми глазами. Здесь - обратите внимание - желтая, синяя и красная грани образуют кресты только желтого, синего и красного цвета, а белая, зеленая и оранжевая грани также меняются крестами друг с другом. Алгоритм сборки такого рисунка, приведенный когда-то в одном из номеров журнала "Наука и жизнь" (кажется, за 1983 год), состоял из тридцати с хвостиком ходов. А теперь решение из 16 ходов находится примерно за 30 секунд счета. Выглядит оно так: L2 R' F D2 L' F' D U' B F' D R F2 D' L R2. Буквами здесь обозначаются грани куба, а цифрами и апострофами - углы, на которые эти грани нужно вращать. R (от слова right, в русской нотации обычно писали П) - правая грань, L (left, по-русски Л) - левая, F (front, Ф) - фасадная, то есть ближняя к нам, B (back, Т) - тыльная, то есть дальняя от нас. Наконец, U (up, В) - верхняя и D (down, Н) - нижняя. Обратите внимание, что буквы обозначают именно положение граней относительно наблюдателя, а не цвета. Кубик можно взять в руки по-разному - и в результате тех же вращений мы получим другой узор. Цифра 2 после буквы означает, что грань нужно повернуть на 180 градусов. Апостроф соответствует повороту на 90 градусов против часовой стрелки. А если после буквы не стоит ни двойка, ни апостроф - грань вращается на 90 градусов по часовой стрелке. Любой из этих трех поворотов в "кубологии" считается одним ходом.

Рисунок 2.

На втором рисунке изображен другой, не менее известный узор. Его традиционное название - "куб внутри куба". Не правда ли, похоже? Хорошо виден один из "кубов внутри куба", но на самом деле их два. Другой находится с противоположной стороны, но грани, его образующие, нарисованы на развертке так, что, лишь обладая хорошим пространственным воображением, можно понять, что три этих квадратика тоже относятся к одному кубу со стороной 2.

Решение этой сложной задачи, оказывается, требует всего 15 ходов! Вот оно: L F L D' B D L2 F2 D' F' R U' R' F2 D. Кстати, если у вас есть не "электронный", а обыкновенный механический (чуть не написал "живой"!) кубик Рубика, но вы давно его не брали в руки, не торопитесь вращать грани в соответствии с этими формулами и любоваться "картинками". Подумайте сначала, сумеете ли вы потом вернуть кубик в исходное состояние? Это не так сложно, как может показаться на первый взгляд. Сообразили, как это сделать? Если еще нет, то вспомните, каким образом Тесей сумел выйти из лабиринта Минотавра.

Рисунок 3.

Третий рисунок может вообще показаться совершенно беспорядочным, но на самом деле это не так. Присмотритесь внимательно: на каждой из шести граней один и тот же узор, правда, нарисованный разными цветами. Чем же замечателен именно этот узор? Скорее всего, почти ничем. Но одна особенность у него все-таки есть. Это один из очень немногих рекордных узоров, с которыми Cube Explorer справляется только за 24 хода и никак не быстрее (R U D2 R' B D' L' F' R F2 U B U' L2 U' L2 B2 L2 U' B2 R2 U B2 U2). Разумеется, это не означает, что к данному узору нельзя прийти за меньшее число ходов - просто алгоритм, заложенный в программе, тоже несовершенен. Полный же перебор всех вариантов состояний кубика Рубика сегодня не под силу не только персоналкам, но и мощным рабочим станциям. Даже если ограничиться только "легальными" состояниями, то есть теми, которые можно получить, не ломая механическую головоломку и не переклеивая на ней цветные наклейки, все равно число состояний кубика имеет тот же порядок, что и ответ в знаменитой древней задаче о награждении изобретателя шахматной игры. Помните эту историю? "На первую клетку, о господин, положи мне одно зернышко пшеницы, на вторую - два зернышка, и так далее, на каждую следующую клади вдвое больше, чем на предыдущую". При таких скромных запросах изобретателя на доске оказывается ни много ни мало, 264-1 зерен пшеницы - намного больше, чем может взрастить вся наша планета за один год.

Впрочем, компьютерная техника вот уже тридцать лет развивается по тому же закону. Скорость вычислений, объем хранимых данных, количество выпущенных компьютеров - все это растет в геометрической прогрессии. И, значит, недалек тот день, когда перебор вариантов порядка 1020 станет таким же обыденным делом, как сейчас - перебор десятков или сотен тысяч. Вот тогда все тайны кубика будут раскрыты полностью. А пока всех желающих приглашаю к открытию. Адрес программы Cube Explorer (текущая версия имеет номер 1.5, объем архива 140 килобайт) - http://home.t-online.de/home/kociemba/cube.htm. Успехов вам в кубоверчении!

Ну и последнее. В Интернете разбросано довольно много страниц, посвященных кубику Рубика и другим аналогичным головоломкам. Увы, среди них нет ни одной русской страницы. Может быть, среди моих читателей найдутся желающие исправить это досадное недоразумение? Пишите мне по адресу kk@knop.spb.ruНаписать комментарий (комментариев - нет)&n