Question

Доказать, что любую целочисленную денежную сумму,большую 7 руб., можно выплатить без сдачи трешками и пятерками.Для данного n > 7 найти такие целые неотрицательные a и b, что 3a +5b = n. Нужно написать на делфи

Answer 1

Var
    a, b, n: integer;

begin
    read(n);
    if n<=7 then exit;
   
    for a := 1 to n do
        for b := 1 to n do
            if 3 * a + 5 * b = n then
                writeln('3 * ', a, ' + 5 * ', b, ' = ', n);
end.

Answer 2

Для доказательства того, что любую целочисленную денежную сумму, большую 7 рублей, можно выплатить без сдачи трешками и пятерками, нам необходимо найти такие целые неотрицательные числа a и b, что 3a + 5b = n, где n > 7.

Для решения этой задачи мы можем использовать алгоритм нахождения наименьшего общего кратного (НОК) двух чисел. НОК двух чисел a и b обозначается как lcm(a, b) и равно произведению a и b, деленному на их наибольший общий делитель (НОД(a, b)).

Алгоритм нахождения НОК двух чисел:

1. Найдите НОД(a, b) с помощью алгоритма Евклида. 2. Вычислите НОК(a, b) как произведение a и b, деленное на НОД(a, b).

Теперь, чтобы найти такие целые неотрицательные числа a и b, что 3a + 5b = n, мы можем использовать НОК(3, 5) = 15. Таким образом, любую сумму n > 7 рублей можно выплатить без сдачи трешками и пятерками, используя комбинацию трешек и пятерок в количестве, равном n / 15, и добавляя оставшиеся рубли, если они есть.

Ниже представлен пример кода на Delphi, который реализует этот алгоритм:

program Change;

var
  n, a, b: Integer;

begin
  Write('Введите сумму n (n > 7): ');
  ReadLn(n);

a := n div 3;
  b := (n - 3 * a) div 5;

WriteLn('Можно выплатить сумму ', n, ' рублей без сдачи трешками и пятерками следующим образом:');
  WriteLn('Трешки: ', a);
  WriteLn('Пятерки: ', b);
  WriteLn('Остаток: ', n - 3 * a - 5 * b, ' рублей');
end.

В этом примере мы сначала запрашиваем сумму n от пользователя. Затем мы вычисляем количество трешек a, которое равно n, деленному на 3, и количество пятерок b, которое равно остатку от деления (n - 3 * a) на 5. Наконец, мы выводим результат на экран, показывая количество трешек, пятерок и оставшийся остаток.

Примечание: Обратите внимание, что этот алгоритм предполагает, что у нас есть достаточное количество монет трешек и пятерок для выплаты суммы n. Если у нас нет достаточного количества монет, то этот алгоритм не сработает.