这个解决方案如何成为动态规划的一个例子?

发布于 2024-10-07 14:41:45 字数 941 浏览 5 评论 0 原文

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

n 个整数的序列存储在 数组 A[1..n]。 A 中的整数 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
}

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

A lecturer gave this question in class:
[question]

A sequence of n integers is stored in
an array A[1..n]. An integer a in A is
called the majority if it appears more
than n/2 times in A.

An O(n) algorithm can be devised to
find the majority based on the
following observation: if two
different elements in the original
sequence are removed, then the
majority in the original sequence
remains the majority in the new
sequence. Using this observation, or
otherwise, write programming code to
find the majority, if one exists, in
O(n) time.

for which this solution was accepted
[solution]

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
}

I can't see how the solution provided is a dynamic solution. And I can't see how based on the wording, he pulled that code out.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

帅气称霸 2024-10-14 14:41:45

术语动态编程的起源试图描述一种优化某些类型的真正很棒的方法解决方案(使用动态是因为它听起来更有力)。换句话说,当你看到“动态规划”时,需要将其翻译为“很棒的优化”。

The origin of the term dynamic programming is trying to describe a really awesome way of optimizing certain kinds of solutions (dynamic was used since it sounded punchier). In other words, when you see "dynamic programming", you need to translate it into "awesome optimization".

奢欲 2024-10-14 14:41:45

'动态编程'与内存的动态分配或其他什么无关,它只是一个旧术语。事实上,它与“编程”的现代含义也没有什么关系。

它是解决特定类别问题的方法 - 当子问题的最优解保证是更大问题的最优解的一部分时。例如,如果您想用最少的账单金额支付 567 美元,则该解决方案将至少包含 1..566 美元的解决方案之一以及另外一张账单。

代码只是算法的一个应用。

'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.

听你说爱我 2024-10-14 14:41:45

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

This is dynamic programming because the findCandidate function is breaking down the provided array into smaller, more manageable parts. In this case, he starts with the first array as a candidate for the majority. By increasing the count when it is encountered and decreasing the count when it is not, he determines if this is true. When the count equals zero, we know that the first i characters do not have a majority. By continually calculating the local majority we don't need to iterate through the array more than once in the candidate identification phase. We then check to see if that candidate is actually the majority by going through the array a second time, giving us O(n). It actually runs in 2n time, since we iterate twice, but the constant doesn't matter.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文