用java怎样将一个正整数L随机拆分成N个正整数?

Alittle 发布于 2015/01/05 14:44
阅读 4K+
收藏 0
要求:拆分后的n个整数之和等于L;
如100,要求拆分成5个数值,则可能为 [1 , 80, 10, 1, 8]....
加载中
0
麻美学姐
麻美学姐
用随机种子,从(0,n]中随机一个int值,然后作减法,则得到俩个int值x,n-x,然后再从其中一个数中再 取(0,x]或者(0,n-x]取一个随机数,再作减法。反正随机出5个数就行了。
麻美学姐
麻美学姐
回复 @Alittle : 如果想考虑效率的话,我不太会算法的,就没办法想了~~~
麻美学姐
麻美学姐
回复 @Alittle : 第二次的300和700 也能再一次随机吧。就(0,1]两个数嘛。全部都可以随机,第一次300,然后random到 0-700,然后出个500,就比300大了嘛,。就是200 300 500 的。。然后再random 0-2,又出一个。
Alittle
Alittle
回复 @Alittle : 比如拆分一个1000,第一次是【0-1000】,可能得到300,然后第二次【0,700】......值得随机分布不好保证是“随机”的。
Alittle
Alittle
可是这样做存在一个问题,就是越到后面的值越小,这个违背了“随机”的初衷了
0
bronze
bronze
Random random = new Random();
        //拿到四个随机数,可以做个池什么的每次取四个来提升效率
        List<Double> r = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            r.add(random.nextDouble());
        }
        //排序
        r.sort(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                return o1 < o2 ? -1 : 1;
            }
        });
        //用这四个随机数来打断一个数,来取得五份分解之后的数
        int num = 100;
        List<Integer> out = new ArrayList<>();
        int last = 0;
        for (int i = 0; i < 4; i++) {
            int c = (int) (r.get(i) * num);
            out.add(c - last);
            last = c;
        }
        out.add(num - last);
        System.out.println(out);

也许还存在些小问题,你写个测试用例什么的仔细测下。


OSCHINA
登录后可查看更多优质内容
返回顶部
顶部