Математика: Комбинаторика и перебор.

Перечислить все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел (N, K-вводятся, 1<K<N ). Если К=0, то выдать все возможные произведения (суммы). Представления чисел, отличающихся только порядком сомножителей (слагаемых), считаются одинаковыми.

Предложим простой способ построения всех разбиений числа.

на слагаемые. Разбиения будут строится в порядке, обратном лексикографическому. Очевидно, что первым разбиением в таком порядке будет разбиение, содержащее одно слагаемое, равное, а последним - разбиение из слагаемых, равных 1.

Как выглядит разбиение, следующее непосредственно за разбиением

n=с[1]+...+с[к] (1)

Будем искать разбиение, которое имеет самое большое число начальных слагаемых, равных начальным слагаемым разбиения (1) - обозначим эти слагаемые а[1],...,а[t-1] - и оставшиеся слагаемые которого определяются разбиением, непосредственно следующим за разбиением

s=a[t]+a[t+1]+...+a[k].

Легко видеть, что эти условия однозначно определяют значение t

t=max{i:a[i]>1}.

Таким образом, задача свелась к нахождению разбиения, непосредственно следующего за разбиением s=a[t]+1+...+1, где a[t]>1, а количество единиц равно k-t.Таким разбиением является разбиение s1=p+p+...+p+(s mod p), где p=a[t]-1.

Вверх по странице, к оглавлению и навигации.