如何在不实际进行除法的情况下获得将数组划分为树所生成的数组数？ [英] How to get the number of arrays generated by dividing an array into a tree, without actually doing the division?

问题描述

假设我们有一个大小为 n 的数组，并且我们在概念上通过 divide 函数使用 size == 5 ，如 divide（array_of_size_n，5）：

Assume we have an array of size n, and we conceptually run it through this divide function with size == 5, as in divide(array_of_size_n, 5):

function divide(data, size) {
  const result = []

  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;
}

这将生成一个 tree ，其中每个节点不大于5

This will generate a tree where each node is no larger than 5 items in length.

问题是，它创建了多少个数组，而没有实际运行 divide 函数并创建数组？什么是方程，它可以为您提供要计算的数组数量，如 getNumArrays（n）一样？有没有一种方法可以实现独立于 n 大小的算法？如何将其概括化，以使每个数组最多有 m 个数组，而不是每个数组最多5个项目？

The question is though, how many arrays does it create, without actually running the divide function and creating the arrays? What is the equation that will give you the number of arrays that would get computed, as in getNumArrays(n)? Is there a way to do this with an algorithm that is independent of the size of n? How can you generalize it to make it so instead of 5 items max per array, there were m items max per array?

这里是我试图通过...

Here is me trying to think it through...

所以我有兴趣让它在32号阵列上工作。

So I am interested in getting this to work on arrays size 32.

因此，首先，您填充一个32个项目的数组。然后，这将导致上面的一个出现，现在仅在其中填充第一个广告位/子项（旧的32个项目的数组）。然后，我们可以再添加31个32项数组。因此32 * 32项。然后，这会导致上面的另一个级别出现，我认为 遵循相同的模式，所以32 * 32 * 32 ....嗯...至少可以告诉我们

So first, you fill up a 32-item array. Then this causes one above to appear, where now only it's first slot/child (the old 32-item array) is filled. Then we can add 31 more 32-item arrays. So 32 * 32 items. This then causes another level above to appear, which I think follows the same pattern, so 32 * 32 * 32.... Hmm... That tells us at least how many levels there are.

那是什么意思，也就是说，我们转到路径 2/2/2 ：

So does that mean, say we go to the path 2/2/2:

32^(3-1) + 2
+ 32^(2-1) + 2
+ 32^(1-1) + 2
= 1026 + 34 + 2 = 1062 is the index?

现在我想找到相反的地方...

Now I'm interested to find the reverse...

1026 = size^(depth - 1) + x
     + size^(depth - 2) + y
     + size^(depth - 3) + z

现在我迷路了。

推荐答案

所以递归函数是：

f(n,m) = ceil(n/m) + f( ceil(n/m), n) 

计算具有地板和天花板的递归函数的精确封闭式解决方案并非易事（至少对我而言不是） :-)）。我们可以像这样为它创建一个简单的递归函数，它比用数组模拟和整数除法更快。

Computing exact closed form solutions of recursive functions with floor and ceilings isn't trivial (at least not to me :-) ). We can create a simple recursive function for it like this, it is faster than simulating with arrays as is simply integer division.

def f(n, m):
    if ceil(n/m) <= m:
        return ceil(n/m)
    return ceil(n/m) + f(ceil(n/m),m)

（我想这可以通过一个简单的while循环来加快。）

(this can be made faster by just a simple while loop i guess.)

一些结果：

f(25,5) = 5   # 25 elements grouped into exactly 5 arrays

f(26,5) = 8   # 25 elements grouped into 6 arrays, which again are grouped into two arrays

级别数将为log_m（n），在每个级别上，元素数减少m倍。

The number of levels will be log_m(n), at each level the number of elements are reduced by a factor of m.

这篇关于如何在不实际进行除法的情况下获得将数组划分为树所生成的数组数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！