时间戳

首页 > 解决方案 > 分区 N，其中零件的数量和每个零件都是 2 的幂，并且零件大小和数量受到限制

javascript - 分区 N，其中零件的数量和每个零件都是 2 的幂，并且零件大小和数量受到限制

问题描述

您如何获取表示项目列表的数字，并将其划分为块，其中块的数量是 2 的幂，并且每个块也具有 2 的项目数（其中大小最大功率为 2，所以 1、2、4、8、16、32、32 是最大值）？这甚至可能吗？

因此，例如，8 个项目可以分为 1 个桶（两个桶的幂）和 8 个项目（两个项目的幂）：

[8]

9 项可能是：

[8, 1]

这是有效的，因为这两个数字都是 2 的幂，并且数组的大小是 2（也是 2 的幂）。

让我们试试 11：

[8, 2, 1]

不，那是行不通的。因为数组的大小是 3，它不是 2 的幂，即使它加到 11。这个怎么样？

[4, 4, 2, 1]

这样可行！它是 4 个元素，是 2 的幂。

[2, 2, 2, 1, 1, 1, 1, 1]

这也有效，因为有 8 个桶（8 是 2 的幂），每个桶有 1 或 2 个项目（每个是 2 的幂）。但[4, 4, 2, 1]更好，因为它更短。

我想一个更好的（在得到评论之后）会是这样，虽然我第一次没有看到它：

[8, 1, 1, 1]

那个很短，也是从最大的数字开始的。

所以按照这个模式，这里有一些其他的数字：

13：

[8, 1, 1, 1, 1, 1] // no, 6 not power of 2
[8, 2, 1, 1, 1] // no, 5 not power of 2
[8, 2, 2, 1] // yes, 4 is power of 2
[8, 4, 1] // no, 3 not power of 2

14:

[8, 2, 2, 2]

15：

[8, 4, 2, 1]

16：

[16]

18:

[16, 2]

200：

[32, 32, 32, 32, 32, 32, 4, 4]

当桶树中第一层桶的大小增长到大于 32 时，就进行嵌套。以数字 1234 为例。这可以用 38 个 32 后跟 16 后跟 4 来表示。

[32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 16, 4]

但是现在桶大小是 40 个项目长，不是 2 的幂并且大于 32。所以它应该是嵌套的！我无法在脑海中完全想象这一点，很抱歉，如果这不是一个完美的例子，我想你可以明白我的意思。

// the parent "x" is 2 in length
x = [a, b]
// child "a" is 32 in length
a = [32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32]
// child "b" is 8 in length
b = [32, 32, 32, 32, 32, 32, 16, 4]

再上一层，假设我们有一个非常大的数字（我不知道最小的大数字是多少）需要另一层嵌套。关于这一层，我们可以说的是，x长度为 32，但我们也将有一个y至少为 1 的层。

_x_ = [a, b, c, d, e, f, g, h,
       i, j, k, l, m, n, o, p,
       q, r, s, t, u, v, w, x,
       y, z, a2, b2, c2, d2, e2, f2]
_y_ = [a3]
a   = [32, 32, 32, ..., ?]
...
f2   = [32, ..., ?]

然后，一旦我们拥有_x_, _y_, _z_, ... 总共 32 个这些, 我们在顶部构建另一个层。

什么是算法/方程式，它将采用一个数字并将其划分为这棵桶/项目大小的树，这些树都是 2 的幂，最大（在本例中为 32）？

一个子目标是最小化级别的数量。没有具体的限制，但我想在整个运行时不超过 100 万或最多 10 亿个节点，所以看起来你可能只有 3 或 4 个级别，我不知道具体如何计算它。

这将用于数组查找。本质上，我将一个单一的、大的、任意大小的“连续”数组分解为大小为 2 的幂的连续小块，最长可达 32。这平衡了查找性能（即适合 cpu 缓存）和内存碎片。

更新：

我认为尝试以某种方式将其合并以构建我要描述的嵌套树会有所帮助。现在缺少的最后一件事是将嵌套数组的大小正确调整为两个值的幂......

到目前为止，我能做的最好的是：

console.log(spread(74))
console.log(spread(85))
console.log(spread(87))
console.log(spread(127))
console.log(spread(1279))
console.log(spread(12790))
console.log(spread(127901))

function spread(n) {
  if (n == 0) {
    return [0, 0, 0, 0, 0, 0]
  }
  let array = []
  let r = split(n)
  while (r[0] > 31) {
    array.push([32, 0, 0, 0, 0, 0])
    r[0] -= 32
  }
  array.push(r)
  let s = sum(r)
  if (!isPowerOf2(s)) {
    let x = pow2ceil(s)
    let i = 1
    while (i < 5) {
      if (r[i] > 1) {
        i++
        break
      }
      i++
    }
    if (i == 5) {
      i = 0
    }
    main:
    while (true) {
      while (r[i]) {
        r[i + 1] += 2
        r[i]--
        s += 1
        if (s == x) {
          break main
        }
      }
      i++
    }
  }

  if (array.length == 1) {
    return array[0]
  } else if (array.length < 33) {
    return array
  } else {
    return divide(array, 32)
  }
}

function sum(arr) {
  let i = 0
  arr.forEach(x => {
    i += x
  })
  return i
}

function split(n) {
  const r = [0, 0, 0, 0, 0, 0]
  let u = 32
  let i = 0
  while (u > 0) {
    while (n >= u) {
      r[i]++
      n -= u
    }
    i += 1
    u >>= 1
  }
  return r
}

function isPowerOf2(v) {
  return v && !(v & (v - 1))
}

function pow2floor(v) {
  var p = 1;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function pow2ceil(v) {
  var p = 2
  while (v >>= 1) {
    p <<= 1
  }
  return p
}

function divide(data, size) {
  const result = []
  const upSize = data.length / size;

  for (let i = 0; i < data.length; i += size) {
    const chunk = data.slice(i, i + size);
    result.push(chunk)
  }

  if (result.length > size) {
    return divide(result, size)
  }

  return result;
}

标签： javascriptarraysalgorithmmathbinary

解决方案

总是有可能的。

从正常的二进制表示开始。

您会得到许多都是 2 的幂的和数。

所以问题是求和数大多数时候不是二的幂。

您总是可以通过将 2 的幂除以 2 的求和（也是 2 的幂）来获得额外的求和。唯一的例外是 1。

所以问题是存在没有足够的 summand > 1 的情况？

答案：没有

最坏的情况是我们有 n 个被加数，其中 n 是（2 的幂）-1。例如 3, 7,15, ... 我们是否有 3 和最小可能的情况是 1+2+4。我们需要 4 个被加数，所以我们必须通过将一个 >1 的被和数一分为二来创建 1 个额外的被加数。例如 1+1+1+4。

对于较大的值，最高和数始终 >= ceeling(value/2) 并且在二进制表示中最多具有 ceeling(sqrt(value))+1 个和数。

ceeling(value/2) 的增长速度比 sqrt(value) 快得多。

因此，随着值的增加，我们总是有大量的加法可以拆分以达到 2 次加法目标的幂。

示例： value= 63
二进制表示：32+16+8+4+2+1 （6 个被加数）
最高被加数是 32（至少 value/2）（可以拆分为任意数量的被和（所有 2 的幂），最多 32 个被和。

我们最多需要ceeling(sqrt(63))+1 = 8个被加数才能达到 2 个被加数的幂。

所以我们需要 2 个额外的求和32+16+8+4+2+1

取任何大于 1 的被加数并将其分成两个被和数（2 的幂），例如32 = 16+16
=> 16+16+16+8+4+2+1（7 个被数）
再做一次（因为我们需要 2 个额外的被数）。取任何 >1 例如 4 并拆分 ist 2+2=4
=> 16+16+16+8+2+2+2+1(8 summands)

推荐阅读