Cтраница 2
Затем третий по порядку элемент исходного списка сравнивается либо с первым, либо со вторым элементом; на этом совпадение дерева на рис. 2.2 с деревом на рис. 2.1 заканчивается. Внешние вершины усеченного дерева на рис. 2.2 представляют правильно упорядоченные последовательности элементов, обозначенных своими порядковыми номерами в исходном списке, получаемые после A ( k) парных сравнений. С увеличением числа ранжируемых элементов дерево быстро разрастается. На схеме все его элементы показаны только для k & 4, следующие уровни дерева представлены фрагментами. При некоторых значениях k несовпадающие последовательности парных сравнений могут приводить к одним и тем же наиболее благоприятным упорядочениям. Такой случай имеет место при k 5; в представленном на рис. 2.2 фрагменте из восьми упорядочений, каждое из которых получено при дЛ ( 5) 2, только пять различных. Повторяющиеся упорядочения этого фрагмента заштрихованы. [16]
Поэтапный процесс упорядочения элементов рассмотренного ранее исходного списка из девяти чисел при использовании алгоритма Штейнгауэа показан в табл. 2.3, которая совпадает с табл. 2.2 во всем, кроме числа необходимых парных сравнений. [17]
Наша программа быстрсорт в случае, когда исходный список уже упорядочен или почти упорядочен, работает очень неэффективно. Проанализируйте причины этого явления. [18]
Поначалу нет необходимости чрезмерно расширять и детализировать исходный список пользователей. Для описания ситуаций использования достаточно определить трех или четырех пользователей. Каждый из них по-разному взаимодействует с системой. Каждое взаимодействие должно быть учтено при определении ситуаций использования. [19]
Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. [20]
Такие условия имеют место, если а) исходный список имеет наиболее благоприятную структуру; б) при наличии двух медианных элементов делается всякий раз правильный вы -, когда это имеет значение. [21]
Число сравнений минимально, JV - 1, когда исходный список полностью упорядочен. Число сравнений максимально, когда список имеет обратный порядок. В этом случае каждое Из N - 1 первичных сравнений порождает вторичную последовательность, что увеличивает общее расстояние от точки первичного сравнения до вершины списка. Чтобы определить ожидаемое число сравнений, учтем, что средняя длина поиска любой позиции списка равна половине длины списка. Процесс просеивания аналогичен поиску в упорядоченном списке чисел нужной позиции для нового числа. [22]
Составление - словаря наименований понятий начинается с пословного кодирования исходного списка именных словосочетаний. Затем производится синтаксический анализ, в результате которого каждое наименование понятия представляется в виде сочетания номеров основ и сопровождается номером грамматической структуры. При этом в сочетании номеров основ на первом месте ставится номер главного слова наименования понятия, а в структурной формуле главному слову и определяющим его прилагательным назначается информация име - - нительный падеж единственного числа. Заключительным этапом составления словаря является сортировка кодов наименований понятий с исключением повторений одинаковых элементов. [23]
Список вывода имеет точно такой же размер, как у исходного списка, следовательно, может быть вычислен адрес позиции любого элемента в списке вывода. При размещении в списке вывода адрес ключа получается сложением значения счетчика этого ключа и начального адреса области вывода. Этот процесс занимает один просмотр сверху вниз списка значений счетчиков. [24]
В последней записи каждого нового списка помещают адрес очередного элемента исходного списка, указывая программе адрес продолжения поиска. [25]
ТУ при ранжировании девяти чисел, составляющих приведенный в предыдущих примерах исходный список. На первом этапе определяются более предпочтительные элементы каждой пары ( рис. 2.7 а); такими элементами являются числа 3 2 7 и 1, для их отыскания необходимо было выполнить четыре парных сравнения. Более предпочтительными из них являются элементы 2 и 1 ( см. рис., 2.7 6), для определения этих элементов потребовалось два парных сравнения. Теперь сравним эти элементы между собой и найдем элемент 1 более предпочтительным. [26]
Корневая вершина ( нулевой уровень) отображает сравнение первой пары элементов исходного списка. Первый уровень содержит две внешние вершины. Второй уровень содержит четыре внутренние вершины, так как третий по порядку элемент исходного списка можно сравнивать в соответствии с алгоритмом III как с первым элементом, полученной последовательности, так и со вторым. Дерево, отображающее проце - ДУРУ ранжирования трех элементов, показано на рис. 2.1. Двенадцать внешних вершин представляют получаемые последователъности из трех элементов, обозначенных своими порядковыми номерами в исходном списке. На третьем уровне представлены упорядочения, для получения которых достаточно выполнения двух парных сравнений; в каждом случае третье парное сравнение было бы избыточным в силу транзитивности бинарного отношения линейного строгого порядка. Вершины четвертого уровня представляют упорядочения, для получения каждого из которых необходимо выполнить три парных сравнения. Отметим, что каждое упорядочение встречается дважды. Для получения двух из них безразличен порядок выполнения двух последних парных сравнений - это последовательности 2 3, 1 и 1 3, 2, тогда как для остальных этот порядок имеет значение, поскольку эти последовательности могут быть получены в результате либо двух, либо трех парных сравнений. [27]
Описанные процедуры автоматического составления словаря наименований понятий основаны на серийной обработке всего исходного списка словосочетаний. Они неудобны для пополнения словарей и для внесения в них изменений. Более удобными в этом отношении являются ассоциативно-адресные методы, и в частности узловой способ, описанный в гл. Этот способ позволяет составлять словарь наименований понятий с нуля и вносить в него любые изменения. [28]
В общем случае цепочки записей связующих массивов, которые соединяют записи одного исходного списка, называются первичными. Следовательно, цепочка компонент СИ и цепочка прямого технологического маршрута - первичные. Кроме этих первичных цепочек, в связующих массивах организуются первичные цепочки в обратном направлении. Операции в ПТН связываются по убыванию последовательного номера. Такая цепочка называется обратным технологическим маршрутом. [29]
В действительности, для нашего конкретного списка из пяти равенств, которые составляют исходный список в рассмотренном выше примере, привести алгоритм, устанавливающий неравенство в случае, когда два слова и вправду неравны - не так уж сложно. [30]