Программирование игр и головоломок
Шрифт:
Если у вас есть предубеждения против рекурсии, то сейчас подходящий момент избавиться от них. И бросьте думать, что рекурсия всегда дорого обходится. Она всегда сокращает время программирования. Неверно, что она всегда приводит к более медленному вычислению (эта головоломка и есть пример). Я соглашусь с вами, что она всегда занимает немного больше места…
Эта процедура, действуя на 6 шашек
100 75 50 25 10 10,
быстро находит число 370, но терпит неудачу для 369.
7. Обо всем понемногу
Головоломка 29.
Эта задача также не должна была бы излагаться ошибающимися людьми. Я пытался понять, где эти программисты оступаются. Я считаю, что есть две опасности:
— прежде всего нет никакой уверенности в том, что поступающее
— далее поиск должен происходить с помощью разделения каждый раз таблицы на две части. Сравниваем x со средним элементом. Если он больше, то нужно искать его место в верхней полутаблице. В противном случае он — в нижней половине. Но средний элемент — это элемент с индексом k = (1 + n)/2 или, в наиболее общем случае, где рассматривается кусок таблицы, начинающийся в p и кончающийся в q, — элемент с индексом (p + q)/2. Конечно, рассматривается только целая часть дроби. По этой причине некоторые программисты опасаются, что это может заставить обращаться много раз к одному и тому же элементу, и тогда программа не остановится или может вызвать потерю элемента.
Это — пустые опасения. Возьмем как общую следующую ситуацию: пусть мы смогли найти такие два целых p и q, что
a[p] < x <= a[q], причем p < q.
Тогда все очевидным образом завершено, если q = p + 1.
В противном случае скачок между q и p не меньше 2, и так как p меньше q, то, следовательно, элемент с промежуточным номером
r = целая_часть ((p + q)/2)
обязательно отличается от элементов с номерами p и q, и вам нечего опасаться. Вы сравниваете x с элементом с индексом r и в зависимости от результата сравнения берете r либо как новую нижнюю границу p, либо новую верхнюю границу q.
Остается одна трудность. Как выбрать p и q, чтобы так пустить в ход процесс, чтобы выполнялось общее двойное неравенство? Всегда, когда приходится выполнять обращение к таблице, представляет интерес введение дополнительных элементов, освобождающих от влияния концов таблицы. Введем элемент с индексом 0, меньший, чем любой из тех x, к которым можно обратиться (мы отложим на более поздний срок решение вопроса, как мы можем сделать это эффективно), и элемент с номером n + 1, больший, чем все возможные x. Тогда x обязательно больше, чем a[0], и меньше, чем a[n + 1].
Тогда мы можем начать с p = 0 и q = n + 1. Напишите соответствующую программу, вовсе не заботясь заранее о значениях a[0] и a[n + 1] и оставляя в неопределенном положении задачу эффективного описания таблицы (некоторые языки, такие как Фортран или LSE, не допускают индекса ноль —
один только бог знает почему…). Покажите, что единственный индекс, для которого фактически приходится читать значение элемента таблицы, — это индекс r. Так как r всегда строго содержится в интервале (p, q), причем p не убывает, a q не возрастает, то r всегда строго больше 0 и не меньше n. Таким образом, элементы 0 и n + 1 никогда не опрашиваются. Поэтому и нет необходимости их материализовывать. Объявите массив (таблицу) с индексом, пробегающим от 1 до n, и все пройдет без сучка и задоринки…Головоломка 30.
Это — задача, на которой я заваливаю профессионалов. Совершенно очевидно, что обе цепочки символов играют одну и ту же роль. Следовательно, в программе есть симметрия, которая касается способа обращения с этими цепочками. Вот — более или менее символически — программа, которую пишут профессионалы:
Эта программа понятна. В 150 находим два символа, не являющихся пробелами. Если они совпадают, то нужно продолжать маршрут, а если они различны, то и цепочки различны (строчка 800).
Если в 120 констатируется, что все символы цепочки а уже испытаны, причем каких-либо различий с уже изученными символами цепочки b но обнаружено, то имеется выбор одной из двух возможностей (строки 200 и 210):
— либо в цепочке b нет ни одного символа, не являющегося пробелом (что приводит к тому, что в поисках такого символа мы выходим из b), и цепочки совпадают (строчка 900), либо мы обнаруживаем в цепочке b символ, не являющийся пробелом; эта цепочка включает символы, не входящие в a, и, следовательно, результат есть ЛОЖЬ (строка 800).
То же самое происходит, когда исчерпывается цепочка b (из строчки 140 переход осуществляется к строчке 300).
Я попытаюсь сделать из этого головоломку. Еще не слишком поздно. Найдите ошибку и исправьте ее. Но вы можете составить намного лучшую программу.
Головоломка 31.
Вот несколько идей. Вы можете сначала «отсортировать» обе цепочки, переставляя символы в каждой из них, чтобы они оказались, например, в алфавитном порядке. Когда это сделано, то цепочки должны оказаться одинаковыми, Это очень тяжеловесно…