在 C++ 中从其伪代码实现算法

Question

我正在尝试根据以下伪代码实现 Change 问题的递归算法

但我不知道如何正确实现它，我的目标是学习如何阅读伪代码，而不是如何解决更改问题。

这是我的 C++ 代码

int recChange(int money){
    int coins [6] = { 50, 25, 20, 10, 5, 1 };

    if (money == 0) return 0;

    int minNumberCoins;

    for (int i=0; i < 6; ++i){
        if (money >= coins[i]) {
            int numberCoins = recChange(money - coins[i]);

            if (numberCoins + 1 < minNumberCoins ){
                minNumberCoins = numberCoins + 1;
            }
         }
     }
     return minNumberCoins;
}

Answer 1

好吧，我在这里看到的一个问题是您已经声明了 minNumber 个硬币，但是您还没有将它具体初始化为任何数字。因此，它的开头值为 0（零），当它与正数比较时，它永远不会 return 为真，因为它不大于正数。这就是您的程序无法正常运行的原因。我没有看到实施伪代码的任何其他问题。你已经很好地度过了它。祝你好运:)

Answer 2

伪代码：

MinNumCoins ← ∞

这表示 "Initialize MinNumCoins to an infinity"。

你的等效代码：

int minNumCoins;

这声明了 minNumCoins，但未初始化。这不仅不是伪代码所说的，而且由于代码随后使用了未初始化的变量，这会导致未定义的行为。

有两种基本方法可以实现这个伪代码：

1) 使用第二个变量，指示该值是否已设置。将变量初始化为无穷大的目的是找到为其计算的最小值。每次尝试时，都会计算 MinNumCoins 的潜在候选值，如果它小于 MinNumCoins 的当前值，则新值将替换它。 MinNumCoins 最终得到为其计算的最小值。

通过用正无穷大初始化变量，这具有获取 MinNumCoins 的第一个计算值并设置它的效果（因为第一个计算值将始终小于无穷大）。

替换逻辑使用第二个变量（标志）来指示是否已设置该值。如果不是，则不管它是什么值都会被设置；但如果已设置变量，代码会像往常一样将它与新的计算值进行比较，如果计算值小于现有值，则更新它。

2) 第二种方法是将变量初始化为可能的最高值。 "infinity" 没有可以设置为 int 的值。最接近的候选值将是 int 可以设置的最高最大值。这将是：

#include <limits>

int MinNumCoins = std::numeric_limits<int>::max();

这是否 "hack" 是您问题的可接受解决方案，由您决定。

Answer 3

而且，"stepping back from all(!) of this ... (ahem) ..."

... 并可能因此泄露我的 age ... (koff) ...

... 请记住，“ 伪代码” 仅 (!!) 曾打算成为： "a (very-exact ...) means by which two human beings might wish to express an algorithm to one another."

当两个人选择描述特定算法 "in pseudo-code," 时，他们之间隐含地理解他们已选择根据特定编程（语言）进行交流-or-style) 两者都相互熟悉。”但是，这应该 not 扩展为意味着有任何类型的 direct 1:1 "what they are saying"和"actual computer source-code."

之间的对应关系

在 C++ 中从其伪代码实现算法

implement an algorithm from its pseudocode in c++

c++

algorithm

pseudocode