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

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

Восстановить пароль Регистрация
 
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
20.11.2010, 03:36     проверить можна ли вывести заданую суму монет из заданых номиналов #1
Доброго времени суток, помогите с програмой

Имеются монеты 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++ Даны целые числа K,N, а также K набор целых чисел по N элементов в каждом наборе. Вывести суму его элементов для каждого набора
C++ Где можна скачать книгы по С+ ?
Произведение 2х наименьших из 3х заданых C++
C++ Из 2 заданых бинарных файлов вывести в 3 разность соответствующих чисел
Определить порядковый номер того дня високосного года, который имеет заданую дату и месяц C++
C++ Чем можна дизассемблить?
C++ Определить, сколько может быть построено квадратов с вершинами в заданых точках
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++ Создать класс прямоугольных треугольников заданых своими катетами
С++ Найти суму n1 цифер дробовой части действительного числа и вывести на экран C++

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

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

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