Паскаль. Основы программирования

       

Задачи с применением НОД


Пример 5. Один мастер делает на длинной ленте пометки синим карандашом от ее начала через каждые 36 см. Другой мастер делает пометки красным карандашом от начала через каждые 25 см. Может ли синяя пометка оказаться на расстоянии 1 см от какой-нибудь красной?

Решение

Ответ: может. Например, 9-я синяя пометка и 13-я красная находятся друг от друга на расстоянии 1 см, так как 13

25 - 9
36 = 1.

В этой задаче нам фактически надо было найти какое-нибудь решение в целых числах одного из уравнений 25x - 36y = 1, 25x - 36y = - 1

или доказать, что таких решений нет. Существует стандартная процедура, с помощью которой всегда можно найти решение уравнения

 если
 Продемонстрируем ее на нашей задаче. Выпишем все шаги алгоритма Евклида для нахождения НОД(36; 25):

    36 = 25

1 + 11; 25 = 11
2 + 3; 11 = 3
3 + 2; 3 = 2
1 + 1.

 Перепишем эту цепочку равенств по остаткам:

11 = 36 - 25

1; 3 = 25 - 11
2; 2 = 11 - 3
3; 1 = 3 - 2
1.

Тогда получим:

               1 = 3 - (11 - 3

3) = 3
4 - 11 = (25-11
2)
4 - 11 = 25
4 - 11
9 =

= 25

4 - 11
9 = 25
4 - (36 - 25)
9 = 25
13 - 36
9.

В результате получается равенство 25

13 - 36
9 = 1, дающее одно решение уравнения 25x - 36y = 1.

Определение. Неопределенные уравнения - уравнения, содержащие более одного неизвестного. 



Под одним решением неопределенного уравнения понимается совокупность значений неизвестных, которая обращает данное уравнение в верное равенство.

Уравнения вида ax + by = c, где a, b, c - целые числа, отличные от нуля

Теорема 1. Если НОД (a; b) = d, то существуют такие целые числа x и y, что  имеет место равенство

.

(Это равенство называется линейной комбинацией или линейным представлением наибольшего общего делителя двух чисел через сами эти числа.)

Теорема 2. Если в уравнении ax + by = l (a, b) = 1, то уравнение имеет по крайней мере одно целое решение.

Справедливость этой теоремы следует из теоремы 1. Таким образом, чтобы найти одно целое решение уравнения ах + by = 1, если (а, b) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и b.


Пример. Найти целое решение уравнения 15x + 37y = 1.
Решение
1) Применим алгоритм Евклида и найдем НОД(15, 37):

НОД(15, 37) = 1
2) Выразим 1 последовательно через неполные частные и остатки, используя полученные равенства, начиная с конца:
, т. е.
x0
= 5, y0 = -2.
Теорема 3. Если в уравнении ах + by = с (а, b) = d > 1 и с не делится на d, то уравнение целых решений не имеет.
Пример. Найти целое решение уравнения 16x - 34y =  7.
Решение
(16, 34) = 2, 7 не делится на 2, уравнение целых решений не имеет.
Теорема 4. Если в уравнении ах + by = с (a, b) = d > 1 и c делится на d, то оно равносильно уравнению а1х + b1у = c1, в котором (a1, b1) = 1.
Теорема 5. Если в уравнении ах + by = с (а, b) = 1, то все целые решения этого уравнения заключены в формулах:

где x0, y0 - целое решение уравнения ах + by = 1, t - любое целое число.
Приведенные теоремы позволяют установить следующее правило решения в целых числах уравнения ах + by = с, где (а, b) = 1:
1) находится целое решение уравнения ах + by = 1 путем представления 1 как линейной комбинации чисел а и b (существуют и другие способы отыскания целых решений этого уравнения, например при использовании цепных дробей);
2) составляется общая формула целых решений данного уравнения:

где x0, y0 - целое решение уравнения ах + by = 1, t—любое целое число.
Придавая t определенные целые значения, можно получить частные решения данного уравнения: наименьшие по абсолютной величине, наименьшие положительные (если можно) и т. д.
Пример 1. Найти целые решения уравнения 407х - 2816у = 33.
Решение
1) Упрощаем данное уравнение, приводя его к виду 37х - 256у = 3.
2) Решаем уравнение 37x - 256y = 1.

 

.
3) Найдем решения данного уравнения по формулам:

 

Ответ:

Для составления программы решения неопределенных уравнений, нам предстоит решить три задачи:
1) нахождение НОД, для последующего выяснения числа решений уравнения, - это легко сделать с помощью известной процедуры;
2) нахождение одного решения уравнения вида ах + by = 1 и


3) последующий вывод обобщенных результатов решения с учётом знаков a и b, и с учетом формулы
 где t - произвольное целое число.
Первую задачу можно решить с помощью рекурсивной функции:
         Function nod(a, b : integer) : integer;
              begin
                if b = 0 then nod := abs(a)
                             else  nod := nod(abs(b), abs(a) mod abs(b))
             end;
Для решения второй задачи применять методику нахождения остатков от деления, а затем выполнять процесс в обратном порядке для компьютера нерационально. Проще составить два цикла с параметром, перебирающие числа от наименьшего (который равен наибольшему по модулю, но берётся с противоположным знаком) до наибольшего из коэффициентов (почему, будут существовать решения уравнения, меньшие или равные его коэффициентов? Докажите сами).
if abs(a) > abs(b) then max := abs(a) else max := abs(b);
            for x := -max to max do
               for y := -max to max do
Для вывода результатов следует рассмотреть несколько случаев, в зависимости от знаков коэффициентов a и b, а также, чтобы не получать несколько ответов, включить оператор безусловного перехода, после завершения проверки каждого условия.
 Procedure
The_equation(a, b : integer);  {Решение уравнения ax + by = 1}
      label 1;
      var
            max, x, y, n : integer;
      begin
        if (nod(a, b) <> 1) then
writeln('Уравнение не имеет решений');
        if abs(a) > abs(b) then
max := abs(a) else max := abs(b);
        for  x := -max  to max  do
         for  y := -max  to  x  do
           begin
            if (a*x + b*y = 1) and
(a > 0) and (b > 0)
             then begin  writeln('Решения уравнения x = ', x, '+', b,'*t, y = ', y, '-', a, '*t,');
                               writeln('где t - произвольное целое число'); goto 1 end;
         if (a*x + b*y = 1) and (a < 0) and (b > 0)
           then begin  writeln('Решения уравнения x = ', x, '+', b,'*t, y = ', y, ' ', a, '*t,');


                              writeln('где t - произвольное целое число'); goto 1 end;
         if (a*x + b*y = 1) and (a > 0) and (b < 0)
           then begin writeln('Решения уравнения x = ', x, ' ', b,'*t, y = ', y, '-', a, '*t,');
                             writeln('где t - произвольное целое число'); goto 1 end;
         if (a*x + b*y = 1) and (a < 0) and (b < 0)
           then begin writeln('Решения уравнения x = ', x, ' ', b,'*t, y = ', y, ' ', a, '*t,');
                             writeln('где t - произвольное целое число'); goto 1 end
       end;
 1:  end;
Полностью программа решения уравнений вида ах + by = 1 будет такой:
Program Problem5;
    uses WinCrt;
    var
        a, b : integer;
{---------------------------------------------------------------------------------------------------------}
    Function nod(a, b : integer) : integer;
        begin
           if b = 0 then nod := abs(a)
                        else nod := nod(abs(b), abs(a) mod abs(b))
        end;
{----------------------------------------------------------------------------------------------------------}
Procedure
The_equation(a, b : integer);  {Решение уравнения ax + by = 1}
      label 1;
      var
            max, x, y, n : integer;
      begin
        if (nod(a, b) <> 1) then
writeln('Уравнение не имеет решений');
        if abs(a) > abs(b) then
max := abs(a) else max := abs(b);
        for  x := -max  to max  do
         for  y := -max  to  x  do
           begin
            if (a*x + b*y = 1) and
(a > 0) and (b > 0)
             then begin  writeln('Решения уравнения x = ', x, '+', b,'*t, y = ', y, '-', a, '*t,');
                               writeln('где t - произвольное целое число'); goto 1 end;
         if (a*x + b*y = 1) and (a < 0) and (b > 0)
           then begin  writeln('Решения уравнения x = ', x, '+', b,'*t, y = ', y, ' ', a, '*t,');
                              writeln('где t - произвольное целое число'); goto 1 end;


         if (a*x + b*y = 1) and (a > 0) and (b < 0)
           then begin writeln('Решения уравнения x = ', x, ' ', b,'*t, y = ', y, '-', a, '*t,');
                             writeln('где t - произвольное целое число'); goto 1 end;
         if (a*x + b*y = 1) and (a < 0) and (b < 0)
           then begin writeln('Решения уравнения x = ', x, ' ', b,'*t, y = ', y, ' ', a, '*t,');
                             writeln('где t - произвольное целое число'); goto 1 end
       end;
 1:  end;
{-----------------------------------------------------------------------------------------------------------}
    begin
       write(' Введите значение коэффициента при x,  a '); readln(a);
       write('Введите значение коэффициента при y,  b '); readln(b);
       The_equation(a, b);
    end.
 

Содержание раздела