Информатика
>>
Книги, журналы
>>
А.Шень, Программирование: теоремы и задачи
>>
глава 2. Порождение комбинаторных объектов
Параграфы:
-
параграф 1. Размещения с повторениями
(4 задачи)
параграф 2. Перестановки
(1 задача)
параграф 3. Подмножества
(5 задач)
параграф 4. Разбиения
(4 задачи)
параграф 5. Коды Грея и аналогичные задачи
(2 задачи)
параграф 6. Несколько замечаний
(4 задачи)
параграф 7. Подсчёт количеств
(3 задачи)
Фильтр
Задачи
Страница: << 1 2 3 4 5 >> [Всего задач: 23]
Перечислить все последовательности длины 2n,
составленные из n единиц и n минус единиц,
у которых сумма любого начального отрезка неотрицательна,
--е число минус единиц в нём не превосходит числа единиц.
(Число таких последовательностей называют числом
Каталана)
(Число разбиений; предлагалась на Всесоюзной олимпиаде
по программированию 1988 года) Пусть P(n) — число
разбиений целого положительного n на целые положительные
слагаемые (без учёта порядка, 1 + 2 и 2 + 1 — одно и то же
разбиение). При n = 0 положим P(n) = 1 (единственное
разбиение не содержит слагаемых). Построить алгоритм
вычисления P(n) для заданного n.
В предложенном в предыдущей задаче алгоритме используется сравнение двух
массивов (x <> last). Устранить его, добавив булевскую
переменную l и включив в инвариант соотношение последовательность x - последняя.
Перечислить все возрастающие последовательности
длины k из чисел 1..n в лексикографическом
порядке. (Пример: при n=5, k=2 получаем:
12 13 14 15 23 24 25 34 35 45.)
Представляя по-прежнему разбиения как невозрастающие
последовательности, перечислить их в порядке, обратном
лексикографическому (для n=4, например, должно быть
4, 3+1, 2+2, 2+1+1, 1+1+1+1).
Страница: << 1 2 3 4 5 >> [Всего задач: 23]
Задача 98836 (#2.6.1) |
|
|
|
|
Решение |
Задача 98840 (#2.7.1) |
|
|
|
|
|
Решение |
Задача 98821 (#2.1.2) |
|
|
|
|
|
Решение |
Задача 98826 (#2.3.2) |
|
|
|
|
|
Решение |
Задача 98831 (#2.4.2) |
|
|
|
|
|
Решение |
Страница: << 1 2 3 4 5 >> [Всего задач: 23]
