phpstudy集成环境

 首页 > 算法问题：把一个数分成m个数，有且仅有一个最大数

算法问题：把一个数分成m个数，有且仅有一个最大数

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

下面详细描述一下题目：

有一个整数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;i<mNum;i++) {
        if(i == mNum-1) {
            var rad = nNum - currentNum;
            if(rad == bestNum) {
            } else {
                arrList.push(rad);
            }
        } else {
            var min = (nNum - currentNum) - (mNum-1-i)*(bestNum-1);
            if(min<0) {
                min = 1;
            }
            var max = bestNum-1;
            if(nNum - currentNum - (mNum-1-i) < bestNum) {
                max = nNum - currentNum - (mNum-1-i);
            }
            var rad = Math.round(Math.random()*(max-min))+min;
            currentNum += rad;
            if(currentNum>nNum) {
                currentNum -= rad;
                i--;
                continue;
            } else {
                arrList.push(rad);
            }
        }
    }
    console.log(arrList);
}

个人算法能力薄弱，见谅

最大数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]

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

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

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

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

https://jsfiddle.net/hsfzxjy/aevc56ts/2/

function random (min, max) {
    if (min >= max) return max;
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function split (n, m, result) {
    if (m === 1) {
      result.push(n);
    return;
  }
  
  let num = random(1, n - m + 1);
  result.push(num);
  split(n - num, m - 1, result);
}

function ran (n, m) {
    let result = [];
  split(n, m, result);
  result.sort((a, b) => (b - a));
  if (result[0] === result[1]) {
      result[0] ++;
    result[1] --;
  }
  return result;
}

其实并不是真正的随机，每种情况概率并不相等

---Update---

另一种实现，相对均匀： https://jsfiddle.net/hsfzxjy/f5r50zr4/4/

function random (min, max) {
  // 从闭区间[min, max]随机取整数
  if (min >= max) return max;
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function selectANumber (arr) {
  // 从数组 arr 中随机选一个数，删除并返回
  let index = random(0, arr.length -1);
  return arr.splice(index, 1)[0];
}

function ran (n, m) {
  // 核心思想：从1～n-1中随机取出m-1个数来
  let indices = [], selected = [0, n];
  let i;
  
  for (i = 1; i < n; ++i) indices.push(i); // 初始化为 0~n-1
  
  for (i = 1; i < m; ++i) selected.push(selectANumber(indices));
  
  selected.sort((a, b) => (a - b));
  
  let result = [];
  
  // 构造答案
  for (i = 1; i < selected.length; ++i) 
    result.push(selected[i] - selected[i - 1]);
    
  result.sort((a, b) => (b - a));
  
  // 调整最大数
  if (result[0] === result[1]) {
    result[0] ++;
    result[1] --;
  }
  
  return result;
}

基本思路：将 n 分成 m 份，等价于 将 n 个球排成一排，在空隙中插入 m-1 个隔板

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;
  }
}
【热门文章】
【热门文章】