Разбиением положительного целого числа M - это представление M в виде суммы целых чисел.
Классическая счетная задача - определение количества P(M) разбиений числа.
Для M=6 разбиениями являются
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
Интересен способ выражения функции P(M) через другую функцию Q(M,N), которая определяется
как число разбиений целого M со слагаемыми, не превышающими N. Несложные рекурсивные рассуждения приводят к следующему:
1.
Q(M,N)=1. Это значит, что существует только одно разбиение целого числа M, в котором наибольшее слагаемое есть единица, а именно M=1+1+...+1.
2.
Q(1,M)=1. Существует только одно разбиение целого числа 1 независимо от величины N наибольшего слагаемого.
3.
Q(M,N)=Q(M,M), если M<N. Ясно, что никакое разбиение M не может содержать слагаемого N, большего M.
4.
Q(M,M)=1+Q(M,M-1). Существует только одно разбиение M со слагаемым, равным M. Все другин разбиения M имеют наибольшее слагаемое N<=M-1.
5.
Q(M,N)=Q(M,N-1)+Q(M-N,N). Любое разбиение M с нибольшим слагаемым, меньшим или равным N, или не содержит N в качестве слагаемого - в этом случае данное разбиение также входит в число Q(M,N-1), или содержит N - приэтом остальные слагаемые образубт разбиение числа M-N. Эти 5 уравнений рекурсивно определяют функцию Q(M,N). Они определяют P(M), так как P(M)=Q(M,M).
Реализовать такую программу сравнительно непросто, если используемый язык программирования не поддерживает рекурсивные вызовы (есть ли такие сейчас?). На языке же С++ решение может выглядеть так:
#include <iostream.h>
int a[1000];
void add( int n, int max, int k)
{
if ( n < max ) max = n;
for ( int i = max; i>0; i-- ){
a[k] = i;
if ( i==n )
{
for( int i=0; i<k; i++ )
cout << a << "+";
cout << a[k] << endl;
}
else
add( n-i,i ,k+1 );
}
}
int main()
{
int n=6;
add(n,n,0);
return 0;
}
|
