Помогите с задачей

[Ascaron]

Учусь, никак немогу додуматься до решения задачи:
Дано натуральное число N(N<=99). Получить все способы выплаты суммы N с помощью монет достоинством 1,5,10,20 копеек.
Помогите кто-нибудь хотя бы с алгоритмом, буду очень признателен, без этой задачи не зачитывают практику

[zhenya]

1) Вариантов бесконечно много.
2)
пример

Code: [Select]

#include<iostream>
#include<conio.h>

using namespace std;

void main()
{
     int N, i = 0;
     static int moneti[4] = {20,10,5,1};
     cout << "vvedite 4islo \n";
     cin >> N;
     /* Пока не разложили на все слогаемые */
     while (N > 0)
     {
          /* Если нашли очередной слогаемое - выводим его,
           если он последний - после него перевод строки, иначе ' ',
           вычитаем из N слогаемое и не увеличиваем i (может быть
           несколько равных слогаемых) */

          if ((N - moneti[i] >= 0))
          {
               printf("%d%c", moneti[i], N > moneti[i] ? ' ' : '\n');
               N -= moneti[i];
               continue;
          }
          /* i - не слогаемое - проверяем следующий */
          i++;
     }
     getch();
}

[ChCh]

1) Вариантов бесконечно много.
2) пример

этот пример даст только один вариант размена,  а нужны все.

[nuclight]

1) Вариантов бесконечно много.

Вариантов отнюдь не бесконечно много. Тут достаточно простая в своей математика: 20a+10b+5c+d=N, надо найти количество комбинаций коэффциентов a,b,c,d. Можно в лоб, 3 вложенных цикла - внешний по a, которое, очевидно, может принимать значений от нуля до N div 20. В следующем делать аналогичный перебор по b, но сумма уже будет не N, а N-20a. И т.д., принцип, думаю, понятен.

[zhenya]

Вариантов отнюдь не бесконечно много. Тут достаточно простая в своей математика: 20a+10b+5c+d=N, надо найти количество комбинаций коэффциентов a,b,c,d. Можно в лоб, 3 вложенных цикла - внешний по a, которое, очевидно, может принимать значений от нуля до N div 20. В следующем делать аналогичный перебор по b, но сумма уже будет не N, а N-20a. И т.д., принцип, думаю, понятен.

3 вложенных цикла не дадут все варианты :\ ведь сумма может быть представлена чисто из 5 или 10+5+5 вместо 20.)

[never hood]

если коэффициенты могут принимать нулевые значения (а что этому мешает?) то все нормально!

[hyc]

Учусь, никак немогу додуматься до решения задачи:
Дано натуральное число N(N<=99). Получить все способы выплаты суммы N с помощью монет достоинством 1,5,10,20 копеек.
Помогите кто-нибудь хотя бы с алгоритмом, буду очень признателен, без этой задачи не зачитывают практику

SICP в русском переводе http://lisp.tomsk.ru/wordpress/wp-content/...007/08/sicp.pdf , страница 55, именно ваша задача, описание алгоритма и пример решения.