Tags标签 网战地图
当前位置: 主页 > 网页设计 > JavaScript >

拆分自然数:纯while实现(Part 2 - 实现)

2014-06-09 21:56 [JavaScript] 来源于:
导读:在拆分自然数:纯while实现 (Part 1 - 思路) 这篇文章里面,我提供了解答Jeff《编程小练习:拆分自然数》问题的一种解答思路,并且使用了两个例子来解释这种思

在拆分自然数:纯while实现 (Part 1 - 思路) 这篇文章里面,我提供了解答Jeff《编程小练习:拆分自然数》问题的一种解答思路,并且使用了两个例子来解释这种思路,不知道你是否已经成功利用这种思路解题了呢?

首先,这道题的搜索域是什么?那就是[min, min, min, ..., min]到[max, max, max, ..., max],或者是它的子集。就算你完全不懂算法,我相信你凭直觉也知道要在[min, min, min, ..., min]到[max, max, max, ..., max]之间搜索。因此,一个算法好不好,就看你能否有效缩小搜索域了。

在不缩小搜索域的情况下,你可以排列组合出搜索域内的所有可能性,逐一验证是否为所求解,这也就是Jeff的DoSimple示例所做的。接着,为了保持解的不重复性,你可能想到了有效解一定是一个不下降序列,因此对所有非不下降序列进行剪枝,这也就是Jeff的DoBetter示例所做的事情。然后,你需要把不下降序列中总和不等于 sum的情况给砍掉,这个剪枝就是最难的一个剪枝了,也就是DoBest所做的事情。

Jeff 在DoBest中的做法是,对于当前操作的第i位,求得itemMinInclusive与itemMaxInclusive,且 minInclusive <= itemMinInclusive <= itemMaxInclusive <= maxInclusive,其中[minInclusive, itemMinInclusive)和(itemMaxInclusive, maxInclusive]这两个区间的取值是无效的,只有[itemMinInclusive, itemMaxInclusive]区间的取值才是有效的。

dragonpig的展开采用了try方式的剪枝,虽然也把无效枝剪掉了,但在循环上还是要遍历到无效枝的首个无效节点,必须在上面try一下看返回false才剪掉,因此性能介于DoBetter与DoBest之间。徐少侠的展开进行了有效的剪枝,在时间复杂度上是与DoBest一致的,不过缓存数据占用空间为实际状态所需空间的3倍,这些空间其实是浪费掉的。我认为比较理想的做法是仅仅缓存sum值,而不缓存下界(即itemMinInclusive)与上界(即itemMaxInclusive),这样是保证性能的前提下最省空间的。至于为什么我说混存下界与上界没用,看一下我的写法就知道了:

function main(m, n, min, max) {
 var array = new Array(n);
 var i = 0;

 var write = function() {
   console.log(m + ' = ' + array.join(' + '));
 };

 var scan = function() {
   if (scan.start) {
    scan.start = false;
    scan.sum = 0;
   }
   scan.sum += array[i];
   return (array[i] > array[n - 1] - 2);
 };

 var step = function() {
  array[i]++;
  fill.sum = scan.sum - array[i];
  i++;
 };

 var fill = function() {
   while (i < n) {
    array[i] = Math.max((fill.sum - (n - i - 1) * max), ((i == 0) ? min : array[i - 1]));
    fill.sum -= array[i];
    i++;
   }
   i--;
 };

 fill.sum = m;
 fill();
 write();
 while (true) {
  scan.start = true;
  while (i >=0 && scan()) {
   i--;
  }
  if (i < 0) {
   break;
  }
  step();
  fill();
  write();
 }
}

(编辑:)

本文标签:
网友评论

栏目列表

推荐文章