Игры с Чипом

Вот как протекала одна партия между Сережей и его подругой Аней.

Аня набрала на калькуляторе число 5.

Сережа: 5x3-1=14.

Аня: 14:2=7.

Сережа: 7x3-1=20

Аня: 20:2=10.

Сережа: 10:2=5.

Аня: 5x3+1=16.

Сережа: 16:2=8.

Аня: 8:2=4.

Сережа: 4:2=2.

Аня: 2:2=1.

Сережа проиграл, ему осталась единица.

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

Аня: 5+7+10+16+...=43.

Сережа: 14+20+5+8+...=49.

А так счет 43:49 в пользу Сережи.

ОТ РЕДАКЦИИ:

Ребята, Чип дает вам задание: подумать, какие ходы могут привести вас к победе. Подсказываем, у каждого варианта игры — свои секреты. Кто догадается, напишите нам.

Барон Мюнхгаузен и урок физкультуры

— Ты над чем так смеешься? — спросил Чип. Сережа зачитывался «Бароном Мюнхгаузеном», а Чип прогуливался по столу, поглядывая по сторонам. Работы для него не было, и он томился от безделья.

— Да вот, представляешь, барон Мюнхгаузен сам себя из лужи вытянул! За волосы!

— И что же тут смешного? По-моему, ничего особенного.

— Уж будто твои программы могут сами себя за волосы тащить!

— А что! — азартно крикнул Чип. — Вот спорим, что я напишу программу, которая сама себя из лужи вытаскивает? Спорим?

— Ну, спорим, — усмехнулся Сережа.

— Это будет программа

«МЮНХГАУЗЕН».

«ЕСЛИ МЮНХГАУЗЕН В ЛУЖЕ, ТО ОН ДОЛЖЕН ТЯНУТЬ СЕБЯ ЗА ВОЛОСЫ».

А «ТЯНУТЬ СЕБЯ ЗА ВОЛОСЫ» — это подпрограмма.

Подпрограмма «ТЯНУТЬ СЕБЯ ЗА ВОЛОСЫ»:

«НАГРЕТЬ СВОИМИ ДВИЖЕНИЯМИ ЛУЖУ НА ОДНУ ТЫСЯЧНУЮ ГРАДУСА. ЕСЛИ ЛУЖА НЕ ВЫСОХЛА, СНОВА ТЯНУТЬ СЕБЯ ЗА ВОЛОСЫ».

Конец подпрограммы.

— Ну, а как же эта подпрограмма поможет Мюнхгаузену вылезти из лужи? — спросил Сережа с подозрением.

— А вот как: Мюнхгаузен первый раз потянет себя за волосы и нагреет своими движениями лужу на одну тысячную часть градуса. Потом, если лужа не высохла (а она, конечно, и не подумала высохнуть, хоть чуть-чуть и нагрелась), он снова потянет и нагреет лужу еще на одну тысячную часть градуса и так далее. Если у Мюнхгаузена скорость работы, как у рядового компьютера, то не пройдет и секунды, как вода в луже поднимается до 100°С и закипит. Ну, а из кипятка-то, я думаю, он и сам не заметит, как выпрыгнет!

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

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

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

— А можешь еще рекурсивную программу написать? Мне очень понравилось.

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

Программа «ПЕРЕСТРОЙ» (колонну).

Если в колонне один человек, то возврат.

ПЕРВЫЙ ДЕЛАЕТ ШАГ ВБОК.

«ПЕРЕСТРОЙ» (остаток колонны).

ПЕРВЫЙ ИДЕТ НАЗАД.

Возврат.

— Постой, постой, дай я соображу, как она будет работать. Если в колонне всего один человек, то его нечего перестраивать. Правильно, тут и написано «возврат». А куда возврат? Ладно, пока это неважно, а там посмотрим.

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

— Ну, сам подумай, что ты должен сейчас делать? Вспомни, что ты делал до того, как прочел таинственное слово «возврат», и... возвращайся к этому делу.

— Как что делал? Я перестраивал колонну из двух человек. У меня первый сбоку стоит и ждет.