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

[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) !
Заранеее спасибо.

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

Вместо цикла - рекурсия.

[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 - он бы привёл более красивый вариант решения (рекурсия - его конёк).

Сообщение отредактировано: Федосеев Павел - 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 - он бы привёл более красивый вариант решения (рекурсия - его конёк).

Спасибо, щас разберусь!

[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 , в нахождении правильного решения подставлять циклическую проверку для всех остальных уравнений. Но вот как это реализовать не получается( ошибка на ошибке получается)
буду рад, если вы поможете еще раз

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

Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок:
1. Поиск в интернет дал мне несколько статей в Wikipedia (как русская, так и английская - выбор языка статьи в левой колонке, а английские версии всех статей по технике почему-то более полные, сложные), сайт алгоритмов "e-maxx.ru", ещё статьи в pdf(яндекс, гугл).
2. После прочтения я понял, что глубокий матаппатат есть для случая a*x1+b*x2+c=0 (как для чисел, так и для матриц). Это уравнение в целых числах имеет бесконечное множество решений (кстати, аналитическое - по формуле). Матаппарат разрабатывался 2,5 тысячи лет, есть наработки, доступные по лицензии Public Domain.
3. Изначальное условие задачи было об одном уравнении со многими переменными, фигурировала фраза, указывающее на конечное множество решений. Это привело меня к мысли об ограничении диапазона значений коэффициентов и корней уравнения только натуральными числами - в противном случае не выполняется условие конечности количества решений. Рекурсией я организовал цикл по всем неизвестным (пока n - не последний элемент, то вычисляется сумма слагаемых уравнения, когда n - последний, то проверяется сумма на равенство правой части уравнения).

К чему это я. Т.к. задача усложнилась, то с ходу я её не понял. Предлагаю тебе сформулировать её ещё раз (в том числе и для себя), ознакомиься с матаппаратом, создать несколько тестовых примеров, написать тестовую программу, решающую только эту задачу, выложить код. Лучше будет, если ты приведёшь словесное описание (или ссылку на пояснительный материал) алгоритма (способа) решения.

Сообщение отредактировано: Федосеев Павел - 11.01.2015 14:52

[zhdanow5a]

Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок:
1. Поиск в интернет дал мне несколько статей в Wikipedia (как русская, так и английская - выбор языка статьи в левой колонке, а английские версии всех статей по технике почему-то более полные, сложные), сайт алгоритмов "e-maxx.ru", ещё статьи в pdf(яндекс, гугл).
2. После прочтения я понял, что глубокий матаппатат есть для случая a*x1+b*x2+c=0 (как для чисел, так и для матриц). Это уравнение в целых числах имеет бесконечное множество решений (кстати, аналитическое - по формуле). Матаппарат разрабатывался 2,5 тысячи лет, есть наработки, доступные по лицензии Public Domain.
3. Изначальное условие задачи было об одном уравнении со многими переменными, фигурировала фраза, указывающее на конечное множество решений. Это привело меня к мысли об ограничении диапазона значений коэффициентов и корней уравнения только натуральными числами - в противном случае не выполняется условие конечности количества решений. Рекурсией я организовал цикл по всем неизвестным (пока n - не последний элемент, то вычисляется сумма слагаемых уравнения, когда n - последний, то проверяется сумма на равенство правой части уравнения).

К чему это я. Т.к. задача усложнилась, то с ходу я её не понял. Предлагаю тебе сформулировать её ещё раз (в том числе и для себя), ознакомиься с матаппаратом, создать несколько тестовых примеров, написать тестовую программу, решающую только эту задачу, выложить код. Лучше будет, если ты приведёшь словесное описание (или ссылку на пояснительный материал) алгоритма (способа) решения.

Нужно поставить дом, чтобы до самой далекой улицы расстояние было минимальным.

Гарантируется, что решение единственно и не существует 4 улиц образующих ромб. Ограничение по времени 1 секунда.

Входной файл:
В первой строке 2 <= N <= 100 – число улиц .
Дальше N строк по три дробных числа a, b, c – коэффициенты уравнения ax + by + c = 0 – задающего прямую – улицу.
Выходной файл:
x y – два подряд идущих числа – координаты дома с точностью не менее 5 знаков после запятой.
Примеры:
Вход:
2
1 0 0
0 1 0
Выход:
0 0

Вроде как подумал, делается также, но потом каждое из верных решений( для ax+by+c=0 их бесконенчо много. как вы подметили) подставляется в следущее уравнение и так до конца, в случае если подходит, оно выводится.Хотя я тут начал было сомневаться, тк чистым подбором задача может решаться намного больше 1 секунды.

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

Кажется, это задача не на диофантовы уравнения, а, скорее, на геометрию или алгебраическую геометрию - не помню точно название этого раздела.
Почему? Диофантовы уравнения исключительно целочисленны, а в условии: "координаты дома с точностью не менее 5 знаков после запятой".
Тут матмодель из геометрии, а решение - может быть, из динамического программирования или из чего-то другого - даже простых геометрических соображений.

[zhdanow5a]

Кажется, это задача не на диофантовы уравнения, а, скорее, на геометрию или алгебраическую геометрию - не помню точно название этого раздела.
Почему? Диофантовы уравнения исключительно целочисленны, а в условии: "координаты дома с точностью не менее 5 знаков после запятой".
Тут матмодель из геометрии, а решение - может быть, из динамического программирования или из чего-то другого - даже простых геометрических соображений.

Действительно, спасибо. Понял, что можно все решить с помощью определителя матрицы. методом крамера. В общем, если появятся вопросы напишу. Спасибо