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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

нисходящей диагонали будем хранить булевское значение - сведения
о том, находится ли на этой линии ферзь (верхний ферзь не учиты-
вается).  (Заметим, что в силу допустимости позиции на каждой из
линий может быть не более одного ферзя.).

     3.2.  Обход дерева в других задачах.

     3.2.1. Использовать метод обхода дерева для решения  следу-
ющей   задачи:   дан  массив  из  n  целых  положительных  чисел
a[1]..a[n] и число s; требуется узнать, может ли  число  s  быть
представлено  как  сумма  некоторых  из чисел массива a. (Каждое
число можно использовать не более чем по одному разу.)

     Решение. Будем задавать k-позицию последовательностью из  k
булевских  значений,  определяющих,  входят  ли  в  сумму  числа
a[1]..a[k] или не входят. Позиция допустима, если  ее  сумма  не
превосходит s.

     Замечание. По сравнению с полным перебором всех (2 в степе-
ни  n) подмножеств тут есть некоторый выигрыш. Можно также пред-
варительно отсортировать массив a в убывающем порядке,  а  также
считать  недопустимыми  те  позиции, в которых сумма отброшенных
членов больше, чем разность суммы всех  членов  и  s.  Последний
приём  называют  "методом  ветвей  и границ". Но принципиального
улучшения по сравнению с полным перебором тут не получается (эта
задача, как говорят, NP-полна,  см.  подробности  в  книге  Ахо,
Хопкрофта и Ульмана "Построение и анализ вычислительных алгорит-
мов").  Традиционное  название  этой задачи - "задача о рюкзаке"
(рюкзак общей грузоподъемностью s нужно упаковать  под  завязку,
располагая  предметами  веса  a[1]..a[n]).  См.  также в главе 7
(раздел о динамическом программировании)  алгоритм  её  решения,
полиномиальный по n+s.

     3.2.2.  Перечислить все последовательности из n нулей, еди-
ниц и двоек, в которых никакая группа цифр  не  повторяется  два
раза подряд (нет куска вида XX).

     3.2.3.  Аналогичная  задача для последовательностей нулей и
единиц, в которых никакая группа цифр не  повторяется  три  раза
подряд (нет куска вида XXX).

     К этой же категории относятся задачи типа "можно ли сложить
данную фигуру из пентамино" и им подобные. В  них  важно  умелое
сокращение  перебора (вовремя распознать, что имеющееся располо-
жение фигурок уже противоречит требованиям, и по этой ветви  по-
иск не продолжать).
        Глава 4. Сортировка.

     4.1. Квадратичные алгоритмы.

     4.1.1. Пусть a[1],  ...,  a[n]  -  целые  числа.  Требуется
построить  массив  b[1],  ..., b[n], содержащий те же числа, для
которых b[1] <= ... <= b[n].
     Замечание. Среди чисел a[1]...a[n] могут быть равные.  Тре-
буется,  чтобы  каждое целое число входило в b[1]...b[n] столько
же раз, сколько и в a[1]...a[n].

     Решение. Удобно считать, что числа a[1]..a[n] и  b[1]..b[n]
представляют собой начальное и конечное значения массива x. Тре-
бование  "a  и b содержат одни и те же числа" будет заведомо вы-

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