Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
#1

Проверить, можно ли набрать заданную сумму монетами заданных номиналов - C++

20.11.2010, 03:36. Просмотров 991. Ответов 11
Метки нет (Все метки)

Доброго времени суток, помогите с програмой

Имеются монеты c различными фиксированными номиналами, выраженными в копейках (например, 3 и 5 копеек) в достаточном количестве. Написать программу COINS, которая:
а) определяет, можно ли представить заданную сумму S (выраженную в копейках), пользуясь монетами заданных номиналов,
б) если это возможно, то представляет эту сумму с помощью минимального количества монет.
Входные данные: содержат в первой строке сумму S (0 < S < 1000000000), во второй строке - N - количество различных номиналов (0 < S < 20), а в следующих N строках - А1 ... АN - номиналы (в порядке возрастания), которые можно использовать (0 < A1 < A2 < ... < AN < 1000000000)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2010, 03:36     Проверить, можно ли набрать заданную сумму монетами заданных номиналов
Посмотрите здесь:

Количество плиток, которое можно уложить на заданную площадь C++
C++ Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек)
Найти координаты первого вхождения в заданную строку подстроки, состоящей из двух одинаковых заданных символов C++
С помощью заданных функций проверить сколько можно построить различных треугольников C++
C++ Проверить, попадает ли точка в заданную область
C++ Проверить, кратно ли произведение двух заданных натуральных чисел третьему числу
Проверить наличие в последовательности пяти подряд идущих заданных символов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2010, 08:26     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #2
Вариант решения:
- Создаем массив (например типа bool), размером S+1.
- Все элементы массива делаем false, а элементы с индексами совпадающими с имеющимися номиналами делаем true. (Для примера
3 и 5 копеек
mas[3]=true, mas[5]=true). Учитываем при этом верхнюю границу массива.
- Далее алгоритм такой: Проходим массив от 1 до S+1. Если попадается mas[i]==false, то ничего не делаем. Если попадается mas[i]==true, то перебираем все имеющиеся номиналы и делаем элементы массива mas[i+(очередной номинал)]=true. Естественно учитываем верхнюю границу массива.
- По окончании прохода смотрим на значение mas[S] - если false, то сумма недостижима, если true то достижима.
Для представления суммы с помощью минимального количества монет алгоритм следующий:
- создаем массив типа int mas1[N] (количество различных номиналов), обнуляем его значения.
- Затем в цикле (пока не достигнем mas[0], начинаем с mas[S]) выполняем следующее. Перебираем с максимального значения номиналов. Если mas[i-(значение номинала)]==true, то mas1[(значение номинала)-1]++ и переходим на mas[i-(значение номинала)].
- По достижении mas[0]. Выводим кол-во монет различных номиналов из mas1[].
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
22.11.2010, 17:20  [ТС]     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #3
а код можешь написать?
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 17:23     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #4
asotel, А самому слабо?
А откуда эта задача? Кто вам ее задал?
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
22.11.2010, 17:34  [ТС]     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #5
одна из моих лаб

Добавлено через 3 минуты
я отметил в первом массиве все элементы типа false, потом считал номиналы в другой массив они там хранятся от 1 и до количиства их, а как слепить теперь что элемент под номеров таким то занести в в первом массиве под таким же элементом true

Добавлено через 1 минуту
получилось типа m[1]=3 m[2]=5,
а как теперь 3тему элементу первого массива поставить true?
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 17:55     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #6
Итак получилось m[0]=3, m[1]=5.
Теперь сначало делаем (если первый массив - mas[S+1]), то так: mas[m[0]]=true; mas[m[1]]=true; Лучше это сделать в цикле.
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
22.11.2010, 19:31  [ТС]     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Итак получилось m[0]=3, m[1]=5.
Теперь сначало делаем (если первый массив - mas[S+1]), то так: mas[m[0]]=true; mas[m[1]]=true; Лучше это сделать в цикле.
я не пойму хода твоих мыслей, вот у меня массив mas[20]='false'; выглядет так:
false
false
false второй массив выглядет m[количество веденных номиналов];
.... к примеру M[0]=3;
M[1]=5; 3 и 5 это номиналы, а не ячейки массива, и соответственно этим номиналам нужно поменять ячейки mas[20] на true, как ты массив в ячейку массива впихнул?

напиши плиз хоть кусок кода

Добавлено через 30 минут
Спасибо, у меня получилось заполнить первый масив)))
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 19:36     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #8
asotel, ладно, за настойчивость в достижении цели напишу весь код..
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
22.11.2010, 20:03  [ТС]     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вариант решения:

Для представления суммы с помощью минимального количества монет алгоритм следующий:
- создаем массив типа int mas1[N] (количество различных номиналов), обнуляем его значения.
- Затем в цикле (пока не достигнем mas[0], начинаем с mas[S]) выполняем следующее. Перебираем с максимального значения номиналов. Если mas[i-(значение номинала)]==true, то mas1[(значение номинала)-1]++ и переходим на mas[i-(значение номинала)].
- По достижении mas[0]. Выводим кол-во монет различных номиналов из mas1[].
РАстолкуй мне вот это

у меня
C++
1
2
3
4
5
6
7
8
9
10
11
12
char mas[20];   // true false хранит
int no[20];  // хранит номиналы
 
мне нужно 
int new[20]=0; // создать масив
for(i=mas[20];i>=mas[1];i--)
{
   if (mas[i]= true)
   {  new[i-1 (зачем -1) ]++;          //то mas1[(значение номинала)-1]++ 
    а тут что зделать я не понял)  }  // и переходим на mas[i-(значение номинала)].
            for(i=1;i<=20;i++)
           cout<<new[i]<<endl;   // По достижении mas[0]. Выводим кол-во монет различных номиналов из mas1[]

как то так?????
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:11     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #10
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
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
 
int main ()
{
    int N, S, i, j, **mas;
    bool *mas1;
    scanf("%d %d\n", &S, &N);
    mas1=new bool[S];
    mas=new int*[N];
    for(i=0; i<S; i++)
        mas1[i]=false;
    for(i=0; i<N; i++)
    {
        mas[i]=new int[2];
        scanf("%d", &mas[i][0]);
        mas[i][1]=0;
        if(mas[i][0]<=S)
        mas1[mas[i][0]-1]=true;
    }
    for(i=0; i<S; i++)
    {
        if(mas1[i])
        {
            for(j=0; j<N; j++)
                if(mas[j][0]+i<S)
                    mas1[mas[j][0]+i]=true;
        }
    }
    if(!mas1[S-1])
        printf("No");
    else
    {
        printf("Yes\n");
        i=S-1;
        while(i!=-1)
        {
            for(j=N-1; j>=0; j--)
                if(mas1[i-mas[j][0]] && i-mas[j][0]>=-1)
                {
                    mas[j][1]++;
                    i-=mas[j][0];
                    break;
                }
        }
        for(i=0; i<N; i++)
            printf("Nominal %d - %d raz\n", mas[i][0], mas[i][1]);
    }
    return 0;
}
Весь код здесь. Если интересует алгоритм то завтра задавайте вопросы.
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
22.11.2010, 20:21  [ТС]     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #11
Огромное Спасибо, Алгоритм я понял)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2010, 20:25     Проверить, можно ли набрать заданную сумму монетами заданных номиналов
Еще ссылки по теме:

Проверить,верно ли, что рекуррентный процесс заданных вычислений завершится C++
C++ Проверить, упорядочены ли три заданных вещественных числа по возрастанию / убыванию и изменить их по условию
C++ Проверить наличие заданных цифр в числе
Проверить равенство двух заданных треугольников по указанному признаку C++
Создать программу вычисления указанной величины; результат проверить при заданных исходных значениях C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:25     Проверить, можно ли набрать заданную сумму монетами заданных номиналов #12
Цитата Сообщение от asotel Посмотреть сообщение
Огромное Спасибо, Алгоритм я понял)))
Я это тоже понял.
Yandex
Объявления
22.11.2010, 20:25     Проверить, можно ли набрать заданную сумму монетами заданных номиналов
Ответ Создать тему
Опции темы

Текущее время: 11:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru