在c++中用伪码实现一种算法

Question

我试图从下面的伪码实现一个变化问题的递归算法

​

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

这是我在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

伪码：

MinNumCoins ← ∞

它的状态是“初始化MinNumCoins到无穷大”。

您的等效代码：

int minNumCoins;

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

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

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

通过初始化具有正无穷大的变量，这将获得MinNumCoins的第一个计算值，并设置它(因为第一个计算值总是小于无穷大)。

替换逻辑使用第二个变量(标志)来指示是否设置了该值。如果不是，则不管变量是什么，都会设置该值；但是，如果变量已经设置，代码将其与新的计算值进行比较，并在计算值小于现有值时更新该值。

2)第二种方法是将变量初始化为尽可能高的值。没有“无穷大”的值，可以将int设置为“无穷”。最近的候选值将是int可能设置的最高最大值。这将是：

#include <limits>

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

对于你的问题来说，这个“黑客”是否是一个可以接受的解决方案，你需要自己来决定。

Answer 2

以及“从all__(!)向后退.(嗯哼).”

..。可能因此暴露了我的年龄..。(考夫)

..。请记住，“伪代码”只是(！！)"a (非常精确的.)意思是两个人可能希望彼此表达一个算法。“

当两个人选择用“伪码”来描述一个特定的算法时，他们之间的默示理解是，他们选择用一种特定的编程(语言或风格)进行交流，而这两者是相互熟悉的。但是，这应该是而不是的延伸，因为这意味着“他们所说的话”和“实际的计算机源代码”之间有任何直接的1:1对应关系。

Answer 3

嗯，我在这里看到的一个问题是，您已经声明了minNumber硬币，但是您还没有将它具体初始化为任何数字。因此，它的起始值为0(0)，当将它与正数进行比较时，它将永远不会返回true，因为它不大于正数。这就是你的程序不能正常工作的原因。在实现伪代码时，我没有看到任何其他问题。你经历得很好。好运:)