Tomsk Sysadmins Forum

Windows => Программирование => Topic started by: Ascaron on March 06, 2008, 21:31:05

Title: Помогите с задачей
Post by: Ascaron on March 06, 2008, 21:31:05

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

Title: Помогите с задачей
Post by: zhenya on March 07, 2008, 13:08:01

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();
}

Title: Помогите с задачей
Post by: ChCh on March 08, 2008, 09:33:32

Quote from: zhenya

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

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

Title: Помогите с задачей
Post by: nuclight on March 08, 2008, 23:09:41

Quote from: zhenya

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

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

Title: Помогите с задачей
Post by: zhenya on March 09, 2008, 12:01:25

Quote from: nuclight

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

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

Title: Помогите с задачей
Post by: never hood on March 09, 2008, 12:21:01

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

Title: Помогите с задачей
Post by: hyc on March 09, 2008, 19:12:51

Quote from: Ascaron

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

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