Пионер 1988-03, страница 65
— Ишь ты, ни одной ошибки,— сказал Чип, заглянув в листок,— не зря ты учишься в кружке программистов. — Только какое это имеет отношение к уборке?— отложив ручку, спросил Сережа. — Самое прямое!— успокоил его Чип.— Давай разберем еще одну задачку. Ты читал сказку Шарля Перро «Золушка»? — Спрашиваешь! — Тогда ты, конечно, помнишь, что принц приказал мерить туфельку всем девушкам королевства. Сначала принцессам, потом герцогиням, потом придворным дамам... А теперь посчитаем. Во Франции порядка миллиона девушек нужного возраста. Если каждая будет мерить туфельку хотя бы в течение минуты, то вся процедура примерки займет около трех лет. и это при условии, что принц будет работать не покладая рук день и ночь. Только сказочная любовь может выдержать подобное испытание. А теперь предположим, что мы с тобой советники короля. Если бы девушек можно было построить, но не по росту, а по размеру ноги, что бы ты предложил принцу? — Я предложил бы ему объявить по радио, чтобы все девушки измерили свои ноги с точностью до миллиметра и позвонили бы во дворец... — Это нечестно. Ты же знаешь, что в те сказочные времена не было ни радио, ни телефонов и даже портновский сантиметр был редкостью. Нет, единственный выход — мерить туфельку на ногу. — Да ведь это та же самая задача! — воскликнул Сережа, немного подумав. — Я бы... — Тсс! Пусть лучше ребята пришлют нам программу поиска Золушки. Я думаю, что без нашей помощи принц ее просто не найдет, и сказка кончится плохо! — Ну, хорошо, а как же построить девушек по размеру туфельки? — Это могут сделать придворные дамы. Представь, что мы уже построили девушек, и тут пришла еще одна. Тогда нам надо найти двух девушек, стоящих одна за другой, чтобы у одной из них размер ноги был меньше, чем у новенькой, а у другой — больше. Ты понимаешь, как эта задача связана с двумя предыдущими? — Конечно, нужно только изменить программу. Но ведь придворных дам много. Нельзя ли эту задачу как-нибудь распараллелить? — Молодец! Не думал я, что ты догадаешься. Но пусть ребята поломают над этой задачей головы сами, а я дам только легкий намек. Предположим, что мы разделили девушек на 2 группы и каждую из них построили. Если ты, используя предыдущие задачи, придумаешь, как соединить эти два строя, ты найдешь самый быстрый метод сортировки, который называется метод «вставок-слияний». А тогда ты не только поможешь королевской женитьбе, но и быстро справишься с генеральной уборкой. ОТ РЕДАКЦИИ. Ребята, поможем Сереже решить задачу Чипа? Пришлите нам свои программы, а на конверте напишите: «Где Золушка?» Лучшие программы мы напечатаем. ш о 0 Раздел ведут профессор А. МИГДАЛ и М. АГИШТЕИН. ANS 0 Н ш ® о м |
