Задача 8.
Составить программу, которая печатает все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел (N, K-вводятся, 1<K<N ). Если К=0, то выдать все возможные произведения (суммы). Представления чисел, отличающихся только порядком сомножителей (слагаемых), считаются одинаковыми.
|
Решение задачи 8.
Предложим простой способ построения всех разбиений числа
на слагаемые. Разбиения будут строится в порядке, обратном лексикографическому. Очевидно, что первым разбиением в таком порядке будет разбиение, содержащее одно слагаемое, равное, а последним - разбиение из слагаемых, равных 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.
|
