9.7. Дополнительные задачи

Задача 9.41:

Найти число способов разложить данное число \(N\) в сумму слагаемых: а) считая разложения, различающиеся порядком слагаемых, различными; б) считая разложения, различающиеся порядком слагаемых, одинаковыми; в) считая разложения, различающиеся порядком слагаемых, одинаковыми и требуя, чтобы все слагаемые в каждом разложении были различны; г) и т.п.

Задача 9.42:

Найти число правильных скобочных последовательностей, состоящих из \(N\) пар скобок. [Коротко говоря, правильная скобочная последовательность — это последовательность открывающих и закрывающих скобок, в которой скобки сбалансированы. (()) — это правильная скобочная последовательность из двух пар скобок, ()() — тоже, а )()( и ())( — нет. Я надеюсь, смысл определения понятен].

а) Используя только круглые скобки;

б) используя круглые, квадратные и фигурные скобки: ()[], [{}] — правильные, а ({)} и )()( — нет.

Научитесь выводить скобочную последовательность по номеру.

Задача 9.43:

Сколькими способами можно замостить доску \(N\times M\) доминошками?

Задача 9.44:

Дана строка \(s\), состоящая из букв, и маска \(m\). Маска может содержать буквы, символы * и ?. Звёздочка может обозначать любую строку (в т.ч. пустую), а знак вопроса — любой символ. Подходит ли данная строка под эту маску? (Например, строка abcdefg подходит под маску ab*f?, но не под ab?f?.)

И ещё я дам несколько задач, по которым я почти не буду писать ответы/подсказки/и т.п.; в разделе «Ответы» вы найдёте только скорее комментарии по их использованию. Думайте над этими задачами сами :)

Задача 9.45:

При умножении матрицы размера \(a\times b\) на матрицу \(b\times c\) получается матрица \(a\times c\), при этом, чтобы выполнить такое умножение, требуется выполнить \(abc\) умножений отдельных чисел. (Т.е. сложность операции умножения матриц — \(O(abc)\).) Умножение матриц не коммутативно (т.е. матрицы нельзя менять местами: \(AB\neq BA\)), но ассоциативно (т.е. в любом выражении можно расставлять скобки как угодно, результат от этого не изменится: \(A(BC)=(AB)C\)). Правда, от расстановки скобок в выражении зависит количество необходимых умножений чисел. Соответственно, получается задача. Дано выражение \(A_1\cdot A_2\cdot\ldots\cdot A_n\), где \(A_1\), \(A_2\) и т.д. — матрицы; размер матрицы \(A_i\)\(r_i\times c_i\), при этом \(c_i=r_{i+1}\) для всех \(i\). Требуется в выражении расставить скобки (т.е. указать порядок выполнения действий) так, чтобы потребовалось как можно меньше умножений чисел.

Задача 9.46:

Дана строка \(s_1\). Разрешается за одно действие либо удалить произвольный символ текущей строки, либо вставить произвольный символ в произвольное место текущей строки, либо изменить произвольный символ текущей строки (на любой символ по вашему выбору).

а) Требуется за наименьшее число действий получить данную строку \(s_2\).

б) То же самое, но за каждое действие есть штраф: \(d\) за удаление, \(i\) за вставку и \(c\) за замену, требуется минимизировать штраф.

в) То же самое, но штрафы зависят от того, что это за символы (т.е. штраф за удаление зависит от того, какой символ удаляем и т.д.; все эти зависимости заданы во входном файле).

г) и т.д.

Задача 9.47:

TeX’s line-breaking algorithm has proved to be general enough to handle a surprising variety of different applications; this, in fact, is probably the most interesting aspect of the whole TeX system.

Donald E. Knuth. The TeX book.

Алгоритм TeX’а для разбиения строк оказывается достаточно всеобщим для того, чтобы справиться с удивительным разнообразием различных приложений. Фактически, это, вероятно, наиболее интересный аспект в системе TeX.

Дональд Е. Кнут. Все про TeX.

Идея и код фигурного абзаца тоже взяты из TeXbook.

../_images/paragraph.png