1910 - 整数划分
时间限制 : 1 秒
内存限制 : 128 MB
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。
正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。
题目输入
第一行，输入需要划分的整数n。
题目输出
输出整数划分的个数。
输入/输出样例
输入格式
6
输出格式
11
C语言解答
#include<stdio.h> int main() { int q(int ,int ); int n,r; scanf("%d",&n); r=q(n,n); printf("%d\n",r); //system("pause"); return 0; } int q(int n,int m) { if(n<1||m<1) return 0; if(n==1||m==1) return 1; if(n<m) return q(n,n); if(n==m) return 1+q(n,m-1); return q(n,m-1)+q(n-m,m); }
C++解答
#include<iostream> using namespace std; class BS{ int n,m; public: void q(int n,int m) { this->n=n; this->m=m; } int p(int n,int m) { if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n<m) return p(n,n); if(n==m) return p(n,m-1)+1; else return p(n,m-1)+p(n-m,m); }}; int main() { BS a; int N,M; cin>>N; M=N; a.q(N,M); a.p(N,M); cout<<a.p(N,M)<<"\n"; }
Java解答
import java.util.Scanner; public class Main { /** * 整数划分算法 *@param number 要划分的数 *@param maxSplitter 最大划分元素 *@return int number能有多少种划分方法 *@author 小龙同学_CTGU *@version 2013-9-3 */ public static int split(int number, int maxSplitter) { if (number < 1 || maxSplitter < 1) return 0; if (number == 1 || maxSplitter == 1) return 1; if (number < maxSplitter) return split(number, number); if (number == maxSplitter) return (split(number, maxSplitter - 1) + 1); if (number > maxSplitter) return (split(number, maxSplitter - 1) + split((number - maxSplitter), maxSplitter)); return 0; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int a=scan.nextInt(); System.out.println(split(a,a)); scan.close(); } }