整理分析了将一个正整数分解成特定的整数和的问题。
把整数N
转化成k个严格递增正整数整数序列n1, n2, …, nk
的和,请问有多少种情况?
设函数 f( n, m )表示n的递增序列和式中最大值小于等于m的数量。那么,如果n分解的最大值为m,则有f( n-m, m-1 )种;最大值小于m,则有f(n, m-1)种。
则有:
若n > m:f(n, m) = f( n-m, m-1 ) + f( n, m-1 )
若n <= m:f(n, m) = f(n, n) = 1 + f(n,n-1)
初始条件:
f( 1, 1 ) = 1
f(i,1) = 0 其中i>1
例程:
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
enum { max_len = 501 };
double cases[max_len][max_len];
class StairCases
{
public:
StairCases() { init(); }
double get_num(int n)
{
return lookup(n, n) -1;
}
private:
double lookup( int n, int m )
{
if ( cases[n][m] >= 0 )
{
return cases[n][m];
}
if ( n==1 && m==1 )
{
return cases[n][m] = 1;
}
if ( n>1 && m==1 )
{
return cases[n][m] = 0;
}
if ( n <= m )
{
return cases[n][n] = 1+lookup( n, n-1 );
}
else // n>m
{
return cases[n][m] = lookup(n-m, m-1) + lookup(n, m-1);
}
}
void init()
{
for ( int i=1; i<max_len; ++i )
{
for ( int j=1; j<max_len; ++j )
{
cases[i][j] = -1;
}
}
for ( int i=2; i<max_len; ++i )
{
cases[i][1] = 0;
}
cases[1][1] = 1;
}
};
int main()
{
StairCases sc;
int n;
while ( cin >> n && n )
{
printf( "%.0f\n", sc.get_num(n) );
}
return 0;
}
将一个正整数n表示成一系列正整数之和,n = n1 + n2 + … + nk
,其中n1 >= n2 >= … >= nk >= 1
.求整数n的划分个数,并展示这些划分。
分析:设f(n,m)为n的不同的划分中,最大加数小于等于m的个数。则有,
若n > m:f(n,m) = f(n-m,m) + f(n,m-1) (对应最大值为m和小于m两种情况)
若 n <=m: f(n,m) = f(n,n) = 1 + f(n,n-1) n>1
初始值:f(n,1) = 1, n>=1
f(1,n) = 1
例程:
#include <iostream>
#include <vector>
using namespace std;
typedef vector< vector<int> > split_vect;
split_vect split( int n, int m )
{
if ( n==1 )
{
vector<int> cur( 1,1 );
return split_vect( 1, cur );
}
if ( m==1 )
{
vector<int> cur( n,1 );
return split_vect( 1, cur );
}
if ( n <= m )
{
split_vect ret( 1, vector<int>(1,n) );
split_vect const& tmp_ary = split( n,n-1 );
ret.insert( ret.end(), tmp_ary.begin(), tmp_ary.end() );
return ret;
}
else // n > m
{
split_vect ret;
split_vect tmp_ary1 = split( n-m,m );
for ( int i=0; i<(int)tmp_ary1.size(); ++i )
{
tmp_ary1[i].push_back( m );
}
split_vect const& tmp_ary2 = split( n,m-1 );
ret.insert( ret.end(), tmp_ary1.begin(), tmp_ary1.end() );
ret.insert( ret.end(), tmp_ary2.begin(), tmp_ary2.end() );
return ret;
}
}
void print( vector<int> const& v )
{
for ( int i=0; i<(int)v.size(); ++i )
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
split_vect const& ret = split(8, 8);
cout << "kinds: " << ret.size() << endl;
for ( int i=0; i<(int)ret.size(); ++i )
{
print( ret[i] );
}
return 0;
}