0

我用java编写了一个分而治之的算法。问题是，我已经对其进行了测试，但我不确定它为什么或对数据做了什么。我知道它将数组拆分为子部分，但除此之外我很困惑他们返回的所有内容会发生什么。例如，最小的基本情况是否返回它的数字并进行比较？如果函数中有多个递归调用，那么递归的顺序是什么？我的代码是：

public static int FindMin(int[] array, int low, int high)
{
int min = 0, min1 = 0, min2 = 0;
int mid = 0;
if (low == high)
    {
    min = array[low];
    }
else if (low == (high - 1))
    {
    if (array[low] < array[high])
        {
        min = array[low];
        }
    else if (array[low] > array[high]);
        {
        min = array[high];
        }
    }
else
    {
    mid = (low + high)/2;
    min1 = FindMin(array, low, mid);
    min2 = FindMin(array, mid+1, high);
    if (min1 < min2)
        {
        min = min1;
        }
    else
        {
        min = min2;
        }
    }
return min;
}

基本上我想知道的是：如果给定输入，算法将如何工作：3,6,1,5,7,2,1。就像它返回的东西和类似的东西。

如果问题有点模棱两可，我很抱歉，但我知道如何编码，我似乎无法理解它如何返回所有内容，无论我开始使用的所有谷歌页面和 pdf 文件。

无论如何感谢所有的帮助！:D

4

2 回答 2

1

虽然调试器很有用，但有时正确的日志文件输出类型可以提供更多洞察力。我在函数末尾添加了对以下函数的FindMin()调用，就在return min;语句之前：

public static void pr (int[] array, int low, int high, int min) {
    System.out.print("low = ");
    System.out.print(low);
    System.out.print(", high = ");
    System.out.print(high);
    System.out.print(", array = ");
    for (int i = low; i <= high; i++) {
        System.out.print(array[i]);
        if (i < high) {
            System.out.print(",");
        }
    }
    System.out.print(" min = ");
    System.out.print(min);
    System.out.print("\n");
}

我得到的输出是：

low = 0, high = 1, array = 3,6 min = 6
low = 2, high = 3, array = 1,5 min = 5
low = 0, high = 3, array = 3,6,1,5 min = 5
low = 4, high = 5, array = 7,2 min = 2
low = 6, high = 6, array = 1 min = 1
low = 4, high = 6, array = 7,2,1 min = 1
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1

这告诉我，虽然FindMin()为这个测试用例返回了正确的答案，但它这样做有点意外。我现在正在寻找为什么...

（编辑）

一个问题是代码：

if (array[low] < array[high])
{
    min = array[low];
}
else if (array[low] > array[high]);  // <- stray semi-colon here
{
    min = array[high];
}

...不考虑的情况array[low] == array[high]。第一个比较应该是<=或第二个应该是>=，否则会出现返回值min将是其初始化值 0 的情况，因为 will 的两个分支都不if适用。

（进一步编辑）

您有一个导致您的错误的杂散分号。我在上面标记的测试后的分号终止了语句。过早终止else if的语句之后是另一个语句，无论前面的测试如何，该语句始终设置min为相等。array[high]

将此代码更改为：

if (array[low] < array[high])
    {
    min = array[low];
    }
else 
    {
    min = array[high];
    }

...给出以下输出：

low = 0, high = 1, array = 3,6 min = 3
low = 2, high = 3, array = 1,5 min = 1
low = 0, high = 3, array = 3,6,1,5 min = 1
low = 4, high = 5, array = 7,2 min = 2
low = 6, high = 6, array = 1 min = 1
low = 4, high = 6, array = 7,2,1 min = 1
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1

...您可以看到每次递归调用都会产生正确的结果。

于 2013-04-07T06:15:48.477 回答
1

好的，现在我了解了它的作用和工作原理。

这很简单。对于给定的数组，您将其进一步分为两部分。现在每个递归代码都必须在某个点停止，你的在两种情况下停止。

A) When the part this recursive needs to process is sized one.
B) When the part this recursive needs to process is sized two.

因此，当满足条件 A 时，您的函数仅返回低，即等于高。

当满足条件 B 时，您的函数会比较array[low]和array[high]，并返回较低值的索引。

如果递归函数必须处理超过 2 的范围，则将其分成两部分，并将这两部分交给另外两个递归部分。

例如，对于这样的给定数组。

array[] = {1, 2, 3, 4, 5}

You will first split it to two parts of {1, 2} [0...1] and {3, 4, 5} [2...4].

    And now since the first part is of size 2, the index 0 gets returned because 1 is smaller than 2, obviously.

    And then the other part {3, 4, 5} gets divided again, to two parts, {3} [2...2], and {4, 5} [3...4].

        The first subpart of sized one, gets returned immediately, because it's of size one, return value = 2.

        And then the second part which is sized two, get compared and returned, return value = 3.

    Now these two return values (2 and 3) gets processed, comparing array[2] and array[3], array[2] is definitely smaller, so it returns 2.

Now those two return values (0 and 2) gets processed, comparing the two, we can see the minima is at index 0, of value 1.

您的代码存在缺陷，在最后一部分，您应该比较array[min1]andarray[min2]并返回min1or min2。

有点乱，希望大家能理解。另一件事是我的语法，{ data}[ index range]

于 2013-04-07T06:22:35.403 回答