前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >随机产生和为S的N个正整数

随机产生和为S的N个正整数

作者头像
孟君
发布2019-08-26 16:59:34
8450
发布2019-08-26 16:59:34
举报
文章被收录于专栏:孟君的编程札记

如果给你一个问题:“随机产生和为S的N个正整数”, 你会如何做呢?

针对该问题,解决的方法有很多种。在这篇文章中,我将为大家给出两种比较好理解的解决方法:一个是“尺子法”;另外一个是“锯木头法”。(名字随便取的,主要是方便理解用)。

方法一:尺子法

将给定值S看成一个尺子的长度,那么,生成N个和为S的正整数的问题就变成在尺子中寻找出N-1个不同的刻度加上最小刻度0和最大刻度S 一共有N+1个刻度。然后,从小到大,计算出相邻刻度的长度,这些长度就可以认为是随机的,因为尺子中产生的N-1个刻度是随机的。

有了上述思想,我们只要如下三个步骤就能完成这个功能。

  1. 验证参数S和N的正确性
  2. 尺子中产生N-1个不同刻度
  3. 计算相邻刻度之间的值
代码语言:javascript
复制
  /**
   * <p>
   * 随机产生和为sum(如10)的num(如5)个正整数
   * </p>
   * 
   * @param num 期望产生的随机数个数
   * @param sum 所有产生随机数的和
   * @return 返回满足和为sum的num个随机正整数组成的数组
   */
  public static Integer[] random(int num, int sum) {

    /**
     * Step1: 验证参数正确性
     */
    if (num < 1) {
      throw new IllegalArgumentException("产生随机数个数的num不能小于1");
    }
    if (sum < num) {
      throw new IllegalArgumentException("产生随机数个数的num不能大于和sum");
    }
    if (sum <= 0) {
      throw new IllegalArgumentException("sum需要为正整数");
    }

    /**
     * Step2: 0~sum之间随机产生num-1个不同的刻度
     */
    Random rand = new Random();
    Set<Integer> locations = new TreeSet<Integer>();
    while (locations.size() < num - 1) {
      locations.add(rand.nextInt(sum - 1) + 1);
    }

    locations.add(0);
    locations.add(sum);

    /**
     * Step3: 计算出相邻刻度的差,计算出来的长度就可以代表一个随机数
     */
    Integer[] locationsArray = locations.toArray(new Integer[] {});
    Integer[] resultArray = new Integer[num];
    for (int i = 0; i < num; i++) {
      resultArray[i] = locationsArray[i + 1] - locationsArray[i];
    }

    return resultArray;
  }

方法二:锯木头法

锯木头法的思想则是将S看成木头的长度,随机产生和为S的N个正整数的问题转换成锯N-1次木头,将产生N段小木头,N段的小木头其长度和就是S

有了上述思想,我们便可以通过如下几个步骤实现该方法:

  1. 验证参数S和N的正确性
  2. 锯N-1次木头

在锯木头的时候,需要考虑可锯的长度

代码语言:javascript
复制
  /***
   * <p>
   * 随机产生和为sum(如10)的num(如5)个正整数
   * </p>
   * 
   * @param num 期望产生的随机数个数
   * @param sum 所有产生随机数的和
   * @return 返回满足和为sum的num个随机正整数组成的数组
   */
  public static int[] random2(int num, int sum) {

    /**
     * Step1: 验证参数正确性
     */
    if (num < 1) {
      throw new IllegalArgumentException("产生随机数个数的num不能小于1");
    }
    if (sum < num) {
      throw new IllegalArgumentException("产生随机数个数的num不能大于和sum");
    }
    if (sum <= 0) {
      throw new IllegalArgumentException("sum需要为正整数");
    }

    /**
     * 如果只有一个 直接返回
     */
    if (num == 1) {
      return new int[] { sum };
    }

    /**
     * Step2: 锯木头的方法
     */

    Random rand = new Random();

    int[] randomNumbers = new int[num];

    // 剩余数
    int remainingNum = sum;
    for (int i = 0; i < num - 1; i++) {
      /**
       * 可以锯掉可选值 remaining - (num - (i+1)) + 1 = remainingNum - num + i + 1
       */
      int randNum = rand.nextInt(remainingNum - num + i + 1) + 1;
      remainingNum -= randNum;
      randomNumbers[i] = randNum;
    }

    /**
     * 最后一个直接赋值即可
     */
    randomNumbers[num - 1] = remainingNum;

    return randomNumbers;
  }

最後,來測試一下~ 随机产生和为20的6个正整数

代码语言:javascript
复制
  public static void main(String[] args) {

    int num = 6;
    int sum = 20;
    System.out.println(String.format("随机产生和为%d的%d个正整数\n", sum, num));
    for (int i = 1; i <= 10; i++) {
      System.out.println(String.format("第%d遍random()产生结果 -- %s", i, Arrays.toString(random(num, sum))));
    }
    System.out.println();

    for (int i = 1; i <= 10; i++) {
      System.out.println(String.format("第%d遍random2()产生结果 -- %s", i, Arrays.toString(random2(num, sum))));
    }
  }

随机产生和为20的6个正整数

第1遍random()产生结果 -- [1, 3, 7, 1, 2, 6] 第2遍random()产生结果 -- [6, 4, 1, 5, 1, 3] 第3遍random()产生结果 -- [10, 2, 5, 1, 1, 1] 第4遍random()产生结果 -- [4, 1, 5, 4, 3, 3] 第5遍random()产生结果 -- [1, 10, 2, 1, 4, 2] 第6遍random()产生结果 -- [7, 3, 1, 2, 3, 4] 第7遍random()产生结果 -- [3, 4, 4, 7, 1, 1] 第8遍random()产生结果 -- [9, 3, 3, 2, 2, 1] 第9遍random()产生结果 -- [2, 5, 10, 1, 1, 1]

第10遍random()产生结果 -- [1, 1, 2, 2, 3, 11]

第1遍random2()产生结果 -- [9, 3, 5, 1, 1, 1] 第2遍random2()产生结果 -- [3, 9, 3, 1, 1, 3] 第3遍random2()产生结果 -- [15, 1, 1, 1, 1, 1] 第4遍random2()产生结果 -- [2, 14, 1, 1, 1, 1] 第5遍random2()产生结果 -- [10, 4, 1, 3, 1, 1] 第6遍random2()产生结果 -- [3, 2, 6, 2, 3, 4] 第7遍random2()产生结果 -- [11, 2, 2, 2, 1, 2] 第8遍random2()产生结果 -- [5, 7, 5, 1, 1, 1] 第9遍random2()产生结果 -- [3, 13, 1, 1, 1, 1] 第10遍random2()产生结果 -- [1, 11, 5, 1, 1, 1]

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 孟君的编程札记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档