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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

     Решение. Наша программа будет  печатать  номера  вершин.  В
массиве  printed: array[1..n] of boolean мы будем хранить сведе-
ния о том, какие вершины напечатаны (и корректировать их  однов-
ременно  с  печатью  вершины).  Будем говорить, что напечатанная
последовательность вершин корректна, если никакая вершина не на-
печатана дважды и для любого номера i, входящего в эту последос-
тельность,  все вершины, в которые ведут стрелки из i, напечата-
ны, и притом до i.

     procedure add (i: 1..n);
     | {дано: напечатанное корректно;}
     | {надо: напечатанное корректно и включает вершину i}
     begin
     | if printed [i] then begin {вершина i уже напечатана}
     | | {ничего делать не надо}
     | end else begin
     | | {напечатанное корректно}
     | | for j:=1 to num[i] do begin
     | | | add(adr[i][j]);
     | | end;
     | | {напечатанное корректно, все вершины, в которые из
     | |  i ведут стрелки, уже напечатаны - так что можно
     | |  печатать i, не нарушая корректности}
     | |  if not printed[i] then begin
     | |  | writeln(i); printed [i]:= TRUE;
     | |  end;
     | end;
     end;

Основная программа:

     for i:=1 to n do begin
     | printed[i]:= FALSE;
     end;
     for i:=1 to n do begin
     | add(i)
     end;

     7.4.3.  В  приведенной  программе можно выбросить проверку,
заменив
          if not printed[i] then begin
          | writeln(i); printed [i]:= TRUE;
          end;
на
          writeln(i); printed [i]:= TRUE;
Почему? Как изменится спецификация процедуры?

     Решение.  Спецификацию можно выбрать такой:
       дано: напеватанное корректно
       надо: напечатанное корректно и включает вершину i;
             все вновь напечатанные вершины доступны из i.

     7.4.4. Где использован тот факт, что граф не имеет циклов?

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