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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



Этот день в истории
В 1681 году скончался(-лась) Педро Кальдерон


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

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

while змея включает не все ребра do begin
| if из головы выходит неиспользованное в змее ребро then begin
| | удлинить змею этим ребром
| end else begin
| | {хвост змеи в той же вершине, что и голова}
| | отрезать конец хвоста и добавить его к голове
| | {"змея откусывает конец хвоста"}
| end;
end;

     Докажем, что мы достигнем цели.

     1)  Идя по змее от хвоста к голове, мы входим в каждую вер-
шину столько же раз, сколько выходим. Так как  в  любую  вершину
входит столько же ребер, сколько выходит, то невозможность выйти
означает, что мы начали движение в этой же точке.
     2) Змея не укорачивается, поэтому либо она  охватывает  все
ребра,  либо, начиная с некоторого момента, будет иметь постоян-
ную длину. Во втором случае змея будет бесконечно "скользить  по
себе".  Это возможно, только если из всех вершин змеи не выходит
неиспользованных ребер. Из связности следует,  что  использованы
все ребра.

     Замечание  по  реализации на паскале. Вершинами графа будем
считать числа 1..n. Для каждой вершины  i  будем  хранить  число
Out[i]  выходящих  из  нее  ребер, а также номера Num[i][1],...,
Num[i][Out[i]] тех вершин, куда  эти  ребра  ведут.  В  процессе
построения  змеи  будет  выбирать  первое свободное ребро. Тогда
достаточно будет хранить для каждой вершины число  выходящих  из
нее  использованных  ребер  -  это  будут ребра, идущие в начале
списка.

     6.2.7. Доказать, что для всякого  n  существует  последова-
тельность  нулей  и  единиц  длины  (2 в степени n) со следующим
свойством: если "свернуть ее в кольцо" и рассмотреть  все  фраг-
менты  длины  n  (их число равно (2 в степени n)), то мы получим
все возможные последовательности нулей и единиц длины n. Постро-
ить алгоритм отыскания такой  последовательности,  требующий  не
более (C в степени n) действий для некоторой константы C.

     Указание. Рассмотрим граф, вершинами которого являются пос-
ледовательности  нулей  и единиц длины (n-1). Будем считать, что
из вершины x ведет ребро в вершину y, если x может быть началом,
а y - концом некоторой последовательности длины n. Тогда из каж-
дой вершины входит и выходит два ребра. Цикл, проходящий по всем
ребрам, и даст требуемую последовательность.

     6.2.8. Реализовать k очередей с ограниченной суммарной дли-
ной  n,  используя  память  порядка  n+k, причем каждая операция
(кроме начальной, делающей все очереди пустыми) должна требовать
ограниченного константой числа действий.

     Решение.  Действуем аналогично ссылочной реализации стеков:
мы помним (для каждой очереди) первого, каждый член очереди пом-
нит следующего за ним (для последнего считается, что за ним сто-
ит фиктивный элемент с номером 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 : 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 Большая Одесская Библиотека.