Форум «Всё о Паскале» > Длинная арифметика

Помощь - Поиск - Пользователи - Календарь

Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи

Reflex

11.10.2006 0:56

Не могли бы ли вы мне помочь (факю читал не то что нужно). Мне нужно : реализация длинной арифметики на массиве цифр этого числа, нужно превеод интеджера в длинную арифметику, остаток от деления и вывод этого числа.
например Inttolong(a:integer):integer;
modlong(num1,num2:long):long;
write(long);
Спасибо большое, если поможите.

P.S. Пишу не своего компьютера

volvo

11.10.2006 1:05

Ну, раз то, что ты читал - не то, что нужно, то Google - твой помощник... Ищи...

Гость

11.10.2006 1:09

искал...
но не нашел, а реализовать не получается

Гость

11.10.2006 1:15

помогите, в четверг сдавать

Michael_Rybak

11.10.2006 1:43

Вот, пока не перешел на с++, пользовал такую свою заготовку для олимпиад.
На изящность, а тем более, на оптимальность код не претендует.

Тут есть InToTNum, +, -, *, /, PrintLong

Остаток от деления вырази как a-(a div b)*b

Код (Показать/Скрыть)

Unit LongMath;
Interface
Const MaxLen=255;
Type TNum=Array[0..MaxLen] Of Byte;
Var mt,dt:Array[0..100] Of Byte;
    iii:Longint;
Procedure Add(A,B:TNum;Var C:TNum);             {Сложение}
Procedure Sub(A,B:TNum;Var C:TNum);
Procedure Mul10(Pow:Longint;Var X:TNum);           {Умножение на 10 в степени}
Procedure Mulm10(Pow:Longint;Var X:TNum);
Procedure Mul(A,B:TNum;Var C:TNum);             {Умножение}
Procedure MulC(A:TNum;C:Longint;Var B:TNum);       {Умножение числа на цифру}
Function InputLong(Var X:TNum):Boolean;                {Ввод}
Procedure PrintLong(Var X:TNum);                {Вывод}
Function Len(X:TNum):Longint;                   {Определение длины}
Function CmpEqLns(A,B:TNum):Char;               {Сравненме чисел одной длины}
Function Cmp(A,B:TNum):Char;                    {Сравнение чисел}
Procedure Dvd(A,B:TNum;Var C:TNum);
Procedure InToTNum(K:Longint;Var R:TNum);
Procedure StToTNum(S:String;Var R:TNum);
Implementation
 Function Max(X,Y:Longint):Longint;
 Begin
  If X>Y Then Max:=X Else Max:=Y;
 End;
 Procedure Add;
  Var I,D                     :Longint;
 Begin
  InToTNum(0,C);
  D:=0;
  For I:=MaxLen DownTo MaxLen-Max(Len(A),Len(B)) Do Begin
   C[I]:=(A[I]+B[I]+D) Mod 10;
   D:=(A[I]+B[I]+D) Div 10;
  End;
  C[0]:=Max(Len(A),Len(B))+1;
  If C[MaxLen-Max(Len(A),Len(B))]=0 Then
   Dec(C[0]);
 End;
 Procedure Mul10;
  Var I:Longint;
 Begin
  For I:=1 To MaxLen-Pow Do
   X[I]:=X[I+Pow];
  For I:=MaxLen+1-Pow To MaxLen Do
   X[I]:=0;
  Inc(X[0],Pow);
 End;
 Procedure Mulm10;
  Var I:Longint;
 Begin
  For I:=MaxLen DownTo Pow+1 Do
   X[I]:=X[I-Pow];
  For I:=1 To Pow Do
   X[I]:=0;
  Dec(X[0],Pow);
  If X[0]<0 Then
   X[0]:=0;
 End;
 Procedure Mul;
  Var I,J,D,V,LA,LB,P                :Integer;
      T                      :TNum;
 Begin
  FillChar(c,SizeOf( c ),0);
  LA:=Len(a); LB:=Len(b);
  For i:=LB DownTo 1 Do Begin
   d:=0;
   For j:=LA DownTo 0 Do Begin
    P:=MaxLen-LA+j+i-LB;
    V:=a[MaxLen-LA+j]*b[MaxLen-LB+i]+d+c[P];
    c[P]:=mt[V];
    d:=dt[v];
   End;
  End;
 End;
 Procedure MulC;
  Var i,j,d:Longint;
      t:TNum;
 Begin
  For I:=1 To MaxLen Do B[I]:=0;
  For J:=1 To MaxLen Do T[J]:=0;
  D:=0;
  For J:=MaxLen DownTo MaxLen-Len(A) Do Begin
   T[J]:=(A[J]*C+D) Mod 10;
   D:=(A[J]*C+D) Div 10;
  End;
  T[0]:=Len(A)+1;
  Add(T,B,B);
 End;
 Function InputLong;
  Var I                      :Longint;
      S                      :String;
      Cod                    :Integer;
 Begin
  Readln(S);
  If s='-1' Then Begin
   InputLong:=False;
   Exit;
  End;
  InputLong:=True;
  FillChar(X,SizeOf(X),0);
  For I:=1 To Length(S) Do Val(S[I],X[MaxLen-Length(S)+I],Cod);
  X[0]:=Length(s);
 End;
 Procedure PrintLong;
  Var I                      :Longint;
 Begin
  If Len(X)=0 Then
   Write(0)
  Else
   For I:=MaxLen+1-Len(X) To MaxLen Do
    Write(X[I]);
 End;
 Function Len;
  Var I                      :Longint;
 Begin
  Len:=0;
  I:=2;
  While ((X[I]=0) And (I<=MaxLen)) Do Inc(I);
  Len:=MaxLen+1-I;
 End;
 Function CmpEqLns;
  Var I                      :Longint;
      R                      :Char;
 Begin
  R:='=';
  I:=1;
  While ((I<=MaxLen) And (R='=')) Do Begin
   If A[I]>B[I] Then
    R:='>'
   Else If A[I]<B[I] Then
    R:='<';
   Inc(I);
  End;
  CmpEqLns:=R;
 End;
 Function Cmp;
 Begin
  If Len(A)>Len(B) Then Cmp:='>' Else
   If Len(A)<Len(B) Then Cmp:='<' Else
    Cmp:=CmpEqLns(A,B);
 End;
 Procedure Sub;
  Var I,D                    :Longint;
 Begin
  InToTNum(0,C);
    Begin
     D:=0;
     For I:=MaxLen DownTo MaxLen-Max(Len(A),Len(B)) Do Begin
      C[I]:=(A[I]-B[I]+10-D) Mod 10;
      If (A[I]-B[I]-D)<0 Then
       D:=1
      Else
       D:=0;
     End;
     C[0]:=Max(Len(A),Len(B));
    End;{If}
 End;
 Procedure InToTNum;
  Var i:Longint;
      cod:Integer;
      s:String;
 Begin
  if k<0 then begin
   R[0]:=1;
   K:=-K;
  end;
  str(k,s);
  for i:=0 to MaxLen do R[i]:=0;
  for i:=1 to length(s) do
   val(s[i],R[MaxLen-length(s)+i],Cod);
  R[0]:=Length(s);
 End;
 Procedure StToTNum;
  Var cod:Integer;
      i:Longint;
 Begin
  if s[1]='-' then begin
   R[0]:=1;
   Delete(s,1,1);
  end;
  for i:=1 to MaxLen do R[i]:=0;
  for i:=1 to length(s) do
   val(s[i],R[MaxLen-length(s)+i],Cod);
 End;
 Procedure Dvd;
  Var i,j,k:Longint;
      r,t,n,v:TNum;
 Begin
  k:=MaxLen+1-len(A);
  InToTNum(a[k],n);
  InToTNum(0,r);
  InToTNum(0,v);
  while k<=MaxLen do begin
   i:=10;
   repeat
    dec(i);
    MulC(b,i,t)
   until cmp(t,n)<>'>';
   mul10(1,r);
   v[MaxLen]:=i;
   add(r,v,r);
   sub(n,t,n);
   mul10(1,n);
   inc(k);
   if k<=MaxLen then begin
    v[MaxLen]:=a[k];
   add(n,v,n);
   end;
  end;
  c:=r;
 End;
Begin
 For iii:=0 To 100 Do Begin
  mt[iii]:=iii Mod 10;
  dt[iii]:=iii Div 10;
 End;
End.

Пример использования:

Program Long;
 Uses LongMath;
 Var A,B,C                   :TNum;
Begin
 InputLong(A);
 InputLong(B);
 Dvd(A,B,C);
 Writeln('A:',Len(A));
 Writeln('B:',Len(B));
 PrintLong( C );
 Readln;
End.

P.S. На алголисте есть, но на сях.

Гость

11.10.2006 1:48

Спасибо

помогли

Гость

11.10.2006 22:00

я понимаю, что выгляжу полным нубом, но подскажите как мне найти НОК (наименьшее общее кратное) двух длинных чисел.

volvo

11.10.2006 22:02

Точно так же, как и для обычных (по той же формуле, только используя процедуры/функции для работы с длинными числами)...

Как для обычных чисел это делается, знаешь?

Гость

11.10.2006 22:52

Цитата

Как для обычных чисел это делается, знаешь?

нет

Гость

11.10.2006 23:01

а почему поиск на НОК не сработал?

Reflex

11.10.2006 23:17

Я зарегестрировалась (извините за флуд)
Надеюсь, что вы не среагруете на мой пол так же, как и на некоторх других форумах

Reflex

11.10.2006 23:30

Volvo...
А Вы не могли бы мне подсказать как находить НОК для обычных чисел?

Michael_Rybak

12.10.2006 0:02

НОК(a, b) = a*b/НОД(a, b)

НОД ищите алгоритмом эвклида

Reflex

12.10.2006 0:25

извините, но я изучаю паскаль всего месяц и никак не могу понять как мне это сделать ( а завтра будет плохо если не принесу) вот то что дал Michael_Rybak мне подходит, я там все знаю, а вот в факю там много что непонятно

и реализовать нахождение НОКа не получается

Помогите умоляю.

Reflex

12.10.2006 1:13

:'( Неужели Volvo узнав что я девушка, передумал мне помочь :'( Почему люди на большинстве форумов отказываються помогать девушкам :'(

volvo

12.10.2006 1:28

Reflex, я еще не успел просто

Смотри... Вот так вычисляется НОК (по-английски LCM: Least Common Multiplier) для обычных чисел типа Integer (для проверки - запусти эту программу и посмотри, что она выдает):

{ GCD - это Greatest Common Divider = НОД }
function GCD (A: integer;  B: integer): integer;
begin
    while (a <> 0) and (b <> 0) do
       if a >= b then
         a := a mod b
       else
         b := b mod a;
    GCD := a + b;
end;

function LCM (A: integer;  B: integer): integer;
begin
     LCM := a * b div GCD (a, b)
end;

begin
  A := 12;
  B := 23;
  R := LCM(A, B);
  writeln('НОК = ', R);
end.

Совершенно аналогично вычислим его для длинных чисел, заменив все операции на процедуры:

uses longmath;

procedure GCD (A: TNum;  B: TNum; var res: TNum);
var
  Zero, DRes, MRes, T: TNum;
begin
  InToTNum(0, Zero);
  while (Cmp(a, Zero) = '>') and (Cmp(b, Zero) = '>') do
       if Cmp(a, b) in ['>', '='] then begin

         Dvd(a, b, DRes);
         Mul(DRes, b, MRes);
         Sub(A, MRes, T);
         A := T;

       end
       else begin

         Dvd(b, a, DRes);
         Mul(DRes, a, MRes);
         Sub(b, MRes, T);
         B := T;

       end;

  Add(a, b, res);
end;

function LCM (A: TNum;  B: TNum; var res: TNum);
var T, MRes: TNum;
begin
     Mul(a, b, MRes);
     GCD(a, b, T);
     Dvd(MRes, T, res);
end;

var
  A, B, R: TNum;
begin
  InputLong(A); { для проверки введи 12}
  InputLong(B); { здесь - для проверки - 23 }
  LCM(A, B, R);
  Write('NOD = ');
  PrintLong( r ); { ... и сравни результат... }
end.

Цитата

Неужели Volvo узнав что я девушка, передумал мне помочь

С чего ты взяла?

Не было этого никогда, чтоб я из-за пола человека отказывался ему помогать...

Reflex

12.10.2006 1:42

Спасибо, сейчас попробую
Просто когда я изучала HTML на одном форуме один парень объяснял, помогал мне, а потом я написала глагол в прошедшем времени(случайно так получилось что до этого были безродные ) он спросил: "Так ты девушка?" ну я скрывать и не собиралась , я ему честно ответила, а он меня тогда послал

Reflex

13.10.2006 22:17

сдала, но преподаватель сказал юниты - хорошо, но лучше все засунуть в один файл как это сделать вроде удталяю превую часть оне начинает ругаться

Michael_Rybak

14.10.2006 3:17

Возьми модуль, удали в нем строки "Unit LongMath;", "Interface" и "Implementation", а после каждого объявления процедуры/функции, находившегося *до* слова Implementation, допиши после точки с запятой: "forward;". Например:

Procedure Add(A,B:TNum;Var C:TNum); {Сложение} forward;
Procedure Sub(A,B:TNum;Var C:TNum); forward;
...

Это называется "предварительное объявление", т.е. ты говоришь компилятору, что такая функция с такими параметрами есть, а как она работает - будет сказано ниже. Таким приемом можно реализовать, например, вложенную рекурсию - когда А вызывает В, а В вызывает А.

А код программы вставь непосредственно перед "end.":

...
Procedure Dvd;
...
begin
...
End;
{здесь вставь объявление своих переменных}
Begin
For iii:=0 To 100 Do Begin
mt[iii]:=iii Mod 10;
dt[iii]:=iii Div 10;
End;
{здесь вставь свой код}
End.

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.