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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

ло таких последовательностей.
     Разобьем  множество  таких  последовательностей на классы в
зависимости от разницы между первой и  последней  цифрами.  Если
эта разница равна t, то разница между суммами групп из оставших-
ся  n-1 цифр равна k-t. Учитывая, что пар цифр с разностью t бы-
вает 10 - (модуль t), получаем формулу
   T(n,k) = сумма по t от -9 до 9 чисел (10-|t|) * T(n-1,  k-t).
(Некоторые слагаемые могут отсутствовать, так как k-t может быть
слишком велико.)
      Глава 3. Обход дерева. Перебор с возвратами.

     3.1. Ферзи, не бьющие друг друга: обход дерева позиций

     В  предыдущей главе мы рассматривали несколько задач одного
и того же типа: "перечислить все элементы  некоторого  множества
A". Схема решения была такова: на множестве A вводился порядок и
описывалась  процедура  перехода  от произвольного элемента мно-
жества A к следующему за ним (в этом порядке).  Такую  схему  не
всегда  удается  реализовать  непосредственно, и в этой главе мы
рассмотрим другой полезный прием перечисления всех элементов не-
которого множества. Его называют "поиск  с  возвратами",  "метод
ветвей  и границ", "backtracking". На наш взгляд наиболее точное
название этого метода - обход дерева.

     3.1.1. Перечислить все способы расстановки n ферзей на шах-
матной доске n на n, при которых они не бьют друг друга.

     Решение. Очевидно, на каждой из n горизонталей должно  сто-
ять  по  ферзю.  Будем  называть k-позицией (для k = 0, 1,...,n)
произвольную расстановку k ферзей на k нижних горизонталях (фер-
зи могут бить друг друга). Нарисуем "дерево позиций": его корнем
будет единственная 0-позиция, а из каждой  k-позиции  выходит  n
стрелок  вверх в (k+1)-позиции. Эти n позиций отличаются положе-
нием ферзя на (k+1)-ой горизонтали. Будем считать, что  располо-
жение  их  на рисунке соответствует положению этого ферзя: левее
та позиция, в которой ферзь расположен левее.

                                        Дерево позиций для
                                           n = 2








Среди позиций этого дерева нам надо отобрать те n-позиции, в ко-
торых ферзи не бьют друг друга. Программа будет "обходить  дере-
во" и искать их. Чтобы не делать лишней работы, заметим вот что:
если  в  какой-то  k-позиции  ферзи  бьют друг друга, то ставить
дальнейших ферзей смысла нет. Поэтому, обнаружив это,  мы  будем
прекращать построение дерева в этом направлении.

     Точнее,  назовем  k-позицию допустимой, если после удаления
верхнего ферзя оставшиеся не бьют друг друга. Наша программа бу-
дет рассматривать только допустимые позиции.




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