Методы программирования. Громов Ю.Ю - 137 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

137
Информация распределяется:
Файл 1 R
1
… R
4 000 000
.
Файл 2 R
4 000 001
… R
5 000 000
.
Файл 3 R
1
… R
4
000
000
; R
4
000
001
… R
5
000
000
.
и сливается ещё раз:
Файл 1 R
1
… R
4 000 000
.
Файл 2 R
4 000 001
… R
5 000 000
.
Файл 3 R
1
… R
5
000
000
.
В итоге имеем пять проходов. В общем случае эта процедура анало-
гична четырёхфайловому сбалансированному слиянию, но выполняется
распределение между любыми двумя слияниями, что приводит к удвоен-
ному числу проходов минус один проход.
§ 17
1. С помощью алгоритма R выбора с замещением (для Р = 4) уста-
новите образуемые в выходном файле отрезки, если во входном файле
находится последовательность из шестнадцати записей с ключами:
а) отрезок 1: 4, 25, 64, 69, 79, 87, 94; отрезок 2: 3, 13, 15, 16, 20, 30,
44, 72; отрезок 3: 9;
б) отрезок 1: 42, 74, 77, 88, 92, 94
1
, 94
2
, 96; отрезок 2: 40, 45, 55, 56;
отрезок 3: 5, 22, 36, 37;
в) отрезок 1: 3, 32, 34, 61, 64, 65, 73, 98; отрезок 2: 12, 21, 35, 38, 54,
69, 81, 82.
§ 18
1. Таблица пошагового преобразования фамилий Euler, Gauss,
Hilbert, Knuth, Lloyd и Lukasiewicz в соответствующие им коды методом
Soundex:
Шаг 1 Шаг 2 Шаг 3 Шаг 4
Euler Elr E46 E46 E460
Gauss Gss G22 G2 G200
Hilbert Hlbrt H4163 H4163 H416
Knuth Knt K53 K53 K530
Lloyd Lld L43 L3 L300
Lukasiewicz Lkscz L2222 L222 L222
2. Количество сравнений K = K
i
и количество сравнений i ≤ N, про-
изводимых алгоритмом S и алгоритмом Q, при поиске в последователь-
ности ключей 503, 87, 512, 61, 908, 170, 897, 275, 653, 426, 154, 509, 612,
677, 765, 703:

Страницы