Разложить число.

[КорДум]

А, да, номиналы в массиве номиналов должны идти от большего к меньшему. В моем варианте. Иначе всего лишь нужно поменять направление цикла.

[Hauts]

Именно такую задачу как-то решал на работе. Реализацию поищу

[pivnoibaron]

спасибо

[Zebestov]

KumoKairo, а накатай. Ну и на работу вместо pivnoibaron выходи!

[alatar]

Мне вот интересно, вот выложит тут кто-то алгоритм (в принципе задача о поиске пути в графе), получит pivnoibaron работу (если на интервью не завалится), а дальше что? Там же работать придется и не всегда можно будет вовремя получить решение задачи на форуме.

[Zebestov]

Я и alatar (почти одновременно) лишь высказали свое отношение к уровню современных "специалистов" и их подходом к своему профессиональному развитию в контексте этой темы. Обсуждать "критерии составления тестовых заданий" предлагаю где-нибудь во Флейме.

[GBee]

А задача прикольная, я че то в лоб ничего придумать не могу. Все упирается в кол-во монеток.

[-De-]

Не можете придумать хорошо - решите прямым перебором.

[Zebestov]

Ну как бы алгоритм делится на два: сначала мы само собой находим минимальную комбинацию, потом "растягиваем" ее до указанного числа путем дробления.

[alatar]

В принципе это один алгоритм. Дробление это тоже поиск минимальной комбинации, только в качестве цели берется число из уже полученной последовательности, пока не будет достигнута необходимая длина.