Случайный афоризм
Улучшать нравы своего времени - вот цель, к которой должен стремиться каждый писатель, если он не хочет быть только "увеселителем публики". Оноре де Бальзак
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

то  заказ  на печатание корня можно не закладывать в стек, а вы-
полнять сразу.
     Несколько более сложная конструкция применима для порядка
        левое поддерево, корень, правое поддерево.
В этом случае все заказы в стеке, кроме самого первого  (напеча-
тать поддерево) делятся на пары:
    напечатать вершину x, напечатать правое поддерево x
(т.е.  поддерево с корнем в правом сыне x). Объединив эти пары в
заказы специального вида и введя переменную для отдельного  хра-
нения первого заказа, мы обойдемся стеком однотипных заказов.
     То же самое, разумеется, верно, если поменять местами левое
и правое - получается еще два порядка.

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

     8.2.7.  Написать  нерекурсивный  вариант  программы быстрой
сортировки. Как обойтись  стеком,  глубина  которого  ограничена
C*log n, где n - число сортируемых элементов?

     Решение.  В  стек кладутся пары , интерпретируемые как
отложенные задания на сортировку соответствующих участков масси-
ва. Все эти заказы не пересекаются, поэтому размер стека не  мо-
жет  превысить n. Чтобы ограничиться стеком логарифмической глу-
бины, будем придерживаться такого правила: глубже в  стек  поме-
щать больший из возникающих двух заказов. Пусть  f(n)  -  макси-
мальная  глубина стека, которая может встретиться при сортировке
массива из не более чем n элементов таким способом. Оценим  f(n)
сверху таким способом: после разбиения массива на два участка мы
сначала сортируем более короткий (храня в стеке про запас) более
длинный, при этом глубина стека не больше f(n/2)+1, затем сорти-
руем более длинный, так что

      f(n) <= max (f(n/2)+1, f(n-1)),

откуда очевидной индукцией получаем f(n) = O(log n).

     8.3. Более сложные случаи рекурсии.

     Пусть функция f с натуральными аргументами и значениями оп-
ределена рекурсивно условиями
        f(0) = a,
        f(x) = h(x, f(l(x))),
где a - некоторое число, а h и l -  известные  функции.  Другими
словами,  значение функции f в точке x выражается через значение
f в точке l(x). При этом предполагается, что для любого x в пос-
ледовательности
        x, l(x), l(l(x)),...
рано или поздно встретится 0.
     Если  дополнительно  известно,  что l(x) < x для всех x, то
вычисление f не представляет  труда:  вычисляем  последовательно
f(0), f(1), f(2),...

     8.3.1.  Написать  нерекурсивную  программу вычисления f для
общего случая.

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 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.