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