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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

доказательства существования не дает требуемой оценки; ее прихо-
дится немного подправить.

     Решение. Наша программа будет  печатать  номера  вершин.  В
массиве  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 : 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 Большая Одесская Библиотека.