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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

     Опишем, как можно  перейти  от  x  к  следующей  последова-
тельности.  Согласно определению, у следующей последовательности
первые s членов должны быть такими же, а (s+1)-ый - больше.  Это
возможно, если x[s+1] было меньше n. Среди таких s нужно выбрать
наибольшее  (иначе полученная последовательность не будет непос-
редственно следующей). Соответствующее x[s+1] нужно увеличить на
1. Итак, надо, двигаясь с конца последовательности, найти  самый
правый  член,  меньший  n (он найдется, так как по предположению
x<>last), увеличить его на 1, а идущие  за  ним  члены  положить
равными 1.

        p:=k;
        while not (x[p] < n) do begin
        | p := p-1;
        end;
        {x[p] < n, x[p+1] =...= x[k] = n}
        x[p] := x[p] + 1;
        for i := p+1 to k do begin
        | x[i]:=1;
        end;

     Замечание. Если членами последовательности считать числа не
от  1 до n, а от 0 до n-1, то переход к следующему соответствует
прибавлению 1 в n-ичной системе счисления.

     2.1.2. В предложенном алгоритме используется сравнение двух
массивов x <> last. Устранить его, добавив булевскую  переменную
l и включив в инвариант соотношение l <=> последовательность x -
последняя.

     2.1.3. Напечатать все подмножества множества {1...k}.

     Решение.  Подмножества находятся во взаимно однозначном со-
ответствии с последовательностями нулей и единиц длины k.

     2.1.4. Напечатать все последовательности из k положительных
целых чисел, у которых i-ый член не превосходит i.


     2.2. Перестановки.

     2.2.1. Напечатать все перестановки чисел 1..n (то есть пос-
ледовательности  длины  n, в которые каждое из чисел 1..n входит
по одному разу).

     Решение. Перестановки будем  хранить  в  массиве  x[1],...,
x[n]  и  печатать в лексикографическом порядке. (Первой при этом
будет перестановка <1 2...n>, последней - .)  Для  сос-
тавления  алгоритма  перехода к следующей перестановке зададимся
вопросом: в каком случае k-ый член перестановки можно увеличить,
не меняя предыдущих? Ответ: если он меньше какого-либо из следу-
ющих членов (членов с номерами больше k). Мы  должны  найти  на-
ибольшее  k,  при  котором  это  так,  т. е. такое k, что x[k] <
x[k+1] > ... > x[n]. После  этого  x[k]  нужно  увеличить  мини-
мальным  возможным способом, т. е. найти среди x[k+1], ..., x[n]
наименьшее число, большее его. Поменяв x[k] с ним, остается рас-
положить числа с номерами k+1, ..., n  так,  чтобы  перестановка
была наименьшей, то есть в возрастающем порядке. Это облегчается
тем, что они уже расположены в убывающем порядке.

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