Д. Кнут - Искусство программирования том 1 (1119450), страница 85
Текст из файла (страница 85)
2. [21] Формула (6) выведена ва основании предположения, что О < 1„< 4, для 1 < г < А Найдите общую формулу, в которой предполагается, что 1, < 1 < и„где 1, и и„— любые значения нижней и верхней границ данного измерения 3. [21] В этом разделе рассматривались нижние треугольные матрицы А[),13, где 0 < Й < ) < и. Как следует видоизменить приведенные рассуждения в случае, если отсчет индексов начинается с единицы, а ие с нуля и 1 < й < ) < и? 4. [22] Покажите, что при хранении верхней треугольной матрицы А[у. 13, где 0 < у < А < и, в лексикографическом порядке индексов распределение памяти будет удовлетворять условию (8). Найдите в таком случае формулу для 10С(А [),К)).
5. [20] Покажите, что значение А[Я,К3 можно занести в регистр А компьютера М1Х, выполнив одну команду и использовав инструменты косвенной адресации, которые описываются в упр. 2.2.2-3, даже если А является пгреугольиой матрицей типа (9). (Предполагается, что ) и К находятся в индексных регистрах.) 6. [М24] Рассмотрим "тетраэдрические массивыь А[г,),13, В[(,),13, где О < й < ) < ( < и в массиве А и 0 < г < ) < )г < и в массиве В. Предположим, что оба эти массива хранятся в последовательных адресах памяти в лексикографическом порядке индексов. Покажите, что 100(А[1,3,К)) = ао + У~ (1) + Уг()) ч- уг(К) для некоторых функций [и Уг, )з.
Можно ли получить аналогичное выражение для 1.0С(В П,у,К3)? 7. [А422] Найдите общую формулу распределения памяти для А-мерного тетраэдрического массива А[В,гг,...,(г), где 0 < гь « .. гг < ц < п. 8. [УУ] (Задача П. Вегнера .) Предположим, что в памяти необходимо разместить шесть тетрвэдрических массивов А[1,),К3, В[1,),К), С[1,),К3, О[1,) К3, Е[1.),К) и Р[1,).К), где О < К < Л < 1 < и.
Существует ли какой-нибудь эффективный способ выполнения этой задачи, аналогичный (10), но для двумерного случая? 9. [22] Рассмотрим таблицу такого же типа, как и таблица на рис. 13, но гораздо ббльшую, в которой все связи направлены в одну сторону (а именно — выполняется условие ЬХМК(Х) < Х для всех узлов и ссылок), Придумайте алгоритм для поиска адресов всех голубоглазых блондинок в возрасте от 21 до 23 лет, основанный на обходе различных полей связей, причем таким образом, что по завершении выполнения алгоритма для каждого из списков выполняется по крайней мере один обход каждого из списков РЕМАЕЕ, А21, А22, А23, ВХОМВ и В(ЛЕ.
10. [26] Можно ли придумать более совершенный способ организации таблицы с персональными данными, чтобы описанный в предыдущем примере поиск можно было выполнить более эффективным способом? (Простой ответ "Да" или "Нет'" в данном случае не годится,) 11. [11] Допустим, что в каждой строке матрицы размера 200 х 200 находится по крайней мере четыре ненулевых элемента Какой объем памяти потребуется для представления ее в виде, показанном на рис. 14, если для каждого узла используется по три слова, а для заголовков списков — по одному? э 12.
[20] Чему равны КА1(00), ЧАЕ(РО) и гАЕ(Р1) в начале шага 87, если их выразить с помощью переменных а, 6, с, 0 из (13)? э 13. [22] Почему в матрице на рис. 14 циклические списки используются вместо линейных списков? Можно ли изменить алгоритм Б так, чтобы в нем не использовалась циклическая связь? 14. [22] Алгоритм Я позволяет сэкономить время выполнения осевого преобразования разреженной матрицы, поскольку он предоставляет возможность пропускать столбцы, в которых значение элемента из осевой строки равно нулю Покажите, что такая зкономия может быть получена в большой разреженной матрице, которая хранится в последовательном порядке, за счет применения вспомогательной таблицы 11ИК [)3, 1 < ) < и.
ь 16. [20] Создайте программу на языке ИХХАА, которая реализует алгоритм Б. Предположите, что поле РАЕ содержит числа с плавающей запятой и для работы с ними в компьютере И1Х предусмотрено несколько команд; РАОО, РВОВ, РИШ. н РОХР. Для простоты положим, что результатом команды сложения РАОО и вычитания РВОВ будет нуль, если при сложении или вычитании операндов будут утрачены старшие разряды, Поэтому на шаге 87 можно применить условие куАЕ(Р1) = О".
При работе операторов для чисел с плавающей запятой регистр гА используется, а регистр гХ вЂ” нет. 16. [25] Создайте алгоритм кодирования разреженной матрицы. (Иначе говоря, напишите алгоритм получения в памяти двух различных представлений матрицы, которые имеют показанную на рис. 14 форму,прн условии, что сначала задано только одно такое представление.) 17. [25] Создайте алгоритм умножения двух разреженных матриц А и В с образованием новой матрицы С, в которой С[1,у3 = 2 А[1,238[1,33.
Причем обе исходные матрицы и результирующая матрица должны иметь представленную на рис. 14 форму. 18. [22] Следующий алгоритм позволяет заменить исходную матрицу А[г'.33, где 1 < г,) < и, обратной ей матрицей. 1) Для А = 1, 2,..., и выполнить следующие действия: просмотреть строку А в столбцах, которые еще не использовались в качестве осевых столбцов, и найти наибольший по абсолютной величине элемент; установить С [23 равным номеру столбца, в котором элемент был найден, и выполнить осевое преобразование, используя этот элемент как осевой.
(Если все такие элементы равны нулю, то матрица является сингулярной и не имеет обратной.) Й) Переставить строки и столбцы так, чтобы А-я строка стала строкой С [23, а столбец С[к) стал /с-ьь Используя описанный выше алгоритм, найдите вручную обратную матрицу для матрицы '[о ] г). 19. [21] Измените описанный в упр. 18 алгоритм так, чтобы для разреженной матрицы, подобной представленной на рис.
14, можно было получить обратную матрицу. Уделите особое внимание эффективности выполнения перестановок среди строк и среди столбцов на шаге (й). 2О. [20] Имеется тревдиагональная матрица (гггбгауопа1 тагггт), в которой элементы аи не равны нулю только тогда, когда ]и — )] < 1 для 1 < г,) < п. Покажите что для нее существует такая функция размещения ЬОС(А[1.13) = во+ аг1+ аз), [1 — Л] < 1, которая позволяет представить все ее ненулевые элементы в (Зп — 2) последовательно расположенных ячейках. 21. [20] Предложите функцию размещения для матрицы размера и х и, где и является переменной. Элементы матрицы А[1,13 для 1 < 1,1 < п должны занимать и последоваг тельно расположенных ячеек независимо от величины и. 22.
[М25] (Задача П. Чоула, 1961.) Найдите такой полинам р((м.,., 1г), .который принимает каждое неотрицательное целое значение в точности один раз прн обходе индексов (гм,1ь) для всех й-мерных неотрицательных целых векторов с учетом того, что из условия ц т +1ь < бг + +)г следует р(п,...,1г) < Р()г .,)г) 28.
[2Ю] Расширлемал матрица (ехгепйЫе та!ггт) с исходными размерами 1 х 1 растет от размера т х и к размеру (т + 1) х и или к размеру гп х (и+ 1) за счет добавления новой строки или нового столбца Найдите для нее простую функцию распределения, согласно которой элементы А~1,33 занимают гпп последовательных ячеек, где О < 1 < ш и О < Л < и, причем при росте матрицы ее элементы не изменяют своего положения в памяти я 24. ]25] (Еще одна хитпрость ири работе с равреясеиимми массивами ) Предположим, что существует некий неинициализированный массив огромного размера и необходимо обеспечить доступ к его немногим произвольным элементам При первой попытке доступа к элементу А]А] для него следует установить значение О, причем смысл данной уловки заключается в том, чтобы избежать инициализации нулями сразу всех элементов массива и исключить связанные с этим большие затраты времени Предложите надежный способ чтения и записи любых элементов А]А] для заданного й, ничего не зная о фактическом начальном содержимом памяти и выполняя лишь небольшое фиксированное количество операций доступа к этому массиву 2.3.
ДЕРЕВЬЯ Пгиступим ткпкгь к изучению деревьев — наиболее важных нелинейных структур, которые встречаются при работе с компьютерными алгоритмами. Вообще говоря, древовидная структура задает для узлов отношение "ветвления",которое во многом напоминает строение обычного дерева. Формально дерево (ггее) определяется как конечное множество Т одного или более узлов со следующими свойствами: а) существует один выделенный узел, а именно — корень (гоо1) данного дерева Т; Ь) остальные узлы (за исключением корня) распределены среди т > 0 непересекающихся множеств Ты...,Т„, и каждое из этих множеств, в свою очередь, являетгя деревом; деревья Т„...,Т называются поддерееья ии (эиЫгееэ) данного корня.
Как видите, это определение является рекурсивным: дерево определено на основе понятия дерева. Однако никакого порочного круга определений здесь нет, так как состоящее из одного узла дерево содержит только корень, а все остальные деревья с и > 1 узлами определяются на основе деревьев с и узлами. Следовательно, это позволяет дать определение дерева с двумя, тремя и более узлами.
Помимо рекурсивного способа определения, существует несколько нерекурснвных способов определения деревьев (например, см. упр. 10, 12 и 14, а также раздел 2.3.4), но рекурсивное определение наиболее приемлемо, так как рекурсивность отражает неотъемлемое свойство всех древовидных структур.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
