Чтение онлайн

на главную - закладки

Жанры

Шрифт:

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

Стаканчики профессора Квиббла

Как-то раз продавец прохладительных напитков Барни предложил двум покупателям следующую задачку.

Барни.

Перед вами 10 бумажных стаканчиков, расставленных в ряд. В первые 5 стаканчиков я наливаю кинки-колу, остальные 5 стаканчиков остаются пустыми. Можно ли переставить 4 стаканчика так, чтобы пустые и полные стаканчики чередовались?

Барни. Правильно! Стоит лишь переставить второй стаканчик с седьмым, а четвертый с девятым, как задача будет решена.

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

Проф. Квиббл. Переставлять 4 стаканчика совсем не обязательно. Я берусь решить задачу, переставив лишь 2 стаканчика. Как, по-вашему, это возможно?

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

Глубокая мысль

Хотя предложенное профессором Квибблом шуточное решение основано на неоднозначном толковании слова «переставить» (означающего не только «поменять местами», как полагал Барни, но и «поставить по-другому», чем и воспользовался профессор Квиббл), исходная задача не столь тривиальна, как может показаться. Рассмотрим, например, аналогичную задачу для случая, когда из 200 стаканчиков, выстроенных в ряд, в первые 100 налита кинки-кола, а 100 остальных оставлены пустыми. Сколько пар стаканчиков следует поменять местами, чтобы пустые и полные стаканчики чередовались?

Поскольку следить за 200 стаканчиками довольно трудно, разберем сначала ту же задачу при меньших значениях n, где nчисло полных (или пустых) стаканчиков, и попытаемся подметить общую закономерность. Стаканчики можно «моделировать» фишками двух цветов, игральными картами, выложенными на столе рубашкой либо вверх, либо вниз, монетами и тому подобными предметами, наделенными каким-нибудь «двузначным» признаком. При n = 1 для решения задачи не требуется переставлять ни одной пары стаканчиков. При n = 2 решение очевидно и сводится к перестановке одной пары стаканчиков. Возможно, вы удивитесь, когда узнаете, что при n = 3 чередование пустых и полных стаканчиков достигается перестановкой одной пары стаканчиков. Еще немного усилий, и вам откроется довольно простая общая закономерность. При четном n для решения задачи требуется поменять местами n/2 пар, а при нечетном n соответственно (n– 1)/2 пар стаканчиков. Следовательно, если имеется 100 пустых и 100 полных стаканчиков, то задачу можно решить, переставив 50 пар стаканчиков.

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

Существует одна классическая головоломка, очень похожая на только что рассмотренную нами задачу, но несколько более трудную. Начнем с 2n предметов, выстроенных в ряд. Пусть по-прежнему n предметов, составляющих первую половину ряда, будут одного типа, а n предметов, составляющих вторую половину ряда, будут другого типа. (Как и прежде, их можно «моделировать» стаканчиками, фишками, игральными картами и т. п.) Требуется

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

Вот как это делается, например, при n = 3:

Как выглядит общее решение? При n = 1 решение тривиально. При n = 2 задача, как нетрудно выяснить, неразрешима. При всех n > 2 головоломка допускает решение не менее чем за n ходов.

Найти решение при n = 4 не так-то просто, и поиск его, несомненно, доставит вам немало удовольствия. Может быть, вам удастся сформулировать алгоритм решения головоломки за n ходов при любом n > 3.

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

1. Правила перемещения пар остаются теми же за одним исключением: если пара образована предметами различных типов, то перед тем, как пристроить ее к свободному концу, последовательность предметов в паре следует изменить. Например, перемещая две фишки, первая из которых (левая) красная, а вторая (правая) черная, их необходимо поменять местами, после чего первой станет черная, а второй красная фишка, и лишь после этого пристраивать к свободному концу. При 8 фишках существует решение в 5 ходов. При 10 фишках 5 ходов также оказывается достаточно. Общее решение неизвестно. Может быть, вам удастся найти его.

2. Правила такие же, как в исходной задаче, но фишек одного цвета на 1 меньше, чем другого, то есть фишек одного цвета n, а фишек другого n + 1. Доказано, что при любом n задачу можно решить за n^2 ходов, причем это число минимально.

3. Имеются фишки трех различных цветов. Пары соседних фишек перемещаются по обычному правилу с тем, чтобы фишки каждого цвета оказались выстроенными подряд. При n = 3 (всего 9 фишек) существует решение в 5 ходов. И в этом, и во всех предыдущих вариантах головоломки предполагается, что после последнего перестроения фишки стоят в ряд «сомкнутым строем» (без пробелов). Если ряд может содержать пробелы, то существует необычное решение всего лишь в 4 хода.

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

Что произойдет, если на первом ходу переместить фишку, на втором — 2 фишки, на третьем — 3 фишки и т. д.? Если в ряд выстроены n фишек одного цвета и затем п фишек другого цвета, то всегда ли правильного чередования цветов можно добиться за n ходов?

Дороги, которые мы выбираем

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

Станки. Эй, Сьюзен! Можно, я пойду с тобой?

Сьюзен. Нет, очень тебя прошу, уйди!

Сьюзен. Я придумала, что мне делать. Буду ходить в школу каждое утро другой дорогой. Тогда Станки ни за что не догадается, где меня можно подстеречь.

Поделиться:
Популярные книги

Предатель. Ты променял меня на бывшую

Верди Алиса
7. Измены
Любовные романы:
современные любовные романы
7.50
рейтинг книги
Предатель. Ты променял меня на бывшую

Барон переписывает правила

Ренгач Евгений
10. Закон сильного
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Барон переписывает правила

Призыватель нулевого ранга. Том 2

Дубов Дмитрий
2. Эпоха Гардара
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Призыватель нулевого ранга. Том 2

Последний реанорец. Том I и Том II

Павлов Вел
1. Высшая Речь
Фантастика:
фэнтези
7.62
рейтинг книги
Последний реанорец. Том I и Том II

Ваше Сиятельство

Моури Эрли
1. Ваше Сиятельство
Фантастика:
фэнтези
попаданцы
5.00
рейтинг книги
Ваше Сиятельство

Отмороженный

Гарцевич Евгений Александрович
1. Отмороженный
Фантастика:
боевая фантастика
рпг
5.00
рейтинг книги
Отмороженный

Я еще барон. Книга III

Дрейк Сириус
3. Дорогой барон!
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Я еще барон. Книга III

Темный Лекарь 13

Токсик Саша
13. Темный Лекарь
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Темный Лекарь 13

Хозяин Теней 4

Петров Максим Николаевич
4. Безбожник
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Хозяин Теней 4

Бастард Императора. Том 5

Орлов Андрей Юрьевич
5. Бастард Императора
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Бастард Императора. Том 5

На границе империй. Том 7. Часть 3

INDIGO
9. Фортуна дама переменчивая
Фантастика:
космическая фантастика
попаданцы
5.40
рейтинг книги
На границе империй. Том 7. Часть 3

Капитан космического флота

Борчанинов Геннадий
2. Звезды на погонах
Фантастика:
боевая фантастика
космическая фантастика
космоопера
рпг
5.00
рейтинг книги
Капитан космического флота

Темный Лекарь 7

Токсик Саша
7. Темный Лекарь
Фантастика:
попаданцы
аниме
фэнтези
5.75
рейтинг книги
Темный Лекарь 7

Камень. Книга вторая

Минин Станислав
2. Камень
Фантастика:
фэнтези
8.52
рейтинг книги
Камень. Книга вторая