Программирование игр и головоломок - [60]

Головоломка 30.

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

100 i = 0; j := 0.
110 продвинуть i к ближайшему символу в цепочке a, не являющемуся пробелом
120 ЕСЛИ мы вышли из a ТО ПЕРЕЙТИ К 200 КОНЕЦ_ЕСЛИ
130 продвинуть j к ближайшему символу в цепочке b, не являющемуся пробелом
140 ЕСЛИ мы вышли из b ТО ПЕРЕЙТИ К 300 КОНЕЦ_ЕСЛИ
150 ЕСЛИ a[i] = b[j] ТО ПЕРЕЙТИ К 110
160 ПЕРЕЙТИ К 800
200 продвинуть j к ближайшему символу в цепочке b, не являющемуся пробелом
210 ЕСЛИ мы вышли из b ТО ПЕРЕЙТИ К 900 КОНЕЦ_ЕСЛИ
220 ПЕРЕЙТИ К 800
300 продвинуть i к ближайшему символу в цепочке а, не являющемуся пробелом
310 ЕСЛИ мы вышли из a ТО ПЕРЕЙТИ К 900 КОНЕЦ_ЕСЛИ
800 результат := ЛОЖЬ; ПЕРЕЙТИ К 1000
900 результат := ИСТИНА

Эта программа понятна. В 150 находим два символа, не являющихся пробелами. Если они совпадают, то нужно продолжать маршрут, а если они различны, то и цепочки различны (строчка 800).

Если в 120 констатируется, что все символы цепочки а уже испытаны, причем каких-либо различий с уже изученными символами цепочки b но обнаружено, то имеется выбор одной из двух возможностей (строки 200 и 210):

— либо в цепочке b нет ни одного символа, не являющегося пробелом (что приводит к тому, что в поисках такого символа мы выходим из b), и цепочки совпадают (строчка 900), либо мы обнаруживаем в цепочке b символ, не являющийся пробелом; эта цепочка включает символы, не входящие в a, и, следовательно, результат есть ЛОЖЬ (строка 800).

То же самое происходит, когда исчерпывается цепочка b (из строчки 140 переход осуществляется к строчке 300).

Я попытаюсь сделать из этого головоломку. Еще не слишком поздно. Найдите ошибку и исправьте ее. Но вы можете составить намного лучшую программу.

Головоломка 31.

Вот несколько идей. Вы можете сначала «отсортировать» обе цепочки, переставляя символы в каждой из них, чтобы они оказались, например, в алфавитном порядке. Когда это сделано, то цепочки должны оказаться одинаковыми, Это очень тяжеловесно…

Вы можете взять первый символ первой цепочки и посмотреть, есть ли он во второй цепочке. Если ответ отрицателен, то цепочки не являются анаграммами друг друга. Если же ответ — «да», то изымите этот символ из второй цепочки и переходите ко второму символу в цепочке a. Это ведет, по вашему выбору, к рекурсивной или к итеративной процедуре, Внимание: если вы смогли полностью пробежать a и не нашли ни одного символа, не попавшего в b, проверьте, не осталось ли чего-нибудь в b…

Вы можете задать таблицу, имеющую столько же полей, сколько может быть различных символов в рассматриваемых цепочках. Если мы имеем дело с текстами и если пробелы считаются, то нужны 33 буквы и пустое место… Вы пробегаете первую цепочку и добавляете 1 в клетке, связанной с каждым встречаемым характером (вы считаете число случаев появления каждого знака), Затем вы пробегаете вторую цепочку и все пересчитываете (вычитая, а не складывая). Если в конце вы получаете таблицу, содержащую что-то кроме нулей, то цепочки не являются анаграммами.

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

Головоломка 32.

То что было только что сказано, остается приемлемым и в этой задаче. Но достоинства различных решений могут измениться. Продумайте их. Это Позволит увидеть, что одна программа никогда не бывает абсолютно лучше другой, Это зависит от данных и часто еще и от используемого компьютера…

Головоломка 33.

Есть карточный пасьянс, который более иди менее похож на эту задачу. Выберем из вектора его первый элемент и отложим его в сторону на запасное поле, Мы можем поместить на его место элемент m + 1, который и должен перейти на поле 1. Теперь поле m + 1 свободно. Туда можно перенести элемент, который должен его заполнить. Возьмем конкретный пример: n = 10 и m = 4. Элементы верхней части спускаются на 4 поля, а те, которые находятся в нижней части, поднимаются на 6 полей. Вот последовательные состояния вектора. Я не представляю здесь запасное поле, которое содержит элемент 1. Я помещаю в эти поля именно номера элементов в исходной конфигурации:

исходное положение:

1 2 3 4 5 6 7 8 9 10
  2 3 4 5 6 7 8 9 10
5 2 3 4   6 7 8 9 10
5 2 3 4 9 6 7 8   10
5 2   4 9 6 7 8 3 10
5 2 7 4 9 6   8 3 10

А теперь именно элемент 1 должен прийти на свободное поле, и этот цикл останавливается. Мы убеждаемся, что не все элементы перенесены. Все числа на нечетных местах уже находятся там, где должны находиться, а числа на четных местах не стронуты с мест. Но можно начать новый цикл той же длины, поместив 2 на запасное поле, — это завершит работу.

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