首页 > theory > algorithm > > 正文

js随机产生和为s的整数组

发布人:zhoulujun    点击:

js生成n个和为固定sum的随机整数functionrandomInt(sum,num){letresult=[],reside=sum,tempSum=0;for(leti=0;i<num-1;i++){lettemp=Math ce

js生成n个和为固定sum的随机整数

function randomInt(sum,num) {
    let result=[],reside=sum,tempSum=0;
    for(let i=0;i<num-1;i++){
        let temp=Math.ceil(Math.random()*(reside/2));
        result.push(temp);
        console.log(reside);
        reside-=temp;
        tempSum+=temp;
        console.log("temp:"+temp+"reside:"+reside+"tempSum:"+tempSum+"sum:"+sum+"\n")
    }
    result.push(sum-tempSum);
    return result;

}

这个是随便写,但是,并不靠谱

随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。

以生成和为20的4个数为例,可以先生成随机生成0到20之间的三个数字再排序,假设得到了4,7,18。然后在X-Y数轴上画出这三个数,如下图:


3133209-0b1ee250d6f717ac.png

3133209-7dae856f7f38ed5e.png

由图很容易看出AB,BC,CD,DE这四段的长度和肯定为20。因此AB,BC,CD,DE这四段的长度即和为20的4个数,这4个数分别为4,3,11,2。


这种方法只要随机生成N - 1个小于S的不同数字,排序后计算两两差值就可以得到和为S的N个正整数,因此效率还是比较高的。下面给出完整代码:



java算法:

import java.util.Arrays;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
/**
 * <p>
 * 类RandomUtils中提供了一个方法用于随机产生和为S的N个正整数。
 * </p>
 * 
 * 思路:
 *    第一步:把和为S的数值看做是一把尺子的长度,比如S等于20.那么随机产生和为S的N个整数的问题
 *       就变成了在0~20之间产生N-1不同的刻度。这样的话,尺子就被不同的刻度分割成了N段。
 *    第二步:从左到右,计算出每一段的长度,每一段的长度就可以看做是随机数。N段就有了N个随机数。
 * 
 * @author Eric
 * @version 1.0
 * 
 */
public class RandomUtils {
 public int[] generateRandomArray(int expectedSum, int expectedNum) {
  /**
   * 为了获取不同位置的刻度,用TreeSet来做处理,set中的内容能够排序。
   */
  Set<Integer> set = new TreeSet<Integer>();
  set.add(0);
  set.add(expectedSum);
  Random random = new Random();
  while (set.size() < expectedNum + 1) {
   set.add(random.nextInt(expectedSum - 1) + 1);
  }
  Integer[] locations = new Integer[set.size()];
  set.toArray(locations);
  int[] result = new int[expectedNum];
  /**
   * 计算相邻刻度之间的长度,得到的数值就可以认为是随机数:
   */
  for (int i = 0; i < result.length; i++) {
   result[i] = locations[i + 1] - locations[i];
  }
  Arrays.sort(result);
  return result;
 }
 /**
  * 打印结果
  */
 private void printArray(int[] data) {
  for (int i : data) {
   System.out.print(i);
   System.out.print(" ");
  }
  System.out.println();
 }
 public static void main(String[] args) {
  RandomUtils util = new RandomUtils();
  System.out.println("随机产生和为30的5个正整数如下:");
  util.printArray(util.generateRandomArray(30, 5));
 }
}

参考文章:

https://www.jianshu.com/p/4673fbdd497f

http://mouselearnjava.iteye.com/blog/1858970