С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.62/21: Рейтинг темы: голосов - 21, средняя оценка - 4.62
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8

Жадный алгоритм

27.09.2016, 12:08. Показов 4282. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый день.
Помогите, пожалуйста, понять, где затаилась ошибка.
Это задачка на жадный алгоритм: пользователь вводит размер полагающейся сдачи, а программа должна рассчитать, какое минимальное количество монет можно выдать, располагая монетами номиналом 25с, 10с, 5с и 1с.
Представленный ниже код считает сдачу, но через раз правильно, т.е. к примеру, сдачу 0,40$ и 0,43$ рассчитывает правильно, а 0,41$ и 0,42$ - нет, показывает всего 3 монеты.
Я так понимаю, если бы формула рассчета была неправильная, неправильно бы считало все, а не через раз. Может где-то округляет неправильно? Буду очень благодарна за подсказки.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <cs50.h>
 
int main(void)
{   //переменные для обозначения сдачи и каждой из монет
    float change;
    float quater=0.25;
    float ten=0.10;
    float five=0.05;
    float cent=0.01;
    
    //запрос введения размера сдачи
    printf("O hai! ");
        do
        {
            printf("How much change is owed? ");
            change = GetFloat();
        }
        while (change<0.009);
        
        //рассчет сколько монет каждого номинала составляют данную сумму, начиная с монеты самого большого номинала
        float x = change/quater;
        int a = (int)x;
        
        float y = (change-a*quater)/ten;
        int b = (int)y;
        
        float z = (change-a*quater-b*ten)/five;
        int c = (int)z;
        
        float u = (change-a*quater-b*ten-c*five)/cent;
        int d = (int)u;
        
        int result=a+b+c+d;
        
        printf("%d\n", result);
    
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
27.09.2016, 12:08
Ответы с готовыми решениями:

Жадный алгоритм
Суть задачи - имеется N предметов различного размера. Один ящик имеет строгую вместимость. Необходимо разложить все N предметов в...

Жадный алгоритм
Нужно сделать проверку на правильность жадного алгоритма, доказать, что его решение единственно правильное. Кто знает? вот вполне рабочий...

Жадный алгоритм
Задача: По следам олимпиады. Известно, что оптимальным выбором лыж является такой, когда длина лыж максимально приближена к высоте...

11
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
27.09.2016, 12:48
Раз неправильно, то сколько выводит и сколько должна?
0
59 / 59 / 53
Регистрация: 05.05.2013
Сообщений: 150
27.09.2016, 12:58
Возможно при вычислениях y,z,u необходимо явно преобразовать коэфициенты a,b,c к float.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
27.09.2016, 13:01
Чтоб центы не сбивались, напишите так:
int d = (int)(u+0.1);
0
 Аватар для ture
553 / 361 / 206
Регистрация: 27.11.2014
Сообщений: 1,049
27.09.2016, 13:05
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
 
#define quater 25
#define ten    10
#define five   5
#define cent   1
 
int main() {
    unsigned change, _change;
    do {
        change=_change = 0;
        printf("How much change is owed? ");
        scanf("%d,%d", &change, &_change);
    } while(!change && !_change);
 
    /*переводим все в центы*/
    change *=100;
    change += _change;
 
    unsigned a = change / quater;
    change -= a*quater;
 
    unsigned b = change / ten;
    change -= b*ten;
 
    unsigned c = change / five;
    change -= c*five;
 
    printf("25 - %3d\n10 - %3d\n5  - %3d\n1  - %3d\n Total - %d\n", a, b, c, change, a + b + c + change);
 
    return 0;
}
0
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 13:26  [ТС]
К примеру, сдача составляет 0,41$. Минимальное количество монет: 1х25с, 1х10с, 1х5с и 1х1с, т.е. 4 монеты. Вместо этого выдает 3.
При этом, когда ввожу 0,43$ віводит правильный ответ - 6 монет.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
27.09.2016, 13:35
Fat__Cat, вот для кого это писалось:
Цитата Сообщение от zer0mail Посмотреть сообщение
Чтоб центы не сбивались, напишите так:
int d = (int)(u+0.1);
а ?
Аналогично можно сделать и для других монет.
0
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 13:50  [ТС]
zer0mail, спасибо! int d = (int)(u+0.1); помогло, выводит правильный результат. Но при проверке не прошло при вводе 4,2$, вместо 18 монет выдает 23.
Можете объяснить, как это работает?
Я рассуждала так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
  float x = change/quater; // рассчет количества монет по 0,25.   0,41/0,25=1,64
        int a = (int)x; // из 1,64 оставляем целое число 1 (1 монета)
        
        float y = (change-a*quater)/ten; // рассчет количества монет по 0,10.   (0,41-1*0,25)/0,10=1,64
        int b = (int)y; // из 1,64 оставляем целое число 1 (1 монета)
        
        float z = (change-a*quater-b*ten)/five; //рассчет количества монет по 0,05.   (0,41-1*0,25-1*0,10)/0,05=1,2
        int c = (int)z; // из 1,2 оставляем целое число 1 (1 монета)
        
        float u = (change-a*quater-b*ten-c*five)/cent; //рассчет количества монет по 0,01.   (0,41-1*0,25-1*0,10-1*0,05)/0,01=1
        int d = (int)(u+0.1); // тут получим 1,1?
 
        int result=a+b+c+d;
Добавлено через 1 минуту
ture, спасибо. Но для это пока выше моего уровня. У меня самые первые занятия, я пока 0.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
27.09.2016, 13:54
Я же написал - аналогично... Т.е. как-то так:
int a = (int)(x+0.1);
int b = (int)(y+0.1);
int c = (int)(z+0.1);
0
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 13:59  [ТС]
Цитата Сообщение от zer0mail Посмотреть сообщение
Аналогично можно сделать и для других монет.
Спасибо! Теперь работает все. Но теперь я вообще не понимаю как это работает((
После каждого вычисления я получаю не целое число, а число+0,1?
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
27.09.2016, 14:12
Просле этого:
float z = (change-a*quater-b*ten)/five;
Вы получаете число с плавающей точкой, например 1.9999998... (дальше еще неважно что).
int c = (int)z;
отбрасывает дробную часть (0.9999998) и присваивает 'c' единицу.
А int c = (int)(z+0.1)
сначала получает 2.0999998, а уж потом отбрасывает дробную часть.
Вместо 0.1 можно было использовать 0.01 или 0.0001, т.к. ошибки возникают в 5-6м знаке или дальше.
1
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 14:20  [ТС]
Цитата Сообщение от zer0mail Посмотреть сообщение
Просле этого:
float z = (change-a*quater-b*ten)/five;
Вы получаете число с плавающей точкой, например 1.9999998... (дальше еще неважно что).
int c = (int)z;
отбрасывает дробную часть (0.9999998) и присваивает 'c' единицу.
А int c = (int)(z+0.1)
сначала получает 2.0999998, а уж потом отбрасывает дробную часть.
Вместо 0.1 можно было использовать 0.01 или 0.0001, т.к. ошибки возникают в 5-6м знаке или дальше.
ааа, 0,1 добавляется до преобразования в целое число. Теперь понятно.
Большое спасибо за ликбез
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
27.09.2016, 14:20
Помогаю со студенческими работами здесь

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

Жадный алгоритм С++
С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну операцию объединяются 2 счета и банк...

Жадный граф/алгоритм
Требуется написать программу с графическим интерфейсом: пользователь задаёт точки (A, B, C и т.д.). Далее соединяет между собой какие-то...

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

Жадный алгоритм на графе
Собственно, нужно написать программу поиска кратчайшего пути на графе &quot;жадным методом&quot;. То есть, дан ориентированный взвешенный граф...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru