1

我必须找到一个递归函数，通过重复将数组划分为 2 个几乎相等的部分来找到数组的总和？

我的方法应该是什么？我该怎么做？

我不要求代码！只是解决此问题的提示或方向！

4

6 回答 6

6

这相当容易。数据集上的每个递归算法都应该根据相同的算法(a)在更简单的数据集上定义，并具有终止条件。

在这种情况下，终止条件是一个大小为 1 的数据集，您只需返回值，否则每个递归级别只是在两半上执行相同的任务，然后将两个结果加在一起。

这将类似于以下伪代码：

def sumof (array, start, end):
    if start == end:
        return array[start]
    midpoint = (start + end) / 2
    return sumof (array, start,        midpoint) +
           sumof (array, midpoint + 1, end     )

现在您所要做的就是将其转换为您选择的语言并在边缘情况下调试任何潜在问题。

让我们看看它是如何在一个零索引、七元素数组中的数字 10 到 16 上工作的。如果你通过你的头脑运行该算法，或者如果你还没有像我一样变得比人更机器的话，或者在纸上运行该算法:-)，你会得到这样的东西：

Level 0, call sumof (array, 0, 6):
    Level 1, call sumof (array, 0, 3)
    +---Level 2, call sumof (array, 0, 1)
    |   +---Level 3, call sumof (array, 0, 0), returns 10
    |   |---Level 3, call sumof (array, 1, 1), returns 11
    |   Add together to get 21
    |   Level 2, call sumof (array, 2, 3)
    |   +---Level 3, call sumof (array, 2, 2), returns 12
    |   |---Level 3, call sumof (array, 3, 3), returns 13
    |---Add together to get 25
+---Add together to get 46
|   Level 1, call sumof (array, 4, 6)
|       Level 2, call sumof (array, 4, 5)
|       +---Level 3, call sumof (array, 4, 4), returns 14
|       |---Level 3, call sumof (array, 5, 5), returns 15
|   +---Add together to get 29
|   |---Level 2, call sumof (array, 6, 6), returns 16
|---Add together to get 45
|
Add together to get 91

(a)情况并非总是如此，有时实际算法也会发生变化，但这种情况很少见。

于 2013-06-06T13:09:35.527 回答
2

这是一种“分而治之”的方法。在这里查看更多

于 2013-06-06T13:08:37.370 回答
1

这将是一个分而治之的算法：

  1. 创建一个将采用以下参数的函数：
    • 大批
    • 起始索引
    • 结束索引
  2. 当开始索引等于结束索引时，函数应该从数组中返回开始（或结束）索引位置的值
  3. 否则，它应该返回具有以下参数的同一函数的两次调用的总和：
    • 数组，开始索引，（开始+结束）索引/2
    • 数组，（开始 + 结束）索引/2+1，结束索引
于 2013-06-06T13:11:28.470 回答
1

有一种排序算法，它使用类似的原则进行分区排序http://www.algolist.net/Algorithms/Sorting/Quicksort

于 2013-06-06T13:14:49.430 回答
0

中调用如下函数C，如果原数组的大小为N，初始调用函数为，

sum=rec_sum(0,N-1);

功能如下图， 

int rec_sum(int array[],start,end)
{
   if(start==end)
   {
     return array[start];
   }
   else
   {  
       return rec_sum(array,start,(start+end)/2) + rec_sum(array,(start+end)/2+1,end);
   }
}
于 2013-06-06T13:18:41.733 回答
0

递归函数与divide-and-conquer技术高度相关。您应该关注的两个方面是

  1. 如何将大问题分解成更小的易于解决的问题；
  2. 如何将所有小问题的解决方案合并为原始较大问题的解决方案。

当然，您可以将数组划分为两个大小相似的问题。下一步是如何合并结果。让我们看看你的努力：p。

于 2013-06-06T13:09:59.303 回答