Кол-во решений линейного уравнения., метод счетчика, незнаю как сделать. Опции

[zhdanow5a]

Всем привет! Пока решал одну задачу наткнулся на такую проблему:
ax+by+cz+dk...=sum Нужно вычислить кол-во решений в натуральных числах.
С клавиатуры вводится sum , коеффициенты(в данном случае это(x,y,z,k...), и кол-во данных коеффициентов, а значит кол-во слагаемых.
Понял вот что создаем 2 массива: один с коеффициентами, другой, забитый нулями , с a,b,c,d.... ТАк вот в чем загвоздка:
Не получается сделать нормальный цикл чтобы перебирались все значения, те чтобы сначала d+1 до dk=sum далее c+1 , потом снова d+1 д dk-sum.
Короче метод счет. Как это сделать, если количество любое ( до 500) !
Заранеее спасибо.

[Федосеев Павел]

Я попробовал решить примерно так.
На входе:
a - массив коэффициентов линейного диофантового уравнения (все значащие >=1)
n - размер массива
sum - сумма
На выходе:
Count - количество решений
Чтобы не было разночтений, приведу вид уравнения, которое решается
a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]=sum,
где
a[i] - коэффициенты уравнения, все a[i]>=1
x[i] - искомые переменные, все x[i]>=1.

Код

program LinearDiophantineEquation;

const
  n = 5;
type
  TArray = array [1..n] 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] := 0;
        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
  a:     TArray = (1, 2, 3, 4, 5);
var
  sum:   integer;
  Count: QWord;
begin
  sum := 121;
  writeln;
  Count := Solve(n, a, sum);
  Write('There is ', Count, ' variants of a solutions.');
end.

Это решение линейного диофантового уравнения со следующими ограничениями:
- коэффициенты - натуральные числа (>=1);
- решения x ищутся на множестве натуральных чисел (>=1).

PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк).

Сообщение отредактировано: Федосеев Павел - 5.01.2015 13:57

[zhdanow5a]

Я попробовал решить примерно так.
На входе:
a - массив коэффициентов линейного диофантового уравнения (все значащие >=1)
n - размер массива
sum - сумма
На выходе:
Count - количество решений
Чтобы не было разночтений, приведу вид уравнения, которое решается
a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]=sum,
где
a[i] - коэффициенты уравнения, все a[i]>=1
x[i] - искомые переменные, все x[i]>=1.

Код

program LinearDiophantineEquation;

const
  n = 5;
type
  TArray = array [1..n] 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] := 0;
        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
  a:     TArray = (1, 2, 3, 4, 5);
var
  sum:   integer;
  Count: QWord;
begin
  sum := 121;
  writeln;
  Count := Solve(n, a, sum);
  Write('There is ', Count, ' variants of a solutions.');
end.

Это решение линейного диофантового уравнения со следующими ограничениями:
- коэффициенты - натуральные числа (>=1);
- решения x ищутся на множестве натуральных чисел (>=1).

PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк).

Разобрался, программу подстроил под себя. Теперь вопрос , как эт этого перейти к системе уравнений ax+by+c=0 . Сумма =0 , вводится матрица по 3 элемента в строке (a,b,c) , n строк, . Далее я так понимаю нужно в функции f , в нахождении правильного решения подставлять циклическую проверку для всех остальных уравнений. Но вот как это реализовать не получается( ошибка на ошибке получается)
буду рад, если вы поможете еще раз