1

一位讲师在课堂上提出了这个问题：[问题]

n 个整数的序列存储在数组 A[1..n] 中。如果一个整数 a 在 A 中出现超过 n/2 次，则称为多数。

可以设计一个 O(n) 算法来根据以下观察找到多数：如果原始序列中的两个不同元素被删除，则原始序列中的多数仍然是新序列中的多数。使用这种观察或其他方式，编写编程代码以在 O(n) 时间内找到大多数（如果存在）。

接受此解决方案的[解决方案]

int findCandidate(int[] a)
{
    int maj_index = 0;
    int count = 1;
    for (int i=1;i<a.length;i++)
    {
        if (a[maj_index] == a[i])
            count++;
        else
            count--;

        if (count == 0)
        {
            maj_index =i;
            count++;
        }
    }
    return a[maj_index];
}

int findMajority(int[] a)
{
    int c = findCandidate(a);
    int count = 0;
    for (int i=0;i<a.length;i++)
        if (a[i] == c) count++;

    if (count > n/2) return c;
    return -1;//just a marker - no majority found
}

我看不出所提供的解决方案如何是动态解决方案。而且我看不出他是如何根据措辞提取代码的。

4

3 回答 3

3

动态编程一词的起源是试图描述一种优化某些解决方案的非常棒的方法（使用动态是因为它听起来更有力）。换句话说，当你看到“动态编程”时，你需要把它翻译成“很棒的优化”。

于 2010-12-15T00:14:16.920 回答
2

'Dynamic programming' has nothing to do with dynamic allocation of memory or whatever, it's just an old term. In fact, it has little to do with modern meaing of "programming" also.

It is a method of solving of specific class of problems - when an optimal solution of subproblem is guaranteed to be part of optimal solution of bigger problem. For instance, if you want to pay $567 with a smallest amount of bills, the solution will contain at least one of solutions for $1..$566 and one more bill.

The code is just an application of the algorithm.

于 2010-12-14T23:19:39.790 回答
0

这是动态编程，因为 findCandidate 函数将提供的数组分解为更小、更易于管理的部分。在这种情况下，他从第一个数组开始作为多数人的候选人。通过在遇到计数时增加计数并在遇到计数时减少计数，他确定这是否为真。当计数为零时，我们知道前 i 个字符没有多数。通过不断地计算局部多数，我们不需要在候选识别阶段多次遍历数组。然后，我们通过第二次遍历数组来检查该候选人是否实际上是多数，给我们 O(n)。它实际上运行了 2n 次，因为我们迭代了两次，但常数无关紧要。

于 2010-12-14T23:29:38.530 回答