Поскольку цикл в жадном алгоритме не прерывается, запрашивает ввод бесконечно - PullRequest
Новая
       31

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

2 голосов
/ 16 мая 2019

Я создаю жадный цикл, который находит наименьшее количество монет, которые будут использоваться для возврата значения для pset1 в CS50, и я не могу понять, почему мой цикл while работает бесконечно.

Iя возился с ним и не смог убежать. 

#include <stdio.h>
#include <cs50.h>
#include <math.h>

// declare variable change_owed, num_coins, and input globally
float change_owed;
float input;
int num_coins;

int main(void)
{
    // makes sure the input is non-negative
    do
    {
        input = get_float("Amount paid\n");
    }
    while(change_owed <=0);
    input = round(input);

    // begin checking 
    while(input > 0)
    {
        if(input - .25 > 0) // quarters
        {
            num_coins++; // number of coins used, to be printed later, is incremented
            input = input - .25; // coin is subtracted from total
        }
        else if (input - .10 > 0) // dimes
        {
            num_coins++;
            input = input - .10;
        }   
        else if (input - .05 > 0) // nickels
        {
            num_coins++;
            input = input - .05;
        } 
        else if (input - .01 > 0) // pennies
        {
            num_coins++;
            input = input - .01;
        } 
    }
    printf("%i", num_coins);
}

Ответы [ 2 ]

3 голосов
/ 16 мая 2019

Условием для вашего первого цикла do/while является change_owed <= 0, но в теле цикла нет ничего, что могло бы изменить это значение.Поскольку это глобальное значение, которое инициализируется значением 0 и не изменяется до входа в цикл, оно всегда будет иметь значение 0 при проверке условия while.Это приводит к тому, что цикл никогда не завершается.

0 голосов
/ 16 мая 2019

Вопросы

while(change_owed <=0); - это бесконечный цикл, поскольку change_owed всегда равно 0. Конечно, должно быть while(input <=0);

input = round(input); имеет мало смысла. round() не округляется до ближайшего 0,01, но до ближайшего целого числа.

Результат кода всегда будет четверти .

2-й цикл также является потенциальным бесконечным циклом.

Рассмотрим, что происходит, когда input > 0 и input - .01 > 0 ложно -> бесконечный цикл. Обычно это может произойти, когда input = round(input); исправлено. 

while(input > 0)
{
    if(input - .25 > 0) // quarters
    { ... }
    else if (input - .10 > 0) // dimes
    { ... }
    else if (input - .05 > 0) // nickels
    { ... }
    else if (input - .01 > 0) // pennies
    { ... }
}

КСТАТИ

Конечно, if(input - .25 > 0) должно быть if(input - .25 >= 0) (или лучше if(input >= 0.25f). Используйте >= вместо >.

Увеличенное изображение. Используйте целые числа. 

int main(void) {
  //float change_owed;
  float input;
  long long num_coins = 0;
  do {
    input = get_float("Amount paid\n");
  } while (input <= 0);
  long long input_cents = llround(input * 100.0);

  // begin checking
  while (input_cents > 0) {
    if (input_cents >= 25) {
      num_coins++;
      input_cents -= 25;
    } else if (input_cents >= 10) {
      num_coins++;
      input_cents -= 10;
    } else if (input >= 5) {
      num_coins++;
      input_cents -= 5;
    } else if (input >= 1) {
      num_coins++;
      input_cents -= 1;
    }
  }
  printf("%lld\n", num_coins);
}

Возможна дополнительная эффективность, а не просто num_coins++;

  if (input_cents > 0) {
    num_coins += input_cents/25;
    input_cents %= 25;
    num_coins += input_cents/10;
    input_cents %= 10;
    num_coins += input_cents/5;
    input_cents %= 5;
    num_coins += input_cents;
  }
...