полиндромы - Помощь студентам

Sparky · 21.10.2010, 09:46

Добрый день! Необходимо написать программу для вычисления НОД 2 многочленов. Синтаксический разбор многочленов сделала, но вот не могу написать алгоритм вычисления НОД, вот код:

Код:


type
  TPoly = record  //тип многочлен
    n:integer;  //степень
    a: array[0..255] of integer;  //коэффициенты
  end;

var
  pol_1,pol_2,result:TPoly;
  f_out,f_in:text;
  pos:integer;  //текушая позиция
  ch:char;  //текущий символ

procedure error(code:integer;position:integer);  //процедура печати ошибки в файл(код ошибки,позиция)
var
  res:string;
begin

  case code of
    0: res:='число начинается не с цифры';
    1: res:='степень больше заданной макс степени';
    2: res:='нет числа';
    3: res:='мусор';
  end;
  writeln(f_out,res,' ',position);
  close(f_in);
  close(f_out);
  Halt(0);
end;

procedure next(); //процедура считывания символа
begin
  inc(pos);
  if(not eoln(f_in)) then read(f_in,ch)  //если не конец строки считываем
  else  //иначе переводим коретку
  begin
    readln(f_in);
    ch:=chr(0);
  end;
end;

procedure del(var p:TPoly); //процедура сброса многочлена
var
  i:integer;
begin
  p.n:=0;
  for i:=0 to 255 do
    p.a[i]:=0;
end;

procedure number(var a:integer); //определение числа()
var
  str:string;
begin
  str:='';

  if(ch in ['0'..'9']) then
  begin
    str:=ch;  //накапливаем число
    next();  //если цифра считываем след
  end

  else error(0,pos);  //иначе ошибка число не с цифры
  while (ch in ['0'..'9']) do //ччитываем пока не дойдем до след
  begin
    str:=str+ch;  //накапливаем число
    next();
  end;

  a:=StrToInt(str); //записывем число
end;

procedure st(var p:integer);  //определение степени(степень)
begin
  if(ch='^')then  //если значек степени считываем число
  begin
    next();
    number(p);
    if p>255 then error(1,pos); //если степень больше выдаем ошибку
  end

  else p:=1; //иначе стпень равна 1
end;

procedure addent(var a,k:integer); //слагаемое(коэффициент и степень)
begin
  if(ch in ['0'..'9']) then //если цифра то считываем коэффициент
  begin
    number(a);  //формируем коэффициент

    if(ch='x') then //начинаем формирование степени
    begin
      next();
      st(k);  //формируем степень
    end
    else k:=0;  //степень ровна 0 если х нет
  end
  else if (ch='x') then //если сразу х то коэффициент 1 формируем степень
  begin
    a:=1;
    next();
    st(k);
  end
  else error(2,pos);  //ошибка числа нет
end;

procedure pol(var p:TPoly); //многочлен(многочлен)
var
  a:integer;  //коэффициент
  k:integer;  //степень
  znak:char;  //знак
begin
  del(p); //чистим многочлен

//==============================================================================
//    опредкляем знак
//==============================================================================
  if (ch in ['-','+']) then
  begin
    znak:=ch;
    next();
  end
  else znak:='+';

  addent(a,k);  //определяем слагаемо

//==============================================================================
//    приводим подобные
//==============================================================================
  if znak='+' then p.a[k]:=p.a[k]+a
  else p.a[k]:=p.a[k]-a;

  while(ch in ['+','-']) do
  begin
    znak:=ch;
    next();
    addent(a,k);

    if (znak='+')then  p.a[k]:=p.a[k]+a
    else p.a[k]:=p.a[k]-a;
  end;

//==============================================================================
//    опредкляем степень многочлена
//==============================================================================
  p.n:=255;
  while(p.n>0) and (p.a[p.n]=0) do
    p.n:=p.n-1;
end;

procedure input_poly(var p:TPoly);  //ввод многочлена(многочлен)
begin
  pos:=0; //начальная позиция 0
  next();
  pol(p);
  if ch<>chr(0) then  //если есть что-то лишнее ошибка
    error(3,pos);
end;

procedure output_poly(p:TPoly); //вывод многочлена(многочлен)
var
  i:integer;
begin
  for i:=p.n downto 0 do
  begin
    if ((p.a[i]>0) and (i<>p.n)) then write(f_out,'+')
    else if ((p.a[i]<0) and (i=p.n)) then write(f_out,'-')
    else if(p.a[i]<0) then write(f_out,'-');

    if (abs(p.a[i])>1) or (i=0) and (p.a[i]<>0) or (p.n=0) then write(f_out,abs(p.a[i]));

    if (i>0) and (p.a[i]<>0) then write(f_out,'x');
    if (i>1) and (p.a[i]<>0) then write(f_out,'^',i);
  end;
end;


begin
//==============================================================================
//    инициализация входных данных
//==============================================================================
  assign(f_in,'input.txt');
  reset(f_in);
  assign(f_out,'output.txt');
  rewrite(f_out);
  input_poly(pol_1);
  output_poly(pol_1);
  close(f_in);
  close(f_out);
end.

Sparky · 21.10.2010, 10:43

нужен алгоритм Евклида

Sparky · 21.10.2010, 19:50

может есть какие-нибудь идеи?

_-Re@l-_ · 21.10.2010, 19:54

Вот алгоритм Евклида:

Код:


function NOD(x,y:longint):longint;
 begin
  if x<>0 then NOD:= NOD(y mod x,x) else NOD:= y;
 end;

Недавно тема была.

Sparky · 21.10.2010, 20:13

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

Sparky · 01.12.2010, 20:18

Код:

program nod;

{$APPTYPE CONSOLE}

uses
  SysUtils;

//==============================================================================
//    описание типов данных и переменных
//==============================================================================
type
  TPoly = record
    n:integer;
    a: array[0..255] of real;
  end;

var
  pol_1,pol_2,nod_otvet:TPoly;
  f_out,f_in:text;
  pos:integer;
  ch:char;

//==============================================================================
//    процедуры и функции
//==============================================================================
procedure error(code:integer;position:integer); //процедура обработки ошибки(код ошибки, позиция)
var
  res:string;
begin
  case code of
    0: res:='число начинается не с цифры';
    1: res:='степень больше заданной макс степени';
    2: res:='нет числа';
    3: res:='мусор';
  end;
  writeln(f_out,res,' ',position);
  close(f_in);
  close(f_out);
  Halt(0);
end;


procedure next; //процедура считывания следующего символа
begin
  inc(pos);
  if(not eoln(f_in)) then read(f_in,ch)
  else
  begin
    readln(f_in);
    ch:=chr(0);
  end;
end;


procedure del(var p:TPoly); //инициализация многочлена
var
  i:integer;
begin
  p.n:=0;
  for i:=0 to 255 do
    p.a[i]:=0;
end;


procedure number(var a:integer);  //определение числа()
var
  cislo:integer;
begin
  cislo:=ord(ch)-48;
  if(ch in ['0'..'9']) then //если цифра считываем след
  begin
    next;
  end
  else error(0,pos);  //иначе ошшибка
  while (ch in ['0'..'9']) do //считываем пока не дойдем до след
  begin
    if((32767 div 10) > cislo) then //проверяем на переполнение
    begin
      cislo:=cislo*10+(ord(ch)-48);
      next;
    end
    else error(3,pos);
  end;
  a:=cislo;
end;


procedure st(var p:integer);  //определение степени(степень)
begin
  if(ch='^')then  //если значек степени считываем число-степень
  begin
    next;
    number(p);
    if p>255 then error(1,pos); //если степень больше 255 ошибка
  end
  else p:=1;  //иначе степень 1
end;


procedure addent(var a,k:integer); //слагаемое(коэффициент и степень)
begin
  if(ch in ['0'..'9']) then
    begin
    number(a);

    if(ch='x') then
        begin
      next;
      st(k);
    end
    else k:=0;
  end
  else if (ch='x') then
  begin
    a:=1;
    next;
    st(k);
  end
  else error(2,pos);
end;


procedure pol(var p:TPoly); //многочлен(многочлен)
var
  a:integer;
  k:integer;
  znak:char;
begin
  del(p);
//==============================================================================
//    опредкляем знак
//==============================================================================
  if (ch in ['-','+']) then
  begin
    znak:=ch;
    next;
  end
  else znak:='+';
  addent(a,k);
//==============================================================================
//    приводим подобные
//==============================================================================
  if znak='+' then p.a[k]:=p.a[k]+a
  else p.a[k]:=p.a[k]-a;

  while(ch in ['+','-']) do
  begin
    znak:=ch;
    next;
    addent(a,k);

    if (znak='+')then  p.a[k]:=p.a[k]+a
    else p.a[k]:=p.a[k]-a;
  end;
//==============================================================================
//    опредкляем степень многочлена
//==============================================================================
  p.n:=255;
  while(p.n>0) and (p.a[p.n]=0) do
    p.n:=p.n-1;
end;


procedure input_poly(var p:TPoly);  //процедура ввода многочлена(могочлен)
begin
  pos:=0;
  next;
  pol(p);
  if ch<>chr(0) then
    error(3,pos);
end;

procedure output_poly(p:TPoly); //процедура вывода многочлена(многочлен)
var
  i:integer;
begin
  for i:=p.n downto 0 do
  begin
    if ((p.a[i]>0) and (i<>p.n)) then write(f_out,'+')
    else if ((p.a[i]<0) and (i=p.n)) then write(f_out,'-')
    else if(p.a[i]<0) then write(f_out,'-');

    if (abs(p.a[i])>1) or (i=0) and (p.a[i]<>0) or (p.n=0)
       then
           write(f_out,abs(p.a[i]):0:4);

    if (i>0) and (p.a[i]<>0) then write(f_out,'x');
    if (i>1) and (p.a[i]<>0) then write(f_out,'^',i);
  end;
end;


procedure addition_poly(a,b:TPoly;var c:TPoly); //процедура сложения многочленов(многочлен)
var i,MaxStep:Integer;
begin
     if(a.n>b.n)
       then
         MaxStep:=a.n
       else
         MaxStep:=b.n;
     for i:=0 to MaxStep do
     begin
          c.a[i]:=a.a[i]+b.a[i];
     end;
     c.n:=MaxStep;
end;


procedure substraction_poly(a,b:TPoly;var c:TPoly); //процедура вычитания многочленов(многочлены)
var
  i,MaxStep:Integer;
begin
  if(a.n>b.n) then MaxStep:=a.n
  else
    MaxStep:=b.n;
  for i:=0 to MaxStep do
  begin
    c.a[i]:=a.a[i]-b.a[i];
  end;
  c.n:=255;
  while(c.n>0) and (c.a[c.n]=0)do
    c.n:=c.n-1;
end;

Sparky · 01.12.2010, 20:18

Код:

procedure multiplication_poly(a,b:TPoly;var c:TPoly); //процедура умножения многочленов(многочлены)
var
  i,j:Integer;
begin
  for i:=0 to a.n do
  begin
    for j:=0 to b.n do
    begin
      c.a[i+j]:=c.a[i+j]+a.a[i]*b.a[j];
    end;
  end;
  c.n:=a.n+b.n;
end;


procedure division_poly(a,b:TPoly;var c,d:TPoly); //процедура деления многочленов(многочлены)
var
  i:integer;
  tmp_mul,tmp_sub:TPoly;
begin
  d.n:=a.n;
  for i:=0 to a.n do
    d.a[i]:=a.a[i];
  if(d.n>=b.n)then
  begin
    c.n:=a.n-b.n;
    while(d.n>=b.n) and ((d.n<>0) or (d.a[0]<>0))do
    begin
      del(tmp_sub);
      del(tmp_mul);
      c.a[d.n-b.n]:=d.a[d.n]/b.a[b.n];
      tmp_mul.a[d.n-b.n]:=c.a[d.n-b.n];
      tmp_mul.n:=d.n-b.n;
      multiplication_poly(tmp_mul,b,tmp_sub);
      substraction_poly(d,tmp_sub,d);
    end;
  end;
end;

procedure nod_poly(a,b:Tpoly;Var c:Tpoly);  //процедура вычисления нода(многочлены)
var
  tmp:Tpoly;
begin
  while((a.n<>0) or ((a.n=0) and (a.a[0]<>0))) and ((b.n<>0) or ((b.n=0) and (b.a[0]<>0))) do
  begin
    if(a.n>=b.n) or (a.n=b.n) and (a.a[a.n]>=b.a[b.n]) then
    begin
      del(tmp);
      division_poly(a,b,tmp,a);
    end
    else
    begin
      del(tmp);
      division_poly(b,a,tmp,b);
    end;
  end;
  addition_poly(a,b,c);
end;

Sparky · 01.12.2010, 20:19

Код:

//==============================================================================
//    главная программа
//==============================================================================
begin
//==============================================================================
//    инициализация входных данных
//==============================================================================
  assign(f_in,'input.txt');
  reset(f_in);
  assign(f_out,'output.txt');
  rewrite(f_out);
  input_poly(pol_1);
  input_poly(pol_2);
  output_poly(pol_1);
  writeln(f_out);
  output_poly(pol_2);
  writeln(f_out);
//==============================================================================
//    основная работа
//==============================================================================
  nod_poly(pol_1,pol_2,nod_otvet);
  output_poly(nod_otvet);
  close(f_in);
  close(f_out);
end.

Sparky · 01.12.2010, 20:19

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

21.10.2010, 10:43	#2
Sparky Участник клуба Регистрация: 15.05.2009 Сообщений: 1,222	нужен алгоритм Евклида Единственное, что ограничивает полет мысли программиста-компилятор

21.10.2010, 19:50	#3
Sparky Участник клуба Регистрация: 15.05.2009 Сообщений: 1,222	может есть какие-нибудь идеи? Единственное, что ограничивает полет мысли программиста-компилятор

21.10.2010, 19:54	#4
_-Re@l-_ C++, Java Старожил Регистрация: 10.04.2010 Сообщений: 2,665	Вот алгоритм Евклида: Код: `function NOD(x,y:longint):longint; begin if x<>0 then NOD:= NOD(y mod x,x) else NOD:= y; end;` Недавно тема была.

21.10.2010, 20:13	#5
Sparky Участник клуба Регистрация: 15.05.2009 Сообщений: 1,222	для обычных чисел мне понятно, я не могу приделать его к многочленам Единственное, что ограничивает полет мысли программиста-компилятор

01.12.2010, 20:19	#9
Sparky Участник клуба Регистрация: 15.05.2009 Сообщений: 1,222	вот что у меня получилось, но правильно прога не работает. где ошибка и как ее исправить? Единственное, что ограничивает полет мысли программиста-компилятор

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Простые числа и полиндромы	VL@D1M1R	Помощь студентам	9	19.01.2010 14:42
счастливые числа и полиндромы помогите!!!	starlet	Помощь студентам	2	16.03.2009 09:23
Числа полиндромы	grerg	Помощь студентам	3	28.11.2007 18:15