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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

  { <> .}
  k:=n-1;
  {последовательность справа от k убывающая: x[k+1] >...> x[n]}
  while x[k] > x[k+1] do begin
  | k:=k-1;
  end;
  {x[k] < x[k+1] > ... > x[n]}
  t:=k+1;
  {t <=n, x[k+1] > ... > x[t] > x[k]}
   while (t < n) and (x[t+1] > x[k]) do begin
   | t:=t+1;
   end;
   {x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]}
   ... обменять x[k] и x[t]
   {x[k+1] > ... > x[n]}
   ... переставить участок x[k+1] ... x[n] в обратном порядке

Замечание. Программа имеет знакомый  дефект:  если  t  =  n,  то
x[t+1] не определено.

     2.2.2. Модифицировать алгоритм перехода к следующей  перес-
тановке так, чтобы он сам проверял, не является ли данная перес-
тановка последней.

     2.3. Подмножества.

     2.3.1. Перечислить все k-элементные подмножества  множества
{1..n}.

     Решение.  Будем представлять каждое подмножество последова-
тельностью x[1]..x[n] нулей и единиц длины n, в которой ровно  k
единиц. (Другой способ представления разберем позже.) Такие пос-
ледовательности упорядочим лексикографически (см. выше). Очевид-
ный  способ  решения  задачи - перебирать все последовательности
как раньше, а затем отбирать среди них те, у которых k единиц  -
мы отбросим, считая его неэкономичным (число последовательностей
с  k  единицами  может  быть  много меньше числа всех последова-
тельностей). Будем искать такой алгоритм, чтобы  получение  оче-
редной последовательности требовало порядка n действий.
     В каком случае s-ый член  последовательности  можно  увели-
чить,  не  меняя предыдущие? Если x[s] меняется с 0 на 1, то для
сохранения общего числа единиц нужно справа от х[s]  заменить  1
на 0. Таким образом, х[s] - первый справа нуль, за которым стоят
единицы.  Легко  видеть,  что х[s+1] = 1 (иначе х[s] не первый).
Таким образом надо искать наибольшее  s,  для  которого  х[s]=0,
x[s+1]=1;

                  ______________________
               x |________|0|1...1|0...0|
                           s

За х[s+1] могут идти еще несколько единиц, а после них несколько
нулей. Заменив х[s] на 1, надо выбрать идущие за ним члены  так,
чтобы последовательность была бы минимальна с точки зрения наше-
го  порядка,  т. е. чтобы сначала шли нули, а потом единицы. Вот
что получается:

  первая последовательность    0...01...1 (n-k нулей, k единиц)
  последняя последовательность 1...10...0 (k единиц, n-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 Большая Одесская Библиотека.