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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ таблица знакомств http://www.cyberforum.ru/cpp-beginners/thread194103.html
помогите написать программу Имеется N человек и прямоугольная таблица знакомств А, в которой элемент A равен 1, если человек i знаком с человеком j, и, соответственно, наоборот, А=А. Выяснить,...
C++ Перевод кода из Паскаля на C++ обясните несколько строчек из паскаля, или перевидите их в с++ j1,er числа, i1 char вроде строки val(i1,j1,er); writeln(''); readln; write(i,' '); http://www.cyberforum.ru/cpp-beginners/thread194101.html
C++ Наследование
Тёмного времени суток! Столкнулся с проблемой, основной смысл которой заложен ниже class Parent { void F() = 0; } class Child: protected Parent { void F() {}
Цикл сортировки. C++
Доброго времени суток. Такая вот у меня проблема. Предположим у меня есть два массива: {1, 2, 2, 1, 3, 3, 2, 1, 0, 0} {1, 0, 1, 2, 0, 1, 2, 3, 2, 3} как мне их упорядочить чтобы получить в итоге:...
C++ Сортировка массива [C++] http://www.cyberforum.ru/cpp-beginners/thread194082.html
Доброго времени суток, уважаемые. Не получается сделать сортировку массива, а именно: необходимо сделать сортировку каждого из 3х столбцов в порядке убывания элементов. Метод сортировки неважен....
C++ Потоки вывода Даже не знаю как правильно сформулировать, но хотел сделать примерно следующее и вошел в ступор. Как создать класс, который смог бы привязаться к потокам cout/clog/cerr по выбору пользователя? То... подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2010, 08:26
Вариант решения:
- Создаем массив (например типа 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[].
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru