JavaRush/Курсы/Harvard CS50/Задание 3. Время получать сдачу

Задание 3. Время получать сдачу

Открыта

В наших широтах мы такого не встречали, а в США, похоже, распространён игрушечный кассовый аппарат, изображенный на фото выше. Цилиндры предназначены для хранения монет разного диаметра (и номиналов). Выдает их пружинный механизм, а сам агрегат можно закрепить на поясе ребёнка-кассира.

Однако что будет, если кто-то рассчитается с кассиром крупной купюрой? Представьте, сколько мороки будет с тем, чтобы посчитать монетки на сдачу. Для минимизации количества выдаваемых монет можно использовать так называемые «жадные» алгоритмы. Они, согласно определению Национального Института Стандартов и Технологии (NIST) всегда находят оптимальное решение на каждом шаге решения задачи, допуская, что конечное решение (полученное из совокупности таких шагов) также будет оптимальным.

Что это значит? Представим, что кассир должен покупателю сдачу в 41 цент, а у него на поясе есть цилиндры с монетками для сдачи номиналом в 25, 10, 5 и 1 цент. Руководствующийся «жадным» алгоритмом кассир сразу же захочет выдать максимум, на первом же шаге. На этом шаге оптимальным или наилучшим решением будет выдать 25 пенсов. 41-25 = 16. Осталось выдать 16 пенсов. Очевидно, 25 пенсов слишком много, значит, остается 10. 16-10 = 6. Теперь выдаем по тому же принципу 5 пенсов, и затем — 1. Таким образом, покупатель получит всего четыре монеты номиналом 25, 10, 5 и 1 пенс.

Оказывается, «жадная» пошаговая инструкция выдачи денег оптимальна не только для этого случая, но также для номиналов валюты США (и Евросоюза тоже). То есть, если у кассира достаточно монет любого номинала, алгоритм будет работать лучшим образом, то есть, выдаст минимальное количество монет из всех возможных случаев.

Итак, какое минимальное количество монеток нам нужно, чтобы дать сдачу? Это и есть наша третья задачка.

Создайте файл greedy.c в своей директории ~/workspace/pset1.

Дано: монетки номиналом 25, 10, 5, 1 цент

Программа должна:

Спросить пользователя, сколько сдачи нужно выдать.
Посчитать минимальное количество монет, с помощью которых можно это сделать

Примечание: для ввода будем пользоваться функцией GetFloat из библиотеки CS50 и printf из стандартной библиотеки ввода/вывода для вывода. Кроме того, программа должна проверять корректность ввода.

Мы попросили вас использовать GetFloat, чтобы пользователь мог вводить значение в долларах и центах через точку. Например, если мы должны $9.75, пользователь должен ввести 9.75, но не $9.75 или 975.

Вы должны проследить, чтобы пользователь ввел число, которое имеет смысл. Скажем, неотрицательное, в этом функция GetFloat сама по себе не поможет. Если пользователь сделал неправильный ввод, нужно просить его повторить его, и выполнять программу только с корректными данными.

Внимание! Остерегайтесь неточностей, свойственных числам с плавающей точкой. Например, 0.01 не может быть представлено непосредственно как float. Попробуйте использовать форматированный вывод, например, с 50 знаками после запятой, используя указанный ниже код:

float f = 0.01;
printf("%.50f\n", f);

Кстати, перед тем, как что-либо считать, будет логично перевести всю сумму в центы, (и заодно преобразовать её из float в int), что поможет избежать массы ошибок и сложностей.

Чтобы наш автоматический анализатор кода мог правильно проверить вашу задачу, убедитесь, что последняя строка вывода вашей программы не содержит никакой другой информации, кроме минимального количества монеток: целое число с символом \n после него (те, кто учится на JavaRush, прекрасно знают, о чём мы здесь говорим =)). Ниже — пример, как должен выглядеть результат работы вашей программы.

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
0.41
4

Учитывая особенность чисел с плавающей точкой, можно игнорировать нуль и вводить такое число в форме .41.

Конечно, пользователи, которые захотят проверить программу на возможность ввода некорректных данных по полной, должны увидеть что-то вроде:

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
-0.41
How much change is owed?
-0.41
How much change is owed?
foo
Retry: 0.41
4

Исходя из этих требований и примера, который вы увидели выше, ваш код, скорее всего, должен содержать какой-то цикл.

Если во время тестирования приложения вы поймете, что цикл не останавливается, вы можете прервать выполнение программы комбинацией ctrl-c (иногда — многократной).

Как компилировать и выполнять программу вы уже знаете.

Если вы хотите проверить правильность работы вашей программы, с помощью утилиты check50, в терминале введите следующую строку:

check50 2015.fall.pset1.greedy greedy.c

А если вам захочется поиграть с этой программой, выполненной ассистентами курса, пропишите следующую команду:

~cs50/pset1/greedy

ПредыдущаяПредыдущая лекция

СледующаяСледующая лекция

Комментарии (180)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

xephos23

Уровень 2

28 октября 2025, 11:44

как-то так :))

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

int main(void)
{
    float change;
    int cents;
    int counter = 0;
    int counter_a = 0;
    int counter_b = 0;
    int counter_c = 0;
    int counter_d = 0;

    do
    {
        change = get_float("Сколько сдачи нужно выдать вам? (в долларах $) \t");
    }
    while (change < 0);

    cents = round(change * 100);

    while (cents > 0)
    {
        if (cents >= 25)
        {
            counter_a += cents/25; // деление нацело
            counter += counter_a;
            cents -= cents/25 * 25; // делим нацело, затем умножаем на номинал монеты
        }
        else if (cents >= 10)
        {
            counter_b += cents/10;
            counter += counter_b;
            cents -= cents/10 * 10;
        }
        else if (cents >= 5)
        {
            counter_c += cents/5;
            counter += counter_c;
            cents -= cents/5 * 5;
        }
        else
        {
            counter_d += cents/1;
            counter += counter_d;
            cents -= cents/1 * 1;
        }
    }
    printf("Общее кол-во монет: %i\n25-центовые: %i\t 10-центовые: %i\n5-центовые: %i\t центовые: %i", counter, counter_a, counter_b, counter_c, counter_d);
}

Anonymous #3605906

Уровень 1

16 августа 2025, 06:38

Не идеально, но пока что только начинаю #include <stdio.h> #include <cs50.h> int main ( void ) { float сдача; int цент, a, b, c, d, f, g, h; do { сдача = get_float ( "Сколько вам выдать сдачи: " ); цент = сдача * 100; printf ( "В центах это: %i \n" , цент ); } while ( сдача < = 0 ); do { a = цент / 25 ; printf ( "Монет по 25 центов: %i\n" , a ); } while ( a < 0 ); b = цент - ( a * 25 ); do { c = b / 10; printf ( "Монет по 10 центов: %i\n" , c ); } while ( c < 0 ); d = b - ( c * 10 ); do { f = d / 5; printf ( "Монет по 5 центов: %i\n" , f ); } while ( f < 0 ); g = d - ( f * 5 ); do { h = g / 1; printf ( "Монет по 1 центу: %i\n", h ); } while ( h < 0 ); }

Oleg Ognev

Уровень 2

19 октября 2023, 18:41

программу сам сделал, но ошибку с плавающей запятой( когда значение 1.05 в программе при умножении на 100 даёт результат 104) помог решить ChatGPT, для этого нужно использовать функцию round и библиотеку math.h. Вроде как ошибки быть не должно, тем более мы округляем уже целочисленную переменную cents. #include <cs50.h> #include <stdio.h> #include <math.h> int main(void) { float delivery = 0; int numberOfCoins=0; int cents; while(delivery<=0) { delivery = get_float("Delivery: "); } cents = round((delivery) * 100); while(cents != 0) { if(cents >= 25) { cents-=25; numberOfCoins++; } else if(cents >= 10) { cents-=10; numberOfCoins++; } else if(cents >= 5) { cents-=5; numberOfCoins++; } else { cents-=1; numberOfCoins++; } } printf("Number of coins: %i\n", numberOfCoins); }

Matvey Glukhov

Уровень 1

29 сентября 2023, 10:58

Мой вариант еще оч далек от идеала, но простой в понимании

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

int main (void)
{
   float change;
   int cent, tfcent, restfcent, tcent, restcent, fcent, resftcent, ocent;
   do
   {
      change = get_float ("Введите сколько вам нужно выдать сдачу: \n");
      cent = change * 100;
      printf("Вот столько это будет в центах: %i \n", cent);
   }
   while (change <= 0);

   do
   {
      tfcent = cent / 25;
      printf("Вам нужно взять монет по 25 центов - %i \n", tfcent);
   }
   while (tfcent == 24);

      restfcent = cent - (tfcent * 25);

      do
      {
         tcent = restfcent / 10;
         printf("Вам нужно взять монет по 10 центов - %i \n", tcent);
      }
      while (tcent == 9);

      restcent = cent - ((tfcent * 25) + (tcent * 10));

      do
      {
         fcent = restcent / 5;
         printf("Вам нужно взять монет по 5 центов - %i \n", fcent);
      }
      while (fcent == 4);

      resftcent = cent - ((tfcent * 25) + (tcent * 10) + (fcent * 5));

      do
      {
         ocent = resftcent / 1;
         printf("Вам нужно взять монет по 1 центу - %i \n", ocent);
      }
      while (ocent == 0);
}

Lion Man

Уровень 1

27 апреля 2023, 03:30

Мой варинат, по ощущениям немного неделикатный, но вроде работает

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

int main(void)
{
  float num;

  int num2, b, c, d, ab, ac, ba, aa, aaa;

  do num = GetFloat();
  while (num<=0);

  num2 = num*100;

  b = num2/25;

  c = num2%25;

  d = c/10;

  ab = c%10;

  ac = ab/5;

  ba = ab%5;

  aa = ba/1;

  aaa = b + d + ac + aa;

  printf ("%i\n", aaa);

  return 0;

}

Павел Тукальский

Уровень 6

29 июня 2023, 17:59

Введите число 1.05. Результатом будет 8. Проблема чисел с плавающей точкой.

Павел Тукальский

Уровень 6

10 января 2023, 02:21

/* Комментарий удален */

Alexey Hehnev

Уровень 25

1 февраля 2023, 10:05

метод round(float) округляет число до целого, если число 0,5 или больше то будет 1, а если меньше 0,5 то до нуля.

Oleg Ognev

Уровень 2

19 октября 2023, 18:44

как вариант можешь перевести значение float в int, создав новую переменную и умножив на 100, дальше можно использовать round. Посмотри в комментариях моё решение.

Виктор Ларькин

Уровень 3

7 ноября 2022, 09:59

#include <stdio.h> #include <cs50.h> int main(int avgc, char** argv) { float change; int change_int; int count = 0; do { //printf("O hai! How much change is owed?\n"); change = get_float("O hai! How much change is owed?\n"); printf("%.2f\n", change); } while(change < 0); change_int = (int)(change * 100); while (change_int) { if ((change_int / 25) != 0 ) { count+= change_int / 25; change_int = change_int % 25; } if ((change_int / 10) != 0 ) { count+= change_int / 10; change_int = change_int % 10; } if ((change_int / 5) != 0 ) { count+= change_int / 5; change_int = change_int % 5; } if ((change_int / 1) != 0) { count+= change_int / 1; change_int = change_int % 1; } } printf("Count: %i\n", count); }

Павел Тукальский

Уровень 6

29 июня 2023, 18:01

Введите число 1.05. Результатом будет 8. Проблема чисел с плавающей точкой.

Anonymous #3186289

Уровень 1

21 октября 2022, 11:44

как-то так :) #include <stdio.h> #include <cs50.h> int main(void) { float f; do { f = get_float ("rest:\n"); } while ( f<=0); { int k; k = f * 100; { printf("%d\n",k); } { int h, j, l, p; printf("Enter the first value:"); scanf("%d", &h); printf("Enter the second value:"); scanf("%d", &j); printf("Enter the third value:"); scanf("%d", &l); printf("Enter the fourth value:"); scanf("%d", &p); int a=0; int b=0; int c=0; int d=0; while (h<=k) { k= k -h; a++; } while (k>=j) { k= k- j; b++; } while (k>=l) { k = k - l; c++; } while (k>=p) { k=k-p; d++; } int sum= a + b + c + d; { printf("the rest will consist of %d coins\n", sum); } } } }

Kirill Skladanov

Уровень 2

10 октября 2022, 15:47

по стилю докручивать лениво, главное отличие в том, что число итераций в циклах подсчета - максимум четыре, независимо от величины введенного числа (использовал деление, а не вычитание - при делении остаток отбрасывается автоматом)

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

int main(void){
    float val;
    do {
        val = get_float("Сколько нужно дать сдачи?: ");
    } while (val<0); //проверка на неотрицательное число
    //25 10 5 1 - номиналы монет
    int cents = val*100;
    int coins = 0;
    do { //цикл будет исполняться пока невыданных центов будет больше 0
        if (cents>24){
            coins = coins + cents/25;
            cents = cents - 25*(cents/25);
        }
        else if (cents>9){
            coins = coins + cents/10;
            cents = cents - cents*(cents/10);
    }
        else if (cents>4){
            coins = coins + cents/5;
            cents = cents - cents*(cents/5);
        }
        else {
            coins = coins + cents/1;
            cents = cents - cents*(cents/1);
        }
    } while (cents>0);
    printf("%i\n", coins);
    }

Макс

Уровень 1

10 октября 2022, 13:43

Пока не получается проектировать подсчеты с нуля, приходится подглядывать к коллегам)

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

int main(void)
{
    float n;
    do
    {
        n = get_float("Сколько нужно дать сдачи? ");
    }
    while (n < 0);
    //запрос данных и проверка

    int cent = n * 100;
    int a = 0;
    int b = 0;
    int c = 0;
    int d = 0;

printf("перевод в центы %d\n", cent);

   while (cent >= 25) {
       cent = cent - 25;
       a++;
   }
      while (cent >= 10) {
       cent = cent - 10;
       b++;
   }
   while (cent >= 5) {
       cent = cent - 5;
       c++;
   }
      while (cent >= 1) {
       cent = cent - 1;
       d++;
   }
    int sum = a + b + c + d;



    printf("По 25 = %d\n По 10 = %d\n По 5 = %d\n По 1 = %d\n ИТОГО = %d\n", a, b, c, d, sum);
}