Получить все способы выплаты заданной суммы с помощью монет определенного достоинства - Turbo Pascal

Узнай цену своей работы

Формулировка задачи:

Некоторая сумма представлена в натуральным числом N. Получить все способы выплаты этой суммы с помощью монет достоинством a1, а2, ..., am.

Решение задачи: «Получить все способы выплаты заданной суммы с помощью монет определенного достоинства»

textual
Листинг программы
program test;
 
const
  M = 5;
type
  TArray = array [1..M] of integer;
 
  procedure ShowSolve(EtSum, n: integer; const a, x: TArray);
  var
    sum, i: integer;
  begin
    sum := 0;
    for i := 1 to n do
    begin
      sum := sum + a[i] * x[i];
      Write(a[i], '*', x[i]);
      if i <> n then
        Write('+');
    end;
    Write('=', sum);
    if sum = EtSum then
      writeln(' - Ok')
    else
    begin
      writeln(' - wrong solution!');
      halt;
    end;
  end;
 
  {функция решает диофантово уравнение и возвращает количество решений}
  function Solve(n: integer; const a: TArray; EtSum: integer): QWord;
  var
    Count: QWord;
    x: TArray;
 
    function f(i, sum: integer): integer;
    begin
      if sum < 0 then
        exit;
      if i = 0 then
        exit;
      if i = 1 then
      begin
        if sum mod a[1] = 0 then
        begin
          Inc(Count);
          x[1] := sum div a[1];
          Write('Solution #', Count: 8, ' is: ');
          ShowSolve(EtSum, n, a, x);
        end;
      end
      else
      begin
        x[i] := -1;
        repeat
          Inc(x[i]);
          if sum - a[i] * x[i] <= 0 then
            break;
          f(i - 1, sum - a[i] * x[i]);
        until False;
      end;
    end;
 
  begin
    Count := 0;
    f(n, EtSum);
    Solve := Count;
  end;
 
var
  DenominationCoin: TArray = (1, 2, 5, 10, 15);
var
  sum: integer;
  Count: QWord;
begin
  sum := 121;
  writeln;
  Count := Solve(M, DenominationCoin, sum);
  Write('There is ', Count, ' variants of a solutions.');
end.

Объяснение кода листинга программы

  1. Создается переменная DenominationCoin, которая представляет собой массив из пяти элементов, представляющих достоинство монет (1, 2, 5, 10, 15).
  2. Создается переменная sum, которая представляет собой сумму, которую нужно выплатить (в данном случае 121).
  3. Создается функция Solve, которая принимает в качестве параметров n (количество монет), a (массив с возможными значениями для каждой монеты) и EtSum (сумма, которую нужно выплатить). Эта функция возвращает количество возможных решений.
  4. Внутри функции Solve создается вспомогательная функция f, которая рекурсивно находит все возможные решения для каждой монеты.
  5. В функции f используется рекурсия для поиска всех возможных значений для каждой монеты. Если текущая сумма меньше нуля, функция выходит из цикла. Если текущая монета - первая, проверяется, делится ли сумма на значение этой монеты без остатка. Если да, то увеличивается счетчик решений и значение этой монеты устанавливается равным найденной сумме. Затем вызывается функция ShowSolve для вывода найденного решения.
  6. После того, как все монеты были обработаны, функция f возвращает значение, которое было найдено для последней монеты. Это значение передается в функцию Solve, которая возвращает общее количество решений.
  7. В основной части программы создается экземпляр переменной DenominationCoin и присваивается значение sum. Затем вызывается функция Solve с этими значениями, и результат выводится на экран.

Оцени полезность:

7   голосов , оценка 4.429 из 5
Похожие ответы