通过分治算法计算数组的最大数

Question

我编写了一个程序，使用分而治之算法计算数组的最大值，但输出为 0。

#include <iostream>
using namespace std;
int array[50];

void maximum(int index1, int index2, int&max_number) {
    int max_number1;
    int max_number2;
    int half;
    if (index1 == index2)
        max_number = array[index1];
    else {
        half = (index1 + index2) / 2;
        maximum(index1, half, max_number1);
        maximum(half + 1, index2, max_number2);
        if(max_number1 < max_number2)
        max_number = max_number2;
        else
        max_number = max_number1;
    }
}

int main() {
    int index1;
    int index2;
    int max_number = 0;
    cout << "index2 = ";
    cin >> index2;
    for (index1 = 0; index1 < index2; index1++)
        cin >> array[index1];
        maximum(index1, index2, max_number);
    cout << "maximum number = " << max_number;
    return 0;
}

我该怎么办？

Answer 1

这部分代码有错字

for(index1 = 0; index1 < index2; index1++)

index1 会增加到 index2，然后

maximum(index1, index2, max_number);

将在第一个/第二个参数中传递相同的相同值，您可以像

那样更改代码

for(index1 = 0; index1 < index2; index1++)
    cin>>array[index1];
index1 = 0;
maximum(index1, index2, max_number);

Answer 2

在这个循环之后

for(index1 = 0; index1 < index2; index1++)
cin>>array[index1];

index1 等于 index2。所以这个调用

maximum(index1, index2, max_number);

没有意义。

无论如何，该函数过于复杂并且使用了全局变量，这是一种不好的编程习惯。

使用标准算法可以更简单地编写递归函数 std::max。

例如

#include <iostream>
#include <algorithm>

size_t maximum( const int a[], size_t n )
{
    return n < 2 ? 
           0     : 
           std::max( maximum( a, n / 2 ), 
                     n / 2 + maximum( a + n / 2, n - n / 2 ), 
                     [a] ( size_t i, size_t j ) { return a[i] < a[j]; } );  
}

int main() 
{
    const size_t N = 10;
    int a[N] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int b[N] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    int c[N] = { 0, 2, 4, 6, 8, 9, 7, 5, 3, 1 };

    size_t pos = maximum( a, N );
    std::cout << "The maximum element is " << a[pos] 
              << " at position " << pos  << std::endl;

    pos = maximum( b, N );
    std::cout << "The maximum element is " << b[pos] 
              << " at position " << pos  << std::endl;

    pos = maximum( c, N );
    std::cout << "The maximum element is " << c[pos] 
              << " at position " << pos  << std::endl;

    return 0;
}

程序输出为

The maximum element is 9 at position 9
The maximum element is 9 at position 0
The maximum element is 9 at position 5

通过分治算法计算数组的最大数

Calculating the maximum number of an array by divide and conquer algorithm

c++

arrays

algorithm

recursion

divide-and-conquer