адача
33.
Составить рекурсивную программу-функцию
подсчета количества x(m)
разбиений натурального числа m,
то есть его представлений в виде суммы
натуральных чисел.
6;
5+1;
4+2, 4+1+1;
3+3, 3+2+1, 3+1+1+1;
2+2+2, 2+2+1+1, 2+1+1+1+1;
1+1+1+1+1+1;
Таким образом, x(m)=11 и понятно, что простым перебором возможных случаев уже при m>10 справиться с задачей достаточно сложно.
Для решения исходной задачи перейдем к рассмотрению обобщенной задачи. Составить программу-функцию подсчета количества P(m,n) разбиений натурального числа m со слагаемыми, не превосходящими n. Ясно, что x(m)=P(m,m). Поэтому достаточно научиться вычислять значения функции P(m,n). Но для неё нетрудно выделить рекурсивную базу и указать правило декомпозиции. Сделать это можно, исходя из следующих вполне прозрачных свойств этой функции.
P(m,1)=1 - существует только одно разбиение m, в котором слагаемые не превосходят единицы, а именно: m=1+1+…+1.
P(1,n)=1 - число единица имеет только одно представление при любом n.
P(m,n)=P(m,m) при n>m - слагаемые, большие m, в разбиениях отсутствуют.
P(m,m)=P(m,m-1)+1 - существует лишь одно разбиение со слагаемым, равным m. Все иные разбиения имеют слагаемые, не превосходящие m-1.
P(m,n)=P(m,n-1)+P(m-n,n) (n<m). Обоснование этого соотношения проводится так. Все разбиения m на сумму слагаемых, не превосходящих n, можно разбить на два непересекающихся класса: суммы, не содержащие n в качестве слагаемого, и суммы, содержащие такое n. Количество элементов первого класса равно P(m,n-1), а количество элементов второго класса подсчитаем так. Без учета слагаемого n суммы элементов второго класса равны m-n. Значит, их общее количество равно P(m-n,n) и, следовательно, общее количество элементов второго класса также равно этой величине. Тем самым свойство 5 установлено.
Первые два свойства определяют базу рекурсии, а следующие три задают декомпозицию. Строго в соответствии с этими утверждениями и составлена рекурсивная программа-функция deco(n,m) для вычисления величины P(m,n):
Контрольные примеры:
