打印从1到n的全部正整数_正整数前n个数的和是多少

打印从1到n的全部正整数_正整数前n个数的和是多少题目:把一个正整数n拆分成若干个正整数的相加,列出所有组合例如:4=44=1+3=2+24=1+1+24=1+1+1+1动机:网上有好多解答,大部分都是给出拆分结果的个数,不能把把每一种的情况打印出来,或者效率低,本

题目:把一个正整数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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注