2

我尝试实现一种算法，该算法将在给定数组中搜索最小和最大元素，并使用了 Cormen's Introduction to Algorithms中的想法。我的代码编译并开始工作，输出生成的随机数组，然后很长一段时间什么都不做。为什么会这样？

代码是这样的：

// fast min and max --cormen exercise 1.cpp: entry point
//implemented from a verbal description in cormen's book, p 243

#include "stdafx.h"
#include <vector>
#include <ctime>
#include <cstdlib>
#include <iostream>

struct min_and_max
{
    int min, max;
};


min_and_max find_min_and_max(std::vector<int>& A)
{
    int n = A.size();
    int min, max;
    if (n%2 == 1)
        min = max = A[0];
    if (n%2 == 0)
        if (A[0] < A[1])
        {
            min = A[0];
            max = A[1];
        }
        else
        {
            min = A[1];
            max = A[0];
        }
    for(int i = 2; i < A.size(); (i + 2))
    {
        if (A[i] < A[i+1])
        {
            if (min > A[i])
                min = A[i];
            if (max < A[i+1])
                max = A[i+1];
        }
        else
        {
            if (min > A[i+1])
                min = A[i+1];
            if (max < A[i])
                max = A[i];
        }
    }
    min_and_max result;
    result.min = min;
    result.max = max;

    return result;
}

int main()
{
    std::srand(std::time(0));
    std::vector<int> A(10);
    for (auto i = 0; i < A.size(); i++)
        {
            A[i] = rand() % 1000;
            std::cout << A[i] << " ";           
        }
    std::cout << std::endl; //IT GOES AS FAR AS THIS
    std::cout << "The array has been analyzed; its' minimum is " << find_min_and_max(A).min << "and its' maximum is " << find_min_and_max(A).max << std::endl;

    return 0;
}
4

4 回答 4

7 
 for(int i = 2; i < A.size(); (i + 2))

i + 2不会改变 的值i，您需要使用i += 2.

于 2013-10-14T20:18:56.660 回答
4

问题出在这里：

for(int i = 2; i < A.size(); (i + 2))

你从来没有真正增加i，从而导致一个无限循环。

将其更改为：

for(int i = 2; i < A.size(); i+=2)
于 2013-10-14T20:19:25.627 回答
2

除了给定的答案，如果您使用的是 c++11，您可以使用lambdas和std::for_each函数简化您的算法：

#include <algorithm>
#include <iostream>
#include <cmath>

int main() { 
    int array[] = { -8, 8, 0, 9, 5, -3, 4, 6, -1, 15, 31 };
    int min, max;
    // User std::for_each(v.begin(), v.end(), ...) for either vector or list
    std::for_each(std::begin(array), std::end(array), [&min, &max](int elem) { 
        max = std::max(max, elem);
        min = std::min(min, elem);
    });
    std::cout << min << ", " << max << std::endl;
    return 0;
}

也许它可以更简单

更新：正如@Blastfurnace指出的那样，该std::minmax_element函数可用于进一步减少搜索最小和最大元素所需的代码，从而产生这个更短的版本：

#include <algorithm>
#include <iostream>
#include <vector>   

int main() { 
    std::vector<int> values = { -8, 8, 0, 9, 5, -3, 4, 6, -1, 15, 31 };
    auto minAndMax = std::minmax_element(values.begin(), values.end());
    std::cout << *minAndMax.first << ", " << *minAndMax.second << std::endl;
    return 0;
}

重要的是要注意，除了作为 OT 之外，此答案中所做的一切都是为了学习，为 OP 提供替代方案以改进他（或她）的工作并帮助可能有相同要求的其他用户。

于 2013-10-14T20:57:06.643 回答
0

在任何情况下，算法都是不正确的，因为向量的大小可能等于 0。在这种情况下，1）您尝试访问不存在的元素，以及 2）您从函数返回未定义的值。更正确的方法是返回最小和最大元素的索引，如果向量为空，则返回一对 A.size()。

于 2013-10-14T20:42:01.753 回答