题目:把一个正整数n拆分成若干个正整数的相加,列出所有组合 例如:
4=4
4=1+3=2+2
4=1+1+2
4=1+1+1+1
动机:网上有好多解答,大部分都是给出拆分结果的个数,不能把把每一种的情况打印出来,或者效率低,本人接触这个题目很久了,最近心血来潮想搞定它,嘿嘿
思路一:
设置一个递归方法recursive(int last, int curSum, int n),该方法包含以下几个步骤:
0. 递归出口: 当 last+curSum > n ,返回
1. 该递归方法包含三个参数
a. last:上个递归传递给它的起始数字
b.curSum:当前累加和
c. n:待拆分的数字
2. 设置变量i从last开始到n遍历:
a. curSum=curSum+i;
b. list(成员变量)加入i
c. 判断curSum==n ,如果成立,打印list
3. 递归调用 recursive(i, curSum,n);
4. 还原curSum,list,消除下一层递归对本层递归在成员变量curSum,list的影响。
实现代码
package com.uestc.miaoshi;
import java.util.ArrayList;
import java.util.Scanner;
public class BreakN2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
count = 0;
recursive(1, 0 , n);
System.out.println("所有组合总数" + count);
}
}
static int count = 0;
static ArrayList<Integer> list = new ArrayList<>();
static void recursive(int last, int curSum, int n) {
if (last + curSum > n) return;
for (int i = last; i <= n ; i++) {
curSum = curSum + i;
list.add(i);
if (curSum == n) {
count ++;
System.out.println(list);
}
recursive(i, curSum, n);
curSum = curSum - i;
Integer o = i;
list.remove(o);
}
}
}
输入 5 ,打印出以下结果:
这种思路的优点是容易思考,缺点是当n很大时,耗时大,归根是算法效率低。下面我们继续介绍一种效率高的解决方法。
思路二:动态规划,设置一个函数 f(n, m) ,该函数的功能就是把正整数分成 m等分, 并且m 份中不允许为0,也就是说每一份至少大于等于1. 我们可以得到状态转移方程:
f(n ,m ) = f(n-m,m) + f(n-1, m-1)
看到这里如果,你能经过自己的思考就明白这个公式,我只能膜拜,因为你的天赋很高,哈哈,好了,言归正传。
方程的第一项 f(n-m, m) 代表m份全部都大于1的分法,也可以这样理解,先把 m 拆分成 m 个 1 ,每一份都是1 ,然后 再把 n – m 分到 m 份中
方程的第二项是 f(n-1, m-1)代表至少存在一份为1的情况,那么怎么保证呢?先从n中拿出1,放到m份中的1份,然后把 n-1分到 m-1份
总结: f(n,m)=f(n-m, m)不包含1的组合+f(n-1, m-1)包含1的组合,一分为二的思想
实现代码:
package com.uestc.miaoshi;
import java.util.Scanner;
public class BreakN {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
long start = System.currentTimeMillis();
int res = 0;
int n = sc.nextInt();
for (int i = 1; i <= n; i++) {
res = res + f(n, i);
}
System.out.println("总共组合数: " + res);
long end = System.currentTimeMillis();
System.out.println("耗时秒数:"+ (end - start)/1000);
}
}
/** * 函数功能,把正整数 n 分成 m 等份 4 = 1+3 = 2+2 * @param n * @param m * f(n) = f(n-m, m) + f(n-1, m-1) */
private static int f(int n, int m) {
if ( n <=0 || m <= 0 || n < m) {
return 0;
}
if (m == 1) return 1;
return f(n - m, m) + f(n-1, m-1);
}
}
其实说到这里我们只是把问题解决了一半,我们可以轻松的得出所有组合的总数,我们还不能把每一种组合的具体情况打印出来。咋办呢,山人自有妙计。
思路我就照着下面这个图讲吧
首先定义树的数据结构:
class TreeNode {
int n, m;
ArrayList<Integer> res = new ArrayList<>();
boolean addAll;
TreeNode left, right, parent;
public TreeNode(int n, int m, boolean addAll) {
this.n = n;
this.m = m;
this.addAll = addAll;
}
}
addAll =false表示f(n-1, m-1), 也就是代表m份包含1的分法,由下而上回溯时,上结点的res=下结点的res加上一个元素1
addAll =true表示f(n-m, m), 也就是代表m份不包含1的组合的分法,由下而上回溯时,上结点的res=下结点的res每个元素加上1
res表示具体的分法
我们可以把图看成是二叉树的升级版本(每一个节点都有父指针),叶子节点表示具体的分法,比如f(1,1) = 1 ,f(3,1)=3。
我们可以从叶子结点回溯到根结点,例如
f(1,1) = 1, addAll=false,向上回溯到f(2,2)结点,导致f(2,2)结点的res =[1,1]
f(2,2),res=[1,1],addAll=true,向上回溯到f(4,2)结点,导致f(4,2)结点的res=[2,2]
f(3,1),res=[3],addAll=false,向上回溯到f(4,2)结点,导致f(4,2)结点的res=[1,3]
下面看具体实现代码:
package com.uestc.miaoshi;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class TreeNode {
int n, m;
ArrayList<Integer> res = new ArrayList<>();
boolean addAll;
TreeNode left, right, parent;
public TreeNode(int n, int m, boolean addAll) {
this.n = n;
this.m = m;
this.addAll = addAll;
}
}
public class BreakNToM {
static ArrayList<TreeNode> leafs = new ArrayList<>();
static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
long start = System.currentTimeMillis();
int n = in.nextInt();
int m = in.nextInt();
leafs.clear();
f(n, m, true);
for (TreeNode leaf : leafs) {
recursive(leaf);
}
long end = System.currentTimeMillis();
System.out.println( (end - start)/1000);
System.out.println(result);
}
}
private static void recursive(TreeNode leaf) {
if (leaf.parent == null) {
Collections.sort(leaf.res);
result.add(leaf.res);
return;
}
ArrayList<Integer> res = leaf.res;
if (leaf.addAll) {
ArrayList<Integer> temp = new ArrayList<>();
for (int x : res) {
temp.add(x + 1);
}
leaf.parent.res = temp;
} else {
res.add(1);
leaf.parent.res = res;
}
recursive(leaf.parent);
}
static TreeNode f(int n, int m, boolean allAdd) {
if (n < m || n <= 0 || m <= 0) {
return null;
}
TreeNode node = new TreeNode(n, m, allAdd);
if (n == m) {
TreeNode leaf = new TreeNode(n, n, allAdd);
for (int i = 0; i < m; i++) {
leaf.res.add(1);
}
leafs.add(leaf);
return leaf;
}
if (m == 1) {
TreeNode leaf = new TreeNode(n, 1, allAdd);
leaf.res.add(n);
leafs.add(leaf);
return leaf;
}
node.left = f(n - m, m, true);
if (node.left != null)
node.left.parent = node;
node.right = f(n - 1, m - 1, false);
if (node.right != null)
node.right.parent = node;
return node;
}
}
输入 8 3
搞定
今天的文章打印从1到n的全部正整数_正整数前n个数的和是多少分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/81784.html