Главная Промышленная автоматика.

2.18. Напишите алгоритм порождения всех перестановок целых чисел от 1 до п. Указание: Множество перестановок целых чисел от 1 до п можно получить из множества перестановок целых чисел от 1 до п-1, вставляя п во все возможные позиции в каждой перестановке.

2.19. Напишите алгоритм нахождения высоты двоичного дерева, представленного на рис. 2.7, б.

2.20. Напишите алгоритм подсчета числа потомков каждого узла дерева.

**2.21. Рассмотрим двухпозиционный переключатель с двумя входами и двумя выходами, показанный на рис. 2.18. В одной позиции входы 1 и 2 соединяются соответственно с выходами 1 и 2, в другой - с выходами 2 и 1. Используя эти переключатели, разработайте сеть с п входами и п выходами, на которой можно получить любую из п1 возможных перестановок входов. В вашей сети должно быть не более О (л log п) переключателей. Указание: Примените прием "разделяй и властвуй".

2.22. Напишите РАСП-программу, которая выполняла бы работу следующей программы, вычисляющей :

procedure СОЧЕТ(л, т): if m=0 или пт then return 1 else return (СОЧЕТ(л-1, m)+C04ET(n-1, m-1)) В стеке можно хранить текущие значения л и т, а также адреса возврата и значения, когда происходят вызовы.

*2.23. В ряде ситуаций задачу размера п выгодно разбивать на Уп подзадач размера УИ. В результате получается рекуррентное уравнение вида

т{$-) = пТ{п)+Ьп\

где г - целое число, г1. Покажите, что решение этого рекуррентного уравнения есть O(n(log n)log log п).

Вход 1«----;0-ffi/xoff 1

Вход 2» и---:••-• Вше 2

---Соединения в \-й позиции

.......Соединения во 2-й позиции

Рис. 2.18. Двухпозиционный переключатель.



2.24. Вычислите значения сумм:

П R л

(а) Ц». (б) Ца. (в)

i=i г=1 (=1

(г) Ъ-ч\ (д) (е) t<r).

*2.25. Решите следующие рекуррентные уравнения, считая, что Г{1)=1:

(а) Т {п)=аТ {п-1)+Ьп, (б) Т (п)=Т {п/2)+Ьп log га, (в) Г(га)=аГ(га-l)+fertS (г) Т (п)=аТ (п12)+Ьп.

*2,26. Модифицируйте алгоритм 2.3 для нахождения наибольшего и наименьшего элементов множества, разрешив рекурсии идти до уровня S=1. Какова асимптотическая скорость роста числа сравнений?

**2.27. Покажите, что для одновременного нахождения наибольшего и наименьшего элементов п-элементного множества необходимо и достаточно [Iji-2") сравнений.

*2.28. Модифицируйте алгоритм для умножения целых чисел с помощью разбиения каждого целого числа на (а) три и (б) четыре части. Какова сложность каждого из ваших алгоритмов?

*2.29. Пусть А - массив размера п, состоящий из положительных и отрицательных целых чисел, причем Л[11<;Л[2]<:. . .<ЛЫ]. Напишите алгоритм нахождения числа i, для которого A[i]=i (если такое / существует). Каков порядок времени работы вашего алгоритма? Докажите, что Oc(log п) - наилучший возможный порядок.

**2.30. Для п, не являющегося степенью числа 2, также можно получить из алгоритма 2.4 корректный алгоритм сортировки слиянием, если заменить оператор m ч-(*Ч-/-1)/2 на рис. 2.14 оператором tn L(+/V2J. Пусть Г (п) -число сравнений, требуемых для сортировки этим методом п элементов.

(а) Покажите, что

Г(1) = 0,

r(n) = r(Ln/2J) + r(rn/2-l)-fn-l.

(б) Покажите, что решением этого рекуррентного уравнения служит функция

Г(п)=п Г log n "1 -2 г log «т -I-1.



*2.31. Покажите, что решением рекуррентного уравнения Х(1) = 1.

п- 1

Х(п)== X(i)X{n--i) при п>1

i= 1

служит

X (rt) - это число способов правильной расстановки скобок в цепочке из п символов. Числа X (п) называются числами Каталана. Покажите, что Х(п)>2"-

2.32. Модифицируйте алгоритм 2.5 так, чтобы он выдавал порядок, в котором следует умножать матрицы, чтобы минимизировать число умножений их элементов.

2.33. Напишите эффективный алгоритм для определения порядка, в котором следует вычислять произведение матриц MiXMX X. . .хМ„, чтобы минимизировать число умножений элементов в случае, когда каждая матрица Mi имеет один из размеров 1x1, Ixd, dxl или dxd при некотором фиксированном d.

Определение. Бесконтекстной грамматикой G в нормальной форме Хомского называется четверка {N, S, Р, S), где (1) N - конечное множество нетерминальных символов, (2) S - конечное множество терминальных символов, (3) Р - конечное множество пар, называемых продукциями, вида АВС или Аа {А, В, С - символы из yv, а а - из S) и (4) S - выделенный символ из N. Мы будем писать аАу ау, если а, , у - цепочки, состоящие из терминальных и нетерминальных символов, и Л Р принадлежит Р. Языком L (G), порождаемым грамматикой G, называется множество {w\S w} цепочек терминальных символов, где г>* обозначает рефлексивное и транзитивное замыкание отношения

*2.34. Напишите алгоритм сложности 0{п), который определял бы принадлежность данной цепочки w=aia2. . .а„ языку L(G), где G={N, Ii, Р, S) - бесконтекстная грамматика в нормальной форме Хомского. Указание: Пусть mi}{A\A и А aaj+i. . .Uj}. Слово W принадлежит языку L (G) тогда и только тогда, когда S G gmi„. Для вычисления ти примените динамическое программирование.

*2.35. Пусть X и у - цепочки символов и некоторого алфавита. Рассмотрите операции удаления символа изх, вставки символа в х и замены символа в х другим символом. Опишите алгоритм нахождения минимального числа таких операций, необходимых для преобразования X в у.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [26] 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021