implement an algorithm from its pseudocode in c++

Question

Im trying to implement a recursive algorithm of Change problem from the following pseudocode

yet I couldn't know how to implement it correctly, my goal is to learn how read the pseudocode more than how to solve the change problem.

here is my code in 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;
}

Why everyone is all of sudden got excited for coin-change problem ? — P0W, Jul 18 '16 at 03:49
Possible duplicate of [Recursive coin change c++](http://stackoverflow.com/questions/37106465/recursive-coin-change-c) — Ed Heal, Jul 18 '16 at 03:50
Im reading from bioinformatics Algorithms interactive learning approach textbook p204 and trying to understand their pseudocode .. so I can move on ! — Zingo, Jul 18 '16 at 03:54

score 3 · Accepted Answer · answered Jul 18 '16 at 04:00

The pseudocode:

MinNumCoins ← ∞

This states "Initialize MinNumCoins to an infinity".

Your equivalent code:

int minNumCoins;

This declares minNumCoins, but leaves this uninitialized. This is not only not what the pseudocode states, but since the code subsequently uses the uninitialized variable, this results in undefined behavior.

There are two basic approaches to implement this pseudocode:

1) Use a second variable, that indicates whether the value has been set, or not. The intent of initializing a variable to infinity to is to find the smallest value that gets computed for it. On each attempt, a potential candidate value for MinNumCoins gets computed, and if it's less than the current value of MinNumCoins, the new value replaces it. MinNumCoins ends up having the smallest value that gets computed for it.

By initializing the variable with a positive infinity, this has the effect of taking the first computed value for MinNumCoins, and setting it (since the first computed value will always be less than infinity).

The replacement logic uses a second variable, a flag, to indicate whether the value has been set. If it is not, the value gets set no matter what it is; but if the variable has been set, the code compares it to the new computed value, as usual, and updates it if the computed value is less than the existing value.

2) The second approach is to initialize the variable to the highest possible value. There is no value for "infinity", that an int can be set to. The closest candiate would be the highest maximum value an int can possibly be set to. This would be:

#include <limits>

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

Whether this somewhat "hack" would be an acceptable solution for your problem, is something for you to decide.

score 1 · Answer 2 · answered Jul 18 '16 at 04:20

And, "stepping back from all(!) of this ... (ahem) ..."

... and possibly thereby revealing my age ... (koff) ...

... kindly remember that "pseudo- code" is only(!!) ever intended to be: "a (very-exact ...) means by which two human beings might wish to express an algorithm to one another."

When two human beings choose to describe a particular algorithm "in pseudo-code," it is implicitly understood between them that they have elected to communicate in terms of a particular programming (language-or-style) that both of them are mutually acquainted with." But, this should not be extended to mean that there is any sort of direct 1:1 correspondence between "what they are saying" and "actual computer source-code."

score 0 · Answer 3 · answered Jul 18 '16 at 04:00

0

Well, one problem I can see here is that you've declared minNumber coins but you haven't initialized it specifically to any number. As a consequence, it will have the value of 0(zero) at the beginning and when comparing it with a positive number, it will never return true, since it is not bigger than a positive number. And that's why your program does not work properly. I do not see any other problem in implementing the pseudo-code. You have gone through it well. Good Luck :)

answered Jul 18 '16 at 04:00

Athena

543
10
30

No, it will not have the value of 0. It is uninitialized, and this results in undefined behavior. `MinNumCoins` is not 0-initialized, in the code sample. – Sam Varshavchik Jul 18 '16 at 04:02
@SamVarshavchik You're right. It depends on the compiler. some initial to 0 and some will not. – Athena Jul 18 '16 at 04:06
I know of no compiler that will zero-initialize an uninitialized object by default. Given that compilers try their best to produce the fastest, smallest code, it would be fairly unlikely for a compiler to suddenly desire to generate a bunch of code that they're not required to generate. – Sam Varshavchik Jul 18 '16 at 04:09
I think [Visual Studio may initialize a variable to `0` in Debug](http://stackoverflow.com/questions/312312/what-are-some-reasons-a-release-build-would-run-differently-than-a-debug-build), but definitely not the kind of thing to guarantee nor teach. – Tas Jul 18 '16 at 04:23

implement an algorithm from its pseudocode in c++

3 Answers3