Новая игра
Многие мальчики и девочки спрашивают в письмах Чипа: не знает ли он игры, в которую можно поиграть на самом простом калькуляторе?
Знает Чип такие игры. Вот одна из них:
«ЧИСЛОВЫЕ ПРЫГАЛКИ»
На калькуляторе набирают любое число меньше 100. Двое играющих «ходят» по очереди: если число четное, то его в один ход делят пополам. Если нечетное, то другой игрок, тоже за один ход, сначала число умножает на 3, а дальше по своему усмотрению или отнимает, или прибавляет единицу. Выигрывает тот, кто в ответе получает единицу.
Вот как протекала одна партия между Сережей и его подругой Аней.
Аня набрала на калькуляторе число 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°С и закипит. Ну, а из кипятка-то, я думаю, он и сам не заметит, как выпрыгнет!
— Здорово, — восхищенно протянул Сережа. — Слушай, а я как-то и не понимал, что компьютеры так быстро работают. В одну секунду: раз — буль-буль — и прыг! Готово дело!
— А ты заметил другое, что моя подпрограмма вызывает сама себя, как и Мюнхгаузен сам себя за волосы тащит? И не просто себя вызывает. Если бы она только себя вызывала и больше ничего не делала, то получился бы бесконечный цикл, как в стишке про попа и собаку. Но она при каждом вызове чуть нагревает лужу, так что рано или поздно лужа испарится и цикл закончится.
Такие подпрограммы называются рекурсивными, их всегда трудно понять. Кажется, что они не смогут работать, как Мюнхгаузен не сможет вытянуть себя из лужи. Для того, чтобы рекурсивная подпрограмма работала, надо, чтобы при каждом вызове что-то изменялось так, чтобы работа могла кончиться.
— А можешь еще рекурсивную программу написать? Мне очень понравилось.
— Ну что ж, например, ваш класс на физкультуре неправильно выстроился по росту: впереди самый маленький, в затылок ему смотрит мальчик повыше, а сзади самый большой. Вот такая рекурсивная программа перестраивает их в обратном порядке.
Программа «ПЕРЕСТРОЙ» (колонну).
Если в колонне один человек, то возврат.
ПЕРВЫЙ ДЕЛАЕТ ШАГ ВБОК.
«ПЕРЕСТРОЙ» (остаток колонны).
ПЕРВЫЙ ИДЕТ НАЗАД.
Возврат.