► 15. [29] Создайте программу на языке MIXAL, которая реализует алгоритм S. Предположите, что поле VAL Содержит числа с плавающей запятой и для работы с ними в компьютере MIX предусмотрено несколько команд: FADD, FSUB, FMUL и FDIV. Для простоты положим, что результатом койанды сложения FADD и вычитания FSUB будет нуль, если при сложении или вычитании операндов будут утрачены старшие разряды. Поэтому на шаге S7 можно применить условие "VAL(Pl) = О". При работе операторов для чисел с плавающей запятой регистр г А используется, а регистр гХ - нет.

16. [25] Создайте алгоритм копирования разреженной матрицы. (Иначе говоря, напишите алгоритм получения в памяти двух различных представлений матрицы, которые имеют показанную на рис. 14 форму, при условии, что сначала задано только одно такое представление.)

17. [26] Создайте алгоритм умножения двух разреженных матриц А и В с образованием новой матрицы С, в которой C[i,j] = kli ,к}Ъ[.к .j}. Причем обе исходные матрицы и результирующая матрица должны иметь представленную на рис. 14 форму.

18. [22] Следующий алгоритм позволяет заменить исходную матрицу A[i,j], где 1 < i,j обратной ей матрицей.

i) Для к = 1,2,... ,п выполнить следующие действия: просмотреть строку к в столбцах, которые еще не использовались в качестве осевых столбцов, и найти наибольший по абсолютной величине элемент; установить С [fc] равным номеру столбца, в котором элемент был найден, и выполнить осевое преобразование, используя этот элемент как осевой. (Если все такие элементы равны нулю, то матрица является сингулярной и не имеет обратной.)

ii) Переставить строки и столбцы так, чтобы fc-я строка стала строкой C[fc], а столбец C[fc] стал fc-m.

Используя описанный выше алгоритм, найдите вручную обратную матрицу для матрицы

/1 2 3\

0 12. \0 О 1/

19. [31] Измените описанный в упр. 18 алгоритм так, чтобы для разреженной матрицы, подобной представленной на рис. 14, можно было получить обратную матрицу. Уделите особое внимание эффективности выполнения перестановок среди строк и среди столбцов на шаге (ii).

20. [20] Имеется трехдиагональная матрица [tridiagonal matrix), в которой элементы a,j не равны нулю только тогда, когда г - j < 1 для 1 <i,j <п. Покажите, что для нее существует такая функция размещения

LOC(A[I,J]) =oo-)-oiH-02J, 1I-J<1,

которая позволяет представить все ее ненулевые элементы в (Зп - 2) последовательно расположенных ячейках.

21. [20] Предложите функцию размещения для матрицы размера п х п, где п является переменной. Элементы матрицы A[I,J] для 1 < I, J < п должны занимать п последовательно расположенных ячеек независимо от величины п.

22. [М25] (Задача П. Чоула , 1961.) Найдите такой полином p(ii,..., ik), который принимает каждое неотрицательное целое значение в точности один раз при обходе индексов («1, ••.,«*) для всех fc-мерных неотрицательных целых векторов с учетом того, что из условия 11 Н-----h ifc < ji Н-----h jk следует p{i\,... ,ik) < p{ji,- ,3k)-

23. [23] Расширяемая матрица {extendible matrix) с исходными размерами 1x1 растет от размера т х п к размеру (m + l) х п или к размеру т х (п+1) за счет добавления

новой строки или нового столбца Найдите для нее простую функцию распределения, согласно которой элементы A£l,J] занимают тп последовательных ячеек, где О < I < m и О < J < га, причем при росте матрицы ее элементы не изменяют своего положения в памяти

► 24. [25] (Еще одна хитрость при работе с разреженными массивами ) Предположим, что существует некий неинициализированный массив огромного размера и необходимо обеспечить доступ к его немногим произвольным элементам При первой попытке доступа к элементу А[к] для него следует установить значение О, причем смысл данной уловки заключается в том, чтобы избежать инициализации нулями сразу всех элементов массива и исключить связанные с этим большие затраты времени Предложите надежный способ чтения и записи любых элементов к[к] для заданного к, ничего це зная о фактическом начальном содержимом памяти и выполняя лишь небольшое фиксированное количество операций доступа к этому массиву

2.3. ДЕРЕВЬЯ

Приступим теперь к изучению деревьев - наиболее важных нелинейных структур, которые встречаются при работе с компьютерными алгоритмами. Вообще говоря, древовидная структура задает для узлов отношение "ветвления", которое во многом напоминает строение обычного дерева.

Формально дерево {tree) определяется как конечное множество Т одного или более узлов со следующими свойствами:

a) существует один выделенный узел, а именно - корень {root) данного дерева Т;

b) остальные узлы (за исключением корня) распределены среди m > О непересекающихся множеств Ti,...,Tm, и каждое из этих множеств, в свою очередь, является деревом; деревья Ti,...,Tm называются поддеревьями {subtrees) данного корня.

Как видите, это определение является рекурсивным: дерево определено на основе понятия дерева. Однако никакого порочного круга определений здесь нет, так как состоящее из одного узла дерево содержит только корень, а все остальные деревья с п > 1 узлами определяются на основе деревьев с п узлами. Следовательно, это позволяет дать определение дерева с двумя, тремя и более узлами. Помимо рекурсивного способа определения, существует несколько нерекурсивных способов определения деревьев (например, см. упр. 10,12 и 14, а также раздел 2.3.4), но рекурсивное определение наиболее приемлемо, так как рекурсивность отражает неотъемлемое свойство всех древовидных структур. Рекурсивный характер деревьев можно наблюдать и в природе, например почки молодых деревьев растут и со временем превращаются в ветви (поддеревья), на которых снова появляются почки, которые также растут и со временем превращаются в ветви (поддеревья), и т. д. В упр. 3 методом индукции по числу узлов дерева доказано несколько вг1жных свойств деревьев на основе приведенного выше рекурсивного определения.

Из этого определения следует, что каждый узел дерева является корне.м некоторого поддерева данного дерева. Количество поддеревьев узла называется степенью {degree) этого узла. Узел со степенью нуль называется концевым узлом {terminal node) или листом {leaf). Неконцевой узел называется узлом ветвления {branch node). Уровень {level) узла по отношению к дереву Т определяется рекурсивно следующим образом. Уровень корня дерева Т равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева Т, содержащего данный узел.

Эти понятия иллюстрируются на рис. 15 на примере дерева с семью узлами. Узел А является корнем, который имеет два поддерева: {В} и {C,D,E,F,G}. Корнем дерева {C,D,E,F,G} является узел С. Уровень узла С равен 1 по отношению ко всему дереву. Он имеет три поддерева, {D}, {Е} и {F,G}, поэтому С имеет степень 3. Концевыми на рис. 15 являются узлы В, D, Е к G. Узел F - единственный узел со степенью 1, а узел G - единственный узел со степенью 3.

Если в п. (Ь) данного выше определения имеет значение относительный порядок поддеревьев Ti,... ,Тт, то дерево является упорядоченным {ordered tree). Если, в упорядоченном дереве m > 2, то имеет смысл назвать поддерево вторым поддеревом данного корня и т. д. Упорядоченные деревья иногда также называются плоскими деревьями (plane trees), поскольку при их упорядочении имеет значение