根据需求自然数分割阵列

我有两个自然数数组{A_i}和{B_i}。所有元素的总和是相等的。根据需求自然数分割阵列

我需要两个阵列中的每个元素分成三个自然数：

A_i = A1_i + A2_i + A3_i B_i = B1_i + B2_i + B3_i

使得A1中的所有元素的总和等于B1的所有元素的总和与对于所有其他对都是一样的。

我最初忘了最重要的部分：

每个元件从A1 _Ĵ，A2 _Ĵ，A3 _Ĵ应该是A _Ĵ/3-2和A _Ĵ之间/3 + 2或至少等于其中一个号码

从B1 _Ĵ，B2 _Ĵ，B3每个元素Ĵ应/3 + 2或至少等于这些数字

所以阵列的元件必须在分割几乎相等的部分

之一乙 _Ĵ/3-2和B _{Ĵ之间我寻找一些更优雅的解决方案，而不仅仅是计算两个阵列的所有可能的变体。}

来源

2013-08-23 Igor Traskunov

将A复制到A1。将B复制到B1。将A2，A3，B2和B3中的每个元素设置为零。也许你有一个要求被省略了？ –

@EricPostpischil哈哈这是模范：D – gen

哎呀！我做了一些更新。所以不是那么简单;） –

您应该查看dynamic programming的原理。

在这种情况下，它似乎类似于一些coin change problems。

至于寻找A1_i，A2_i，A3_i你应该这样做递归：

def find_numbers(n, a, arr): 
    if arr[n] not empty: 
     return 

    if n == 0: 
     arr[n].append(a) 
     return 

    if a.size() > 2: 
     return 
    t = n 

    for each element of a: 
     t -= element 

    for i = 0 to : 
     find_numbers(n, append(a, i), arr)

我们使用arr，使我们并不需要多次计算每个数字可能的组合。如果您在一段时间后查看调用树，该函数将返回arr中的组合，而不是再次计算它们。在你的主电话：

arr = [] 
for each n in A: 
    find_number(n, [], arr) 
for each n in B: 
    find_number(n, [], arr)

现在，你必须在ARR [N]每个n所有组合。我知道这是问题的一个子部分，但是从arr中为每个A_i，B_i找到正确的组合与此非常相似。 >阅读我给你的链接非常重要，这样你才能理解背后的基本理论。

来源

2013-08-23 15:54:45 gen

这段代码应该做什么？对于数组中的每个值，找出其总和就是那个值的每个三元组？这很容易迭代完成，不需要浪费递归。它在解决问题中提出的问题有什么用处？ –

@EricPostpischil是的，它的递归很好地转化为迭代，但是我正在向asker展示这个概念如何处理这样的问题。 OFC迭代更有效，但是： 1.这并不重要，提问者可以改变它，2.它有助于他理解我们如何处理它。我为什么寻找组合？因为从这个角度他可以着手解决整个问题。其他的东西：我认为你不应该因为它不仅仅是从另一个复制另一个，而是更相关的东西，它是一个独立的anwser。 – gen

这个答案没有帮助解决问题。 –

我寻找一些更优雅的解决方案，而不仅仅是计算两个阵列的所有可能的变体。

应该可以将它们分开，使得A1，A2和A3的总和接近A的三分之一，B的总和也是一样。只需使所有的值精确到三分之一就容易了，但对于自然数来说这是不可能的。所以我们必须floor结果（微不足道），并将余数均匀分布在三个数组（可管理）上。

我不知道它是否是唯一的解决办法，但它工作在O(n)和我的直觉说，它将把你不变（虽然我没有证据吧）：

n = 3 
for j=0 to n 
    A[j] = {} 
x = 0 // rotating pointer for the next subarray 
for i in A 
    part = floor(A[i]/n) 
    rest = A[i] % n 
    for j=0 to n 
     A[j][i] = part 

    // distribute the rest over the arrays, and rotate the pointer 
    for j=0 to rest 
     A[x][i]++ 
     x++ 

/* Do the same for B */

人们还可以制定不分割的循环，仅分配的A [I]（1）单个单元在A [X] [I] S：

n = 3 
for j=0 to n 
    A[j] = {} 
    for k=0 to |A| 
     A[j][i] = 0 
x = 0 // rotating pointer for the next subarray 
for i in A 
    // distribute the rest over the arrays, and rotate the pointer 
    for j=0 to A[i] 
     A[x][i]++ 
     x++

来源

2013-08-23 16:49:58 Bergi

这很简单。但是每个新数组A1，A2，A3的元素总和必须完全等于它们的“兄弟”B1，B2，B3的元素总和。 –

你试过了吗？我相信它是有效的 - 看看底部的实现（手动进行分割） - A [x]的总和不断地以旋转的方式增加。由于| A | = | B |和（A）=和（B）部分数组也应该具有相同的和。 – Bergi

@EricPostpischil：不用，'x'是全局的，每个循环都不会用0重新初始化。它应该把A1 = [1,0] A2 = [0,1] A3 = [0,0] – Bergi

我添加规定，即A1，A2，和A3绝从A计算而不知道B，并且类似地，B1，B2和B3必须不计算A的知识

每个A1 _我，A2 _我，A3 _我必须在[A _我/3-2，A _我/3 + 2]意味着要求A1，A2和A3的元素总和必须大约为A的三分之一。该规定迫使我们完全定义这一点。

我们将以任何顺序构造数组（例如，从元素0到最后一个元素）。在我们这样做的时候，我们将确保阵列保持接近平衡。

设x是要处理的A的下一个元素。让一个圆（x/3）。为了解释x，我们必须将总数3•a + r附加到数组A1，A2和A3，其中r是-1,0或+1。设D为总和（A1） - 总和（A）/ 3，其中总和是到目前为止处理的元素的总和。最初，d是零，因为没有处理元素。按照设计，我们将确保d在每一步中为-2/3,0或+2/3。

追加如下图所示，A1，A2，和A3，分别三个值：

如果r -1和d是-2/3，附加一个+ 1，A-1，A- 1。这会将d更改为+2/3。
如果r为-1且d为0，则追加a-1，a，a。这将d更改为-2/3。
如果r是-1并且d是+2/3，则追加a-1，a，a。这将d更改为0.
如果r为0，则附加a，a，a。这保持不变。
如果r是+1且d是-2/3，则追加a + 1，a，a。这将d更改为0.
如果r是+1且d是0，请附加a + 1，a，a。这会将d更改为+2/3。
如果r是+1并且d是+2/3，则追加a-1，a + 1，a + 1。这将d更改为-2/3。

最后，A1，A2和A3的总和由A模3的和唯一确定。根据A模3的和是否与-1等于0，A1的和为（和（A3）-2）/ 3，和（A3）/ 3或（和（A3）+2）/ 3 ，或+1。

完成示范：

在任何情况下，A-1，A或A + 1被附加到阵列。a是圆的（x/3），所以它与x/3的差值小于1，所以a-1，a和a + 1的每一个都与x/3的差值小于2，满足值必须[A _i/3-2，A _i/3 + 2]。

当以与上面针对A1，A2和A3所示相同的方式准备B1，B2和B3时，它们的总和由B3的总和确定。由于A的总和等于B的总和，因此A1，A2和A3的总和分别等于B1，B2和B3的总和。

来源

2013-08-23 17:32:53

为什么这会降低投票率？ – Bergi

根据需求自然数分割阵列

回答

相关问题