так далее. Тогда можно за семь шагов найти друга даже в доме со 128 этажами.
— Молодец! — обрадовался Чип. — Вот ты сам придумал алгоритм двоичного поиска. А теперь попробуй написать программу. Давай воспользуемся командой:
ПОВТОРЯЙ, ПОКА ВЕРНО УСЛОВИЕ ((БЛОК)) [7] .
Сережа поднатужился и начал писать, косясь при этом на дверь: вдруг войдет бабушка и задаст ему нагоняй за то, что он отлынивает от уборки?
Программа:
1. ВЕРХНИЙ ЭТАЖ = 128.
2. НИЖНИЙ ЭТАЖ = 0.
3. Читай из записной книжки номер квартиры друга.
4. Повторяй, пока ВЕРХНИЙ ЭТАЖ выше НИЖНЕГО.
((СРЕДНИЙ ЭТАЖ = (ВЕРХНИЙ + НИЖНИЙ) : 2.
если ДРУГ живет на СРЕДНЕМ этаже, то КОНЕЦ,
если ДРУГ живет выше СРЕДНЕГО, то НИЖНИЙ этаж приравниваем к СРЕДНЕМУ,
иначе ВЕРХНИЙ приравниваем к СРЕДНЕМУ.))
— Ишь ты, ни одной ошибки, — сказал Чип, заглянув в листок, — не зря ты учишься в кружке программистов.
— Только какое это имеет отношение к уборке? — отложив ручку, спросил Сережа.
— Самое прямое! — успокоил его Чип. — Давай разберем еще одну задачку. Ты читал сказку Шарля Перро «Золушка»?
— Спрашиваешь!
— Тогда ты, конечно, помнишь, что принц приказал мерить туфельку всем девушкам королевства. Сначала принцессам, потом герцогиням, потом придворным дамам... А теперь посчитаем. Во Франции порядка миллиона девушек нужного возраста. Если каждая будет мерить туфельку хотя бы в течение минуты, то вся процедура примерки займет около трех лет, и это при условии, что принц будет работать не покладая рук день и ночь. Только сказочная любовь может выдержать подобное испытание. А теперь предположим, что мы с тобой советники короля. Если бы девушек можно было построить, но не по росту, а по размеру ноги, что бы ты предложил принцу?
— Я предложил бы ему объявить по радио, чтобы все девушки измерили свои ноги с точностью до миллиметра и позвонили бы во дворец...
— Это нечестно. Ты же знаешь, что в те сказочные времена не было ни радио, ни телефонов и даже портновский сантиметр был редкостью. Нет, единственный выход - мерить туфельку на ногу.
— Да ведь это та же самая задача! — воскликнул Сережа, немного подумав.
— Я бы...
— Тсс! Пусть лучше ребята пришлют нам программу поиска Золушки. Я думаю, что без нашей помощи принц ее просто не найдет, и сказка кончится плохо!
— Ну, хорошо, а как же построить девушек по размеру туфельки?
— Это могут сделать придворные дамы. Представь, что мы уже построили девушек, и тут пришла еще одна. Тогда нам надо найти двух девушек, стоящих одна за другой, чтобы у одной из них размер ноги был меньше, чем у новенькой, а у другой — больше. Ты понимаешь, как эта задача связана с двумя предыдущими?
— Конечно, нужно только изменить программу. Но ведь придворных дам много. Нельзя ли эту задачу как-нибудь распараллелить?
— Молодец! Не думал я, что ты догадаешься. Но пусть ребята поломают над этой задачей головы сами, а я дам только легкий намек. Предположим, что мы разделили девушек на 2 группы и каждую из них построили. Если ты, используя предыдущие задачи, придумаешь, как соединить эти два строя, ты найдешь самый быстрый метод сортировки, который называется метод «вставок-слияний». А тогда ты не только поможешь королевской женитьбе, но и быстро справишься с генеральной уборкой.
Бурная жизнь Фатландии
— Чип, давай во что-нибудь поиграем. — предложил Сережа своему другу, — только на этот раз давай играть по-честному)
— А я всегда играю честно! — возмутился Чип. — Жульничать умеет только очень большой компьютер, да и то с помощью программы искусственного интеллекта. А нам, маленьким машинкам, это просто не по силам.
— Ты только не обижайся, пожалуйста, — спохватился Сережа, — я просто имел в виду такую игру, где шансы у противников одинаковые. Помнишь, как мы с тобой играли в спички? Если один из игроков умеет пользоваться числами Фибоначчи, то он всегда выигрывает. И как только секрет разгадан, играть становится неинтересно.
— Понимаю, ты хочешь, чтобы я показал тебе игру без выигрышной стратегии?
— Да. что-нибудь вроде шахмат, шашек или крестиков-ноликов на бесконечном поле, только новенькое.
— Ну, для крестиков-ноликов выигрышная стратегия есть, при правильной игре всегда побеждает крестик. Только алгоритм не такой простой, как в игре со спичками или в игре «орел-решка». Он придуман в Японии, занимает три увесистых тома и состоит в переборе большого числа позиций. Это больше похоже на математическое доказательство, а не на руководство к действию.
— А что за выигрышный алгоритм в игре «орел-решка»?
— Очень простой: не играть вообще.
— Чип, а есть машины, которые умеют играть в крестики-нолики по выигрышному алгоритму?
— Не знаю, но если у какого-нибудь трудолюбивого японца и хватит терпения запихнуть этот многотомный труд в программу, с таким компьютером никто не станет играть. Интересно иметь дело с противником, который играет немного лучше или немного хуже тебя, пускается в авантюры, выдает красивые идеи и вообще думает как-то по-человечески...
— Ну вот, Чип, опять ты сказки рассказываешь! Разве может машина придумать что-нибудь сама? Она знает только то, что есть в программе.
— Не совсем так. Например, для шашек уже существует программа, думающая, «как человек». Ее идея в том, чтобы компьютер все время учился: после каждого хода сравнивал результаты своих прошлых прогнозов с тем, что на самом деле происходит, и в следующий раз делал более точные прогнозы. Такие прогнозы заменяют ему перебор ходов: он посмотрит несколько ходов вперед, а дальнейшие варианты предугадывает. После каждого хода он прогнозирует все лучше и лучше. Ему ничего не стоит хранить в памяти все сыгранные партии и извлекать из них уроки.
— А как он это делает? Ведь алгоритм прогноза надо было написать заранее?
— Что-то, конечно, надо было написать заранее, в этом и состоит искусство программиста, но можно сделать так, чтобы программа сама себя исправляла.
— Ладно, хватит, Чип, я устал от разговоров. Давай все-таки поиграем.
