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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

        | |  lastvert:= dest[vert[l]][edge[l]]; {последняя}
        | |  if lastvert напечатана then begin
        | |  | edge[l]:=edge[l]+1;
        | |  end else begin
        | |  | l:=l+1; vert[l]:=lastvert; edge[l]:=1;
        | |  end;
        | end;
        end;
        {путь сразу же ведет в пустоту, поэтому все вершины
         левее, то есть 1..n, напечатаны}

     9.2.4. Доказать, что если в графе нет циклов, то этот алго-
ритм заканчивает работу.

     Решение. Пусть это не так. Каждая вершина может  печататься
только  один раз, тако что с некоторого момента вершины не печа-
таются. В графе без циклов длина пути ограничена (вершина не мо-
жет входить дважды), поэтому подождав еще,  мы  можем  дождаться
момента,  после  которого  путь не удлиняется. После этого может
разве что увеличиваться edge[l] - но и это не беспредельно.
     Глава 10. Сопоставление с образцом.

     10.1. Простейший пример.

     10.1.1. Имеется последовательность символов x[1]..x[n]. Оп-
ределить, имеются ли в ней идущие друг за другом символы "abcd".
(Другими словами, требуется выяснить, есть ли в слове x[1]..x[n]
подслово "abcd".)

    Решение. Имеется примерно n (если быть точным, n-3) позиций,
на  которых  может находиться искомое подслово в исходном слове.
Для каждой из позиций можно проверить, действительно ли там  оно
находится, сравнив четыре символа. Однако есть более эффективный
способ. Читая слово x[1]..x[n] слева направо, мы ожидаем появле-
ния  буквы  'a'.  Как только она появилась, мы ждем за ней букву
'b', затем 'c', и, наконец, 'd'. Если наши ожидания оправдывают-
ся, то слово "abcd" обнаружено. Если же какая-то из нужных  букв
не  появляется, мы оказываемся у разбитого корыта и начинаем все
сначала.

     Этот простой алгоритм можно описать в разных терминах.  Ис-
пользуя  терминологию  так  называемых конечных автоматов, можно
сказать, что при чтении слова x слева направо мы в каждый момент
находимся в  одном  из  следующих  состояний:  "начальное"  (0),
"сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3)
и  "сразу после abcd" (4). Читая очередную букву, мы переходим в
следующее состояние по правилу

         Текущее         Очередная      Новое
         состояние       буква          состояние
          0                a             1
          0              кроме a         0
          1                b             2
          1                a             1
          1              кроме a,b       0
          2                c             3
          2                a             1
          2              кроме a,c       0
          3                d             4
          3                a             1

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