8.5. ЗАДАЧИ
1. В программе идентификации символов, приведенной в данной главе, предполагалось, что классы символов не пересекались. Как бы вы написали подпрограмму для проверки принадлежности в пересекающихся классах, таких как строчные буквы, прописные буквы, цифры и алфавитно-цифровые символы?
2. Напишите фрагмент программы, которая по заданному N (степени числа 2) устанавливает начальное значение в массиве CountTable [О ... N - 1], как это описано в данной главе.
3. Как себя "будут вести" различные алгоритмы двоичного поиска, если их применить (вопреки спецификации) к неупорядоченным массивам?
4. На заре программирования Ф. Брукс столкнулся с проблемой представления большой таблицы на компьютере с небольшим объемом памяти. Он не мог хранить всю таблицу, так как места хватало только на то, чтобы представить каждый элемент в виде нескольких битов (фактически на каждый элемент отводилась только одна десятичная цифра - я ведь сказал, что это было очень давно!). Альтернативный подход заключался в использовании численного анализа, чтобы подобрать функцию, соответствующую этой таблице. В результате значения функции были весьма близки к табличным (ни одно значение не отличалось более чем на пару единиц от истинного). На ее реализацию потребовался крайне малый объем памяти, но в силу реальных ограничений зта аппроксимация не оказалась достаточно хорошей. Как мог бы Брукс получить требуемую точность при ограниченной памяти?
5. Типичный пример последовательного поиска для определения того, есть ли элемент Т в массиве X [1 ... N], был приведен в задаче 9 гл. 4.
I := 1
while I <= M and ХСП ф Т do I := 1+1
При общепринятом способе оптимизации программы ее работу ускоряют, помещая элемент Т на "сторожевую позицию" в конец массива.
ХСМ+13 := Т
I :; 1
while ХСП Ф Т do I := 1+1
Исключение проверки I < N обычно уменьшает время работы программы на 20 - 30 %. Реализуйте эти две программы и измерьте время их работы в своей системе.
115
