整数分割

整数n(100>n>1)が何通りに分割できるか

つまり、正の整数の和で何通りに表せるか

例えば、6の場合は、以下の11通りとなる。

[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]

動的計画法(Dynamic programming)で解いてみよう

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int dynamic(int m){
	int n,a,i;
	int tmp;
	//int p[100][100];//静的配列
	vector< vector<int> > p;//vector 動的配列
	p.resize( m, vector<int>(m) );//vector 動的配列
	for(a = 0;a <= m; a++)
		p[0][a] = 1;//分割し終わったことを示す配列
	for(n = 0;n <= m; n++)
		p[n][1] = 1;//aが1のときは,1しかない
	for(n = 1;n <= m; n++){
		for(a = 2;a <= m; a++){
			p[n][a] = p[n][a-1];//aを含まない分割数
			if(n >= a)
				p[n][a] += p[n-a][a];//aを含む分割数
		}
	}
	return p[m][m];
}
void main(){
	int n;
	int tmp;
	while(1){
		scanf("%d",&n);
		if(n == 0) break;
		printf("%d\n", dynamic(n) );
	}
}

100以上の値で実行する場合、signed int型だと、121までしかできなかった

バックトラック法(Backtracking method)でも解いてみる

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int backtrak(int n, int a){
	int ret;
	if(n == 0 || a == 1)//分割しきったとき || 1しかないとき
		return 1;
	ret = backtrak(n, a-1);//aより下の結果
	if(n >= a)//nがa以上ならば
		ret += backtrak(n-a,a);//aが解に含まれる場合
	return ret;
}
void main(){
	int n;
	int tmp;
	while(1){
		scanf("%d",&n);
		if(n == 0) break;
		printf("%d\n",backtrak(n, n) );
	}
}

動的計画法と比べてありえないほど時間がかかる