Тестовое задание №2 для компании STC
- Дан массив уникальных целых чисел (int[] с), которые представляют возможные номиналы денежных монет.
Дано целое число, которое представляет сумму денег (а).
Необходимо вернуть значение, показывающее минимальное количество монет с заданными номиналами, которое вам потребуется чтобы составить сумму а.
Если сумма не может быть составлена, вернуть -99.
Например, для с = [1,3,5], a = 22
Ответ: 6
Допустимые варианты:
22 = 5 + 5 + 5 + 5 + 1 + 1
22 = 5 + 5 + 3 + 3 + 3 + 3
По сути ничего сверх сложного я не делал. Использовал алгоритм динамического программирования для нахождения результата. Скорость выполнения - O(nk), где n - сумма денег, k - количество разменных монет.
Для выполнения, нужно подкинуть файл с тестом Input.txt в папку TestProblemSTC#2.Main\bin\Debug\net6.0. Если не подкидывать - файл сам создастся и заполнится значиниями из тестового задания. Есть небольшая обработка ошибок на вводимые данные, чтобы алгоритм работал корректно. Кроме того, если данные выводятся некорректно - в консоли выскакивает напоминание как корректно ввести данные.
Итоговый результат помещается в файл, расположенный TestProblemSTC#2.Main\bin\Debug\net6.0\Output.txt Дополнительно дублируется в консоль.
Код старался аккуратно прокомментировать, возможно даже чересчур, но надеюсь будет понятно. Кроме того, добавлен небольшой проект с тестами, их немного, в основном для проверки алгоритма.
P.S.: Из основного мог где-то не заметить обработку некоторых ошибок или результата, но в целом сделал все возможное, что требовалось.
P.P.S.: Кроме того есть ссылка на мат. задание - https://disk.yandex.ru/i/xx2htEtuJESH4w