Pascal/Вводится целое неотрицательное число. Определить, сколько различных чисел такой же длины можно составить из его цифр. При составлении числа должны использоваться все цифры исходного числа, в том же количестве, что и в исходном числе.

Чтобы узнать, сколько различных чисел той же длины можно составить из цифр исходного числа, нужно решить комбинаторную задачу о перестановках с повторениями.

Пусть в числе n цифр. Среди них могут быть одинаковые. Если все цифры разные, ответ — \( n! \). Но если есть повторяющиеся, общее число перестановок всех цифр (без учёта ведущих нулей) равно:

\[ P = \frac{n!}{c_1! \cdot c_2! \cdot \ldots \cdot c_k!} \]

где \( c_i \) — сколько раз встречается каждая различная цифра.

Однако среди этих перестановок могут быть такие, где на первом месте стоит ноль. Такие комбинации не считаются числами той же длины (ведущий ноль отбрасывается, и длина уменьшается). Поэтому, если в исходном числе есть нули, нужно вычесть те варианты, которые начинаются с нуля.

Число перестановок, начинающихся с нуля, считаем так: фиксируем ноль на первой позиции, а оставшиеся \( n-1 \) цифр переставляем с учётом повторений, при этом количество нулей уменьшается на 1. То есть:

\[ P_0 = \frac{(n-1)!}{(c_0 - 1)! \cdot c_1! \cdot \ldots \cdot c_k!} \]

где \( c_0 \) — количество нулей в исходном числе.

Тогда ответ: \( P - P_0 \).

Если нулей в числе нет, ответ просто \( P \).

Пример: число 112. Цифры: 1,1,2. n=3. \( P = 3!/(2! \cdot 1!) = 3 \). Нулей нет, ответ 3 (числа: 112, 121, 211).

Пример с нулём: число 100. Цифры: 1,0,0. n=3. \( P = 3!/(1! \cdot 2!) = 3 \) (перестановки: 100, 010, 001). Из них начинаются с нуля: фиксируем 0, остались 1 и 0: \( P_0 = 2!/(1! \cdot 1!) = 2 \) (010 и 001). Ответ: 3 - 2 = 1 (только 100).

Если исходное число 0, ответ 1.

Таким образом, алгоритм сводится к подсчёту частот цифр, вычислению факториалов и применению формулы.

0 0 Пожаловаться