javascript - 算法问题:把一个数分成m个数,有且仅有一个最大数
大家讲道理
大家讲道理 2017-04-10 17:06:56
[JavaScript讨论组]

今天写一个游戏的时候遇到了这么一个算法问题,因为觉得自己写的算法不是很好,又想不出其他解法,想来求助一下。

下面详细描述一下题目:

有一个整数n,分成m个整数(m个整数之和等于n),m个整数中有且仅有一个最大数且都不为0。返回一个组合即可,但是该组合应该是所有组合里随机的一个。
eg:

n=4,m=2, 分解后整数为 3,1
n=9,m=2, 分解后整数为 8,1或7,2或6,3或5,4

下面是我的代码(js):

function ran(nNum,mNum) {
    var m = nNum - mNum + 1;
    var n = nNum%mNum == 0?nNum/mNum+1:Math.ceil(nNum/mNum);
    var bestNum = Math.floor(Math.random()*(m-n)+n);
    var currentNum = 0;
    var arrList = [];
    arrList.push(bestNum);
    currentNum+=bestNum;
    for(var i=1;inNum) {
                currentNum -= rad;
                i--;
                continue;
            } else {
                arrList.push(rad);
            }
        }
    }
    console.log(arrList);
}

个人算法能力薄弱,见谅

大家讲道理
大家讲道理

光阴似箭催人老,日月如移越少年。

全部回复(4)
阿神

大概有个思路:
生成一组m个随机数,并只有一个最大数
取得这组数的和sum,然后n/sum得到比例s
再把这组数都乘以s并取整

问题在取整后总和可能会小于n,或者是最大值和次大值差值很小时取整后可能会相等
对这两个情况特殊处理一下就可以了

因为生成随机数时不用考虑n,在生成完成后再用比例去缩放数值,所以随机性应该还可以
代码晚点看情况补上

PHPz

最大数max = n - m + 1,剩下的都为1,这样分可以吗?

function foo(n, m) { // 名字就不起了,就叫这个吧
    var average = Math.floor(n / m); // average >= 1
    var max = 0;
    var left = n;
    var arr = [];
    for (var i = 0; i < m; i++) {
        // 这里是关键,每次随机得到一个大于0的值,但必须确保余下的数足够剩下的元素分配
        // 一开始我使用的是 Math.random() * (left - (m - i - 1)),但是效果不好
        // 会导致随机性很差,大数都集中在前面的元素中,而后面的元素往往都是1
        // 这是由于最初的算法在开始时的随机空间很大,所以也容易得到较大的数的原因,而越到后面,剩下的可分配的值越小
        // 后来我改进了算法,加了一个average,用来平均每次的随机空间,测试下来效果挺不错
        arr[i] = i == m - 1 ? left
            : Math.floor(Math.random() * (left - (m - i - 1) * average)) + 1;
        left -= arr[i];
        if (arr[i] > arr[max]) {
            max = i;
        } else if (arr[i] == arr[max] && arr[i] >= average) { // 这里用来修正最大值,确保最大值的元素只有一个
            arr[i]--;
            arr[max]++;
        }
    }
    console.log(arr);
    return arr;
}

测试代码:

foo(4, 2);
foo(4, 2);
foo(4, 2);
foo(8, 3);
foo(8, 3);
foo(8, 3);
foo(8, 3);
foo(20, 7);
foo(20, 7);
foo(20, 7);
foo(20, 7);
foo(20, 7);
foo(20, 7);
foo(20, 7);

下面是某一次测试的结果:

[3, 1]
[1, 3]
[1, 3]
[4, 2, 2]
[3, 1, 4]
[4, 2, 2]
[4, 2, 2]
[1, 2, 4, 2, 6, 1, 4]
[3, 6, 1, 4, 2, 1, 3]
[1, 1, 6, 5, 1, 2, 4]
[3, 4, 5, 1, 2, 3, 2]
[2, 8, 1, 3, 2, 2, 2]
[4, 1, 7, 1, 2, 2, 3]
[3, 1, 2, 4, 5, 2, 3]
PHP中文网
function ran(nNum, mNum) {
  var n = nNum - mNum;
  var maxNum = 1;
  var maxNumIndex = 0;
  var numArray = [];
  if (n > 0) {
    for (var i = 0; i < mNum - 1; i++) {
      numArray.push(getNum(i) + 1);
    }
    if (n === maxNum) numArray[maxNumIndex]--;
    numArray.push(n + 1);
    console.log(numArray);
  } else {
    console.log("unsolvable");
  }

  function getNum(i) {
    var m = Math.ceil(Math.random() * n);
    if (m === maxNum) {
      m = getNum(i);
    } else {
      n -= m;
      if (m > maxNum) {
        maxNum = m;
        maxNumIndex = i;
      }
    }
    return m;
  }
}
黄舟

先将n-1分隔成m个随机数,然后取其中最大值进行+1

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号