алгоритм евклида Опции

[Feagor]

условие в прикрепленном файле.
вот то что сделал, дальше что делать не врубаюсь

uses crt;
 function nod(a, b:longint):longint;
 begin
  if (a=0) or (b=0) then if a=0 then nod:=b
                                else nod:=a
                    else if a >= b then nod:=nod(a mod b,b)
                                   else nod:=nod(a,b mod a);
 end;
 var f,g,i:integer;
 ff,aa:array[1..1000] of integer;
  begin
    clrscr;
    read(f,g);
    ff[1]:=f;
    ff[2]:=g;
    i:=2;
    while ff[i] mod ff[i-1]>0 do
        begin
         inc(i);
         ff[i]:=ff[i-1] mod ff[i-2];
         aa[i]:=ff[i-1] div ff[i-2];
        end;
    readkey;
  end.

Сообщение отредактировано: Feagor - 10.01.2008 16:11

[Tan]

Тут материал с пояснением.

[Feagor]

2 Tan - посмотри внимательно задание, и посмотри пожалуста, что у меня сделано! на той ссылке лежит разъянению функции, которая считает нод!

 function nod(a, b:longint):longint;
 begin
  if (a=0) or (b=0) then if a=0 then nod:=b
                                else nod:=a
                    else if a >= b then nod:=nod(a mod b,b)
                                   else nod:=nod(a,b mod a);
 end;

она у меня написана, проблема в том что вообще делать дальше?!

[Tan]

Алгоритм Евклида - это поиск наибольшего общего делителя двух целых чисел, что и сделано в приведённой мной ссылке. Не вижу проблемы.

[Michael_Rybak]

Tan, имеется ввиду расширенный алгоритм Эвклида. Посмотри объяснение, присоединенное к первому посту.

Feagor, тебе нужно кроме f и a еще считать коэффициенты p и s такие, что для любого i:

f[0] * s[i] + f[1] * p[i] = f[i].

Как это сделать, написано в том объяснении.

Ответом будет пара (s[n], p[n]).

[Feagor]

2 Michael_Rybak в каком объяснении?я туплю?=)
а с вариантом Б) и В) что делать?

Сообщение отредактировано: Feagor - 10.01.2008 20:04

[Michael_Rybak]

б) - сократи уравнение на нод и подумай что дальше делать

в) - делай то что там сказано. вычисляй не s[i] и p[i] а только s[i].

[Feagor]

спасип, буду разбиратся! понял на счет объяснения, туплю!!!

Сообщение отредактировано: Feagor - 10.01.2008 20:05

[Feagor]

после десятикратного прочтения объяснения, до сих пор не могу понять как искать u и v...

[Michael_Rybak]

u=s[n]
v=p[n]

[Feagor]

а n- это последний член? или как?

[Feagor]

по материалам algolist.manual.ru решил сделать вот так:

uses crt;
 procedure nod(a, b:longint; var d,x,y:longint);
 var q,r,x1,x2,y1,y2:longint;
 begin
   if b=0 then
        begin
          d:=a;
          x:=1;
          y:=0;
        end
   else
        begin
          x2:=1;x1:=0;y2:=0;x1:=1;
          while b>0 do
                begin
                  q:=a div b;
                  r:=a-q*b;
                  x:=x2-q*x1;
                  y:=y2-q*y1;
                  a:=b;b:=r;x2:=x1;x1:=x;y2:=y1;y1:=y;
                end;
        end;
   d:=a; x:=x2;y:=y2;
 end;
 var a,b,d,x,y:longint;
 begin
   clrscr;
   Write('Input f,g');
   Read(a,b);
   nod(a,b,d,x,y);
   writeln(d,'   ',x,'   ',y);
   readkey;
 end.

заработало!!! остались б и в

Сообщение отредактировано: Feagor - 11.01.2008 12:33

[Michael_Rybak]

работает неправильно на каком тесте?

[Feagor]

2 Michael_Rybak попровил свои кривые ручки - заработало, помоги с написанием б

[Michael_Rybak]

про б я тебе уже сказал что делать.

[Feagor]

ну вот смотри, берем уравнение fu+gv=nod(f,g) делим его на нод fu/nod(f,g)+fg/nod(f,g)=1 выносим за скобку u и g u*(f/nod(f,g))+v*(g/nod(f,g))=1, тогда m=1; k=f/nod(f,g); l=g/nod(f,g) Я правильно тебя понял так делать?

Добавлено через 1 мин.
тольков объяснении кажись что-то другое написано

[Michael_Rybak]

Не совсем так.

Тебе нужно вычислить не m, k и l - они тебе даны! А вычислить нужно х и у.

Берешь уравнение kx + ly = m, и делишь его на нод(x, y).

[Feagor]

Берешь уравнение kx + ly = m, и делишь его на нод(x, y).

может не нод(x,y), а нод(k,l)?

[Michael_Rybak]

Ой Да, конечно.

[Feagor]

вот что получилось:

uses crt;
 procedure nod(a, b:longint; var d,x,y:longint);
 var q,r,x1,x2,y1,y2:longint;
 begin
   if b=0 then
        begin
          d:=a;
          x:=1;
          y:=0;
        end
   else
        begin
          x2:=1;x1:=0;y2:=0;y1:=1;
          while b>0 do
                begin
                  q:=a div b;
                  r:=a-q*b;
                  x:=x2-q*x1;
                  y:=y2-q*y1;
                  a:=b;b:=r;x2:=x1;x1:=x;y2:=y1;y1:=y;
                end;
        end;
   d:=a; x:=x2;y:=y2;
 end;
 var a,b,d,x,y,k,l,m:longint;
     xx,yy:real;
 begin
   clrscr;
   Writeln('Input f,g');
   Read(a,b);
   nod(a,b,d,x,y);
   writeln(d,'   ',x,'   ',y);
   writeln('Input k,l,m');
   read(k,l,m);
   nod(abs(k),abs(l),d,x,y);
   xx:=x*m/d;
   yy:=y*m/d;
   writeln(trunc(xx),'   ',trunc(yy));
   readkey;
 end.

Вроде работает, Michael_Rybak +1 за великое знание

Сообщение отредактировано: Feagor - 11.01.2008 14:29