网站备案 法人/我想做网络推广

问题描述

先将一个整数分割成若干个整数相加，求多少种分割方法，如4
4
3+1
2+2 2+1+1
1+1+1+1
一种5种

思路

我们用到的分治思想，首先我们将问题首先为一个函数F(a,b)表示将a分解为最大值不超过b的式子。因此我们在做的时候，就先将这个递推公式给算出来，那么具体该怎么做呢？
首先我们讲一个数分解的时候，肯定是F(a,a)，而这个我们将它分为一个a加上F(a,a-1),这是一种情况，因此F(a,b)=1+F(a,b-1)
第二种就是F(a,b)，b>a的时候，我们不可能可以分解出来比a还大的式子，因此这种情况，就变成了F(a,b)=F(a,a)
第三种情况就是，a,b其中一个为1的时候，F都是只有一种情况，因此F(a,b)=1
第四种情况就是，一般情况。我们将其分两种，一种里面有b，一种里面没有b。而有b的情况就相当于每一个式子一定至少有一个b，我们可以简化为F(a-b,b)，而另一种情况就是F(a,b-1)
综上所述：
1 a=1 || b=1
F(a,a) b>a
F(a,b)= 1+F(a,b-1) a=b
F(a-b,b)+F(a,b-1) 1<a<b

实现

package suanfa.IntegerDivision;import java.util.Scanner;public class Main {public int f(int n,int m){if (n==1 || m==1)return 1;else if (n<m){return f(n,n);}else if (n==m){return 1+f(n,n-1);}else if (n>m && m>1) {return f(n, m - 1) + f(n - m, m);}else {return -1;}}public static void main(String[] args) {Main yyp = new Main();Scanner in = new Scanner(System.in);int n;System.out.println("请输入要分割的整数");n = in.nextInt();System.out.println(yyp.f(n,n));}
}

测试