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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

  begin
  | ...сделать X, P пустыми;
  | writeln (i);
  | ...добавить i к X, P;
  | {(1) P = множество напечатанных вершин; P содержит i;
  |  (2) напечатаны только доступные из i вершины;
  |  (3) X - подмножество P;
  |  (4) все напечатанные вершины, из которых выходит
  |      ребро в ненапечатанную вершину, принадлежат X}
  | while X непусто do begin
  | | ...взять какой-нибудь элемент X в v;
  | | for k := 1 to num [v] do begin
  | | | w := out [v][k];
  | | | if w не принадлежит P then begin
  | | | | writeln (w);
  | | | | добавить w в P;
  | | | | добавить w в X
  | | | end;
  | | end;
  | end;
  end;

     Свойство (1) не нарушается, так как печать  происходит  од-
новременно с добавлением в P. Свойства (2): раз v было в X, то v
доступно,  поэтому  w  доступно. Свойство (3) очевидно. Свойство
(4): мы удалили из X элемент v, но все вершины, куда из  v  идут
ребра, перед этим напечатаны.

     Оценка  времени  работы. Заметим, что изъятые из X элементы
больше туда не добавляются, так как они  в  момент  изъятия  (и,
следовательно, всегда позже) принадлежат P, а добавляются только
элементы  не  из P. Поэтому цикл while выполняется не более, чем
по разу, для всех  доступных  вершин,  а  цикл  for  выполняется
столько раз, сколько из вершины выходит ребер.
     Для  X  надо  использовать представление со стеком или оче-
редью (см. выше), для P - булевский массив.

     6.3.8. Решить предыдущую задачу, если требуется, чтобы дос-
тупные вершины печатались в таком порядке: сначала заданная вер-
шина, потом ее соседи, потом соседи соседей (еще  не  напечатан-
ные) и т.д.

     Указание. Так получится, если использовать очередь в приве-
денном выше решении: докажите индукцией по k, что существует мо-
мент, в который напечатаны все вершины на расстоянии  не  больше
k, а в очереди находятся все вершины, удаленные ровно на k.

Более  сложные  способы представления множеств будут разобраны в
главах 11 (Хеширование) и 12 (Деревья).

     6.4. Разные задачи.

     6.4.1. Реализовать структуру данных, которая имеет  все  те
же операции, что массив длины n, а именно

        начать работу
        положить в i-ю ячейку число n
        узнать, что лежит в i-ой ячейке

а также операцию "указать номер минимального элемента" (или  од-

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 Большая Одесская Библиотека.