Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Fat__Cat
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
1

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

27.09.2016, 12:08. Просмотров 843. Ответов 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
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.09.2016, 12:08
Ответы с готовыми решениями:

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

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

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

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

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

11
zer0mail
2497 / 2125 / 225
Регистрация: 03.07.2012
Сообщений: 7,706
Записей в блоге: 1
27.09.2016, 12:48 2
Раз неправильно, то сколько выводит и сколько должна?
0
VAN0
59 / 59 / 53
Регистрация: 05.05.2013
Сообщений: 150
Завершенные тесты: 1
27.09.2016, 12:58 3
Возможно при вычислениях y,z,u необходимо явно преобразовать коэфициенты a,b,c к float.
0
zer0mail
2497 / 2125 / 225
Регистрация: 03.07.2012
Сообщений: 7,706
Записей в блоге: 1
27.09.2016, 13:01 4
Чтоб центы не сбивались, напишите так:
int d = (int)(u+0.1);
0
27.09.2016, 13:01
ture
532 / 340 / 206
Регистрация: 27.11.2014
Сообщений: 1,043
27.09.2016, 13:05 5
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
Fat__Cat
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 13:26  [ТС] 6
К примеру, сдача составляет 0,41$. Минимальное количество монет: 1х25с, 1х10с, 1х5с и 1х1с, т.е. 4 монеты. Вместо этого выдает 3.
При этом, когда ввожу 0,43$ віводит правильный ответ - 6 монет.
0
zer0mail
2497 / 2125 / 225
Регистрация: 03.07.2012
Сообщений: 7,706
Записей в блоге: 1
27.09.2016, 13:35 7
Fat__Cat, вот для кого это писалось:
Цитата Сообщение от zer0mail Посмотреть сообщение
Чтоб центы не сбивались, напишите так:
int d = (int)(u+0.1);
а ?
Аналогично можно сделать и для других монет.
0
Fat__Cat
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 13:50  [ТС] 8
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
zer0mail
2497 / 2125 / 225
Регистрация: 03.07.2012
Сообщений: 7,706
Записей в блоге: 1
27.09.2016, 13:54 9
Я же написал - аналогично... Т.е. как-то так:
int a = (int)(x+0.1);
int b = (int)(y+0.1);
int c = (int)(z+0.1);
0
Fat__Cat
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 13:59  [ТС] 10
Цитата Сообщение от zer0mail Посмотреть сообщение
Аналогично можно сделать и для других монет.
Спасибо! Теперь работает все. Но теперь я вообще не понимаю как это работает((
После каждого вычисления я получаю не целое число, а число+0,1?
0
zer0mail
2497 / 2125 / 225
Регистрация: 03.07.2012
Сообщений: 7,706
Записей в блоге: 1
27.09.2016, 14:12 11
Просле этого:
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
Fat__Cat
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 8
27.09.2016, 14:20  [ТС] 12
Цитата Сообщение от 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
27.09.2016, 14:20
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2016, 14:20

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

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

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


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru