せいすうぶんかつ

整数分割問題はアルゴリズムの古典的な命題の一つであり,この問題に関する記述は再帰に説明する際に基本的に関与する.整数分割とは、n=m 1+m 2+...+mi; (miが正の整数であり、1<=mi<=nである)、{m 1,m 2,...,mi}はnの1つの区分である.{m 1,m 2,...,mi}の最大値がmを超えない場合、すなわちmax(m 1,m 2,...,mi)<=mである場合、nのm分割に属すると称される.ここではnのm区分の個数をf(n,m)と記す.例えばn=4の場合、彼は5つの区分,{4},{3,1},{2,2},{2,1,1},{1,1,1,1}を持っている.注意4=1+3と4=3+1は同一の区分と考えられる.この問題は,nのすべての分割個数,すなわちf(n,n)を求めることである.次に、f(n,m)を求める方法を考える.1.再帰法:nとmの関係に基づいて、(1)n=1の場合、mの値がいくら(m>0)であっても、1つの区分のみが{1}である.(2)m=1の場合、nの値にかかわらず、n個の1,{1,1,1,...,1}の区分しかない.(3)n=mの場合、分割にnが含むか否かによって、(a)の2つに分けることができる.区分にnが含まれている場合は、{n}が1つしかありません.              (b). 分割にnが含まれていない場合、このとき分割で最大の数字もnより小さいに違いない.すなわち、nのすべての(n−1)分割である.従ってf(n,n)=1+f(n,n−1);(4)nmの場合、分割に最大値mが含むか否かによって、(a)の2つに分けることができる.分割にmを含む場合、すなわち{m,{x 1,x 2,...xi}、ここで{x 1,x 2,...xi}の和はn-mであるため、この場合はf(n-m,m)(b)である.区分にmが含まれていない場合、区分中のすべての値はmより小さく、すなわちnの(m−1)区分であり、個数はf(n,m−1)である.従ってf(n,m)=f(n−m,m)+f(n,m−1);以上、f(n,m)=1;               (n=1 or m=1)                              f(n, n);                        (nm)
コードは次のとおりです.

#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int fun(int n, int m)
{
	if(n == 1 || m == 1) return 1;
	else if(n < m) return fun(n, n);
	else if(n == m) return (1 + fun(n, m - 1));
	else return (fun(n, m - 1) + fun(n - m, m));
}

int main()
{
	//freopen("Input.txt", "r", stdin);
	int N;
	scanf("%d", &N);
	while(N--)
	{
		int n;
		scanf("%d", &n);
		printf("%d
", fun(n, n));
	}
	return 0;
}