I'm trying to come up with a divide-and-conquer algorithm for finding the minimum element in an array but recursive code is a bit mind bending to me.
我正在尝试用一种分而治之的算法来查找数组中的最小元素，但递归代码对我来说有点让人头疼。
For example, taking the following pseudo code:
例如，采用以下伪代码：
procedure R_MIN (A, n)
begin
if (n = 1) then
min := A[0];
else
lmin := R_MIN (A, n/2);
rmin := R_MIN (&(A[n/2]), n - n/2);
if (lmin < rmin) then
min := lmin;
else
min := rmin;
endelse;
endelse;
return min;
end R_MIN
The way I understand it is we split the array in half, unless we have the base case. Then we figure out which half has the min and repeat the call, further splitting it (now we have 4 arrays). But where and how is the min actually found and what would this code look like in C? It seems to me this would only work when we have split into pairs.
我理解它的方式是我们将数组分成两半，除非我们有基本情况。然后我们找出哪一半有min并重复调用，进一步拆分它（现在我们有4个数组）。但是实际找到min的位置和方式以及C中的代码是什么样的？在我看来，这只有在我们分成两对时才有效。
2 个解决方案
#1
1
It finds the minimum from the previous recursive calls on the left and right halves of the array. When the base case is reached and the array has length 1, then that is the minimum of that sub-array of length 1. This minimum is then taken and compared with the minimum of the other half. The lower of the two is the minimum of this sub-array. This is returned to be compared and so on...
它从数组的左半部分和右半部分的先前递归调用中找到最小值。当达到基本情况并且数组的长度为1时，那么这是长度为1的子数组的最小值。然后获取该最小值并将其与另一半的最小值进行比较。两者中的较低者是该子阵列的最小值。返回进行比较等等......
If you translate the pseudo-code to C:
如果您将伪代码转换为C：
#include <stdio.h>
int rec_min(int A [],int len)
{
int min,lmin,rmin;
if(len==1)
return A[0];
else
{
lmin=rec_min(A,len/2);
rmin=rec_min(A+len/2,len-len/2);
if(lmin<rmin)
return lmin;
else
return rmin;
}
}
int main()
{
int test [10]={3,2,7,4,5,8,1,9,6,10};
printf("%d\n",rec_min(test,10));
return 0;
}
#2
1
Recursion is usually better understood from taking a bit of distance. You need to find the minimum in the array. If you split the big array in two halves, the minimum would be the minimum of each half minimum. That's the key concept here. And that's exactly what the code does. It's natural to wonder how this "magic" happens and the dwelling into it can be not so easy. However, it's not needed in most cases. Under the hood the principle of splitting into two halves is repeated without any additional intervention (that's the point of recursion - calling the same code again and again). And it stops at the base case - when there is only one number left so the minimum is the number itself (it could've been written to stop when 2 numbers are left, like you noted - but that's not needed and would force to do an explicit compare as the last step, adding complexity to the code).
通过一点距离通常可以更好地理解递归。您需要在数组中找到最小值。如果将大阵列分成两半，则最小值将是每半个最小值的最小值。这是关键概念。而这正是代码的作用。很自然地想知道这种“神奇”是如何发生的，并且居住它可能并不那么容易。但是，在大多数情况下并不需要它。在引擎盖下，重复分成两半的原则，无需任何额外的干预（这是递归的点 - 一次又一次地调用相同的代码）。它停在基本情况下 - 当只剩下一个数字时，最小值就是数字本身（它可能被写为在剩下2个数字时停止，就像你指出的那样 - 但这不是必需的并且会强制做显式比较作为最后一步，增加了代码的复杂性）。
#1
1
It finds the minimum from the previous recursive calls on the left and right halves of the array. When the base case is reached and the array has length 1, then that is the minimum of that sub-array of length 1. This minimum is then taken and compared with the minimum of the other half. The lower of the two is the minimum of this sub-array. This is returned to be compared and so on...
它从数组的左半部分和右半部分的先前递归调用中找到最小值。当达到基本情况并且数组的长度为1时，那么这是长度为1的子数组的最小值。然后获取该最小值并将其与另一半的最小值进行比较。两者中的较低者是该子阵列的最小值。返回进行比较等等......
If you translate the pseudo-code to C:
如果您将伪代码转换为C：
#include <stdio.h>
int rec_min(int A [],int len)
{
int min,lmin,rmin;
if(len==1)
return A[0];
else
{
lmin=rec_min(A,len/2);
rmin=rec_min(A+len/2,len-len/2);
if(lmin<rmin)
return lmin;
else
return rmin;
}
}
int main()
{
int test [10]={3,2,7,4,5,8,1,9,6,10};
printf("%d\n",rec_min(test,10));
return 0;
}
#2
1
Recursion is usually better understood from taking a bit of distance. You need to find the minimum in the array. If you split the big array in two halves, the minimum would be the minimum of each half minimum. That's the key concept here. And that's exactly what the code does. It's natural to wonder how this "magic" happens and the dwelling into it can be not so easy. However, it's not needed in most cases. Under the hood the principle of splitting into two halves is repeated without any additional intervention (that's the point of recursion - calling the same code again and again). And it stops at the base case - when there is only one number left so the minimum is the number itself (it could've been written to stop when 2 numbers are left, like you noted - but that's not needed and would force to do an explicit compare as the last step, adding complexity to the code).
通过一点距离通常可以更好地理解递归。您需要在数组中找到最小值。如果将大阵列分成两半，则最小值将是每半个最小值的最小值。这是关键概念。而这正是代码的作用。很自然地想知道这种“神奇”是如何发生的，并且居住它可能并不那么容易。但是，在大多数情况下并不需要它。在引擎盖下，重复分成两半的原则，无需任何额外的干预（这是递归的点 - 一次又一次地调用相同的代码）。它停在基本情况下 - 当只剩下一个数字时，最小值就是数字本身（它可能被写为在剩下2个数字时停止，就像你指出的那样 - 但这不是必需的并且会强制做显式比较作为最后一步，增加了代码的复杂性）。