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

— далее поиск должен происходить с помощью разделения каждый раз таблицы на две части. Сравниваем 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.

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

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

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

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

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

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