реализовать алгоритм из его псевдокода в C++

Question

Im пытается реализовать рекурсивный алгоритм Изменение задачи из следующего псевдокода

но я не мог знать, как правильно реализовать, моя цель состоит в том, чтобы узнать, как прочитать псевдокод больше, чем решить проблему изменения.

вот мой код в 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

Ну, одна проблема, которую я могу видеть в том, что вы объявили minNumber монеты, но вы не инициализируются его специально для любого числа. Как следствие, оно будет иметь значение 0 (ноль) в начале и при сравнении его с положительным числом оно никогда не вернет true, так как оно не больше положительного числа. Вот почему ваша программа работает неправильно. Я не вижу никакой другой проблемы при реализации псевдокода. Вы прошли через это хорошо. Удачи :)

Answer 3

И, "отступать от все (!) Этого ... (гм) ..."

... и, возможно, тем самым показывая свой возраст ... (Кофф) ...

... любезно помнить, что" псевдо- код»является только (!!) когда-либо предназначен для:   «(очень-точно ...) означает, по которым два человеческим существам, возможно, пожелают выразить алгоритм друг с другом.»

Когда два человеческих существ выбирают для описанияконкретный алгоритм «в псевдокоде», имплицитно понимается между ними, что они решили общаться в терминах определенного программирования (язык или стиль), с которым оба они знакомы друг с другом ». Но это должно быть не быть расширенным, чтобы означать, что существует какой-либо прямой 1: 1 соответствие между словами «что они говорят» и «фактическим исходным кодом компьютера».