Алгоритмы. Длинная арифметика 1

Автор: WargaL

И для начала информация (для тех, кто плохо учился в школе). В математике существует две простые аддитивные операции: сложение и вычитание. Сложность их реализации заключается в том, что складываться и вычитаться могут числа с разными знаками, т.е. модуль суммы, при сложении, может оказаться меньше модулей слагаемых, а модуль разности, при вычитании – больше (из-за разных знаков). Т.е. получается, что сумма a и (-b) будет равна разности: a+(-b)=a-b. Т.о. операцию сложения надо заменять операцией вычитания, вызывая другую функцию. А ведь вполне возможно, что b>a, и тогда для получения верного результата придется вычитать из b a, и результат умножать на -1. a-b=-(b-a). Так вот в этом и заключается сложность сложения/вычитания. Необходимо проанализировать выражение и вызвать нужную функцию. Для того чтобы избавиться от рекурсии, предлагаю вынести операции «правильного сложения» и «правильного вычитания» в отдельные функции. Под «правильным сложением», я понимаю сложение двух неотрицательных чисел, а под «правильным вычитанием» - разность двух неотрицательных чисел, причем уменьшаемое больше вычитаемого (т.е. результат тоже не отрицателен). А путем преобразований любую операцию можно свести к «правильной».

Еще хотелось бы отметить следующее: т.к. наши числа могут быть дробными, т.е. «с запятой», не будет лишним ввести процедуру, приводящую два числа к одному виду (одинаковое количество знаков до и после десятичной точки). И еще: т.к. эти числа будут выводиться на экран, то следовало бы сделать функцию, отсекающую ненужные знаки, уменьшая длину строки, приводя число к стандартному виду.

Ну-с, приступим! Для начала реализуем дополнительные процедуры и функции. Это будут нормализация и стандартизация чисел, а также сравнения. Нормализация – все просто: заполняем нулями недостающие знаки до и после десятичной точки.

Т.о. нормализованное число всегда выглядит так: знак/целая часть/,/дробная часть н.р.: +123,456

Procedure Normaliz(SourceStr1, SourceStr2:string; var ResStr1,ResStr2:string); var s1p,s2p:integer; // SourceStr1, SourceStr2 – исходные строки. // ResStr1,ResStr2 – переменные, в которые записывается результат. begin ResStr1:=(SourceStr1); ResStr2:=(SourceStr2); if (ResStr1[1]<>'+') and (ResStr1[1]<>'-') //если первый знак не «+» then ResStr1:='+'+ResStr1; //и не «-», то число положительное. if (ResStr2[1]<>'+') and (ResStr2[1]<>'-') //т.е. надо поставить «+». then ResStr2:='+'+ResStr2; s1p:=pos(DecPoint, ResStr1); //определяем позицию десятичной точки. s2p:=pos(DecPoint, ResStr2); if s1p=0 // s1p=0 только при отсутствии дес. точки в строке. При этом //надо эту точку добавить, а вместе с ней и 0. then begin ResStr1:=ResStr1+',0'; s1p:=pos(DecPoint, ResStr1) end; if s2p=0 then begin ResStr2:=ResStr2+',0'; s2p:=pos(DecPoint, ResStr2) end; if ResStr1=ResStr2 then exit; if s1p<>s2p //если количества цифр до запятой не равны, //то добавляем нули к той строке, где их не хватает then if s1p>s2p then insert(stringofchar('0',s1p-s2p),ResStr2,2) else insert(stringofchar('0',s2p-s1p),ResStr1,2); //вставляем строку с нулями, начиная со второго элемента, т.к. первый – знак числа. if length(ResStr1)<>length(ResStr2) //аналогично делаем с дробной частью. then if length(ResStr1)>length(ResStr2) then ResStr2:=ResStr2 + stringofchar('0',length(ResStr1)-length(ResStr2)) else ResStr1:=ResStr1 + stringofchar('0',length(ResStr2)-length(ResStr1)); end;

Забыл сказать, что DecPoint – это константа.

Const DecPoint = ',';

Это не стандартная дельфевская единица, поэтому ее придется объявить самим (так, как указано выше) Где объявить?...присоединяйтесь к нам позже, когда найдете ответ на этот вопрос (скажу только одно: она нам понадобится во многих процедурах и функциях).

Теперь, когда ламеры нас покинули , мы можем продолжить... И следующая на очереди функция – стандартизация. Она нужна для отсечения ненужных знаков и символов от числа. Т.е. строку «+0067300,2300» она преобразует в строку «67300,23», а строку «-00235,000» в «-235», т.е. приводит к стандартному виду, которым мы привыкли пользоваться в повседневной жизни. Резонный вопрос: откуда могут взяться такие числа? Отвечаю. В процессе нормализации мы постоянно добавляем «лишние» знаки, да и при вычислениях может статься, что они появятся (из-за того, что длина строки не меняется). Теперь когда необходимость появления этой функции я обосновал, приступим к ее написанию. Поехали...

Function Standartiz(SourceStr:string):string; var s1p,i1,i2:integer; s1:string; begin s1:=SourceStr; if (s1[1]='+') or (s1[1]='-') //если в качестве первого знака стоит then i1:=2 //«+» или «-» то перебор начинаем с 2 else i1:=1; //иначе с 1 s1p:=pos(DecPoint,s1)-1; //определяем конец перебора (до DecPoint) if s1p=0 then s1p:=length(s1); //если нет DecPoint, то до конца строки. i2:=i1; while (s1p>i2) and (s1[i2]='0') do //определяем, сколько нулей i2:=i2+1; //надо удалить. delete(s1,i1,i2-i1); //собственно удаление нулей. s1p:=pos(DecPoint,s1); //аналогично делаем с дробной частью. if s1p=0 then s1p:=length(s1); i1:=length(s1); i2:=i1; while (i2>s1p) and (s1[i2]='0') do i2:=i2-1; delete(s1,i2+1,i1-i2); if s1[1]='+' then delete(s1,1,1); //если первый символ «+», то удалить его. i1:=length(s1); if s1[i1]=decpoint then delete(s1,i1,1); //если последний символ – DecPoint, удалить его. result:=s1 end;

Ну, и напоследок - проверка. Вернее не проверка, а сравнение двух строк. Сразу скажу, эта функция будет применяться только к нормализованным числам. Поэтому: во-первых, должна использоваться только вместе с Normaliz; во-вторых, будет считаться, что первый символ в числе – знак, и десятичная точка присутствует (не в самом конце строки). Кроме того, сравнение будет происходить без учета знака, т.е. сравниваем модули чисел (нам необходимо именно такое сравнение).

Интерпретация результата: если значение функции положительно, то первое число больше, иначе больше второе. 0 – числа равны. Модуль же числа показывает на каком знаке (порядке) проявляется отличие. Ну, сейчас все станет понятно.

function STRCheck(Str1, Str2:string):integer; var i,r:integer; st1,st2:string; begin St1:=Str1; St2:=Str2; r:=0; i:=2; //инициализация while (i<=length(st1)) and (r=0) do //прогулка по строке в поисках разницы. begin if st1[i]<>st2[i] then if st1[i]>st2[i] then r:=i else r:=(-1)*i; i:=i+1 end; STRCheck:=r end;

Все. С промежуточными функциями и процедурами покончили. Приступаем к реализации функции «правильного сложения». Алгоритм сложения прост. Он такой же, как в статье «двоичный код 2», разница лишь в том, что у нас теперь дробное число, т.е. в строке присутствует символ DecPoint. Предлагаю сделать следующее: сложить отдельно дробную часть и отдельно целую. Но можно попробовать другой вариант: избавиться от DecPoint в строке и просто сложить число, затем вернуть DecPoint на место (количество десятичных знаков при сложении не меняется). Но тут подвох, определять позицию DecPoint надо не от начала строки (как это делает функция), а с хвоста. Это необходимо для исключения ошибки, когда при увеличении разряда (н.р. 10,2 + 92,3=102,5) DecPoint сместиться на один знак относительно начала строки. Определить позицию можно, например так:

PosDecPoint := Length(str) – pos(DecPoint, str);

Если хотите, можете попробовать реализовать данный способ сами, а я буду использовать вариант №1. Поехали.

Function Sum(SourceStr1, SourceStr2: string ):string; var i,j,k,m:integer; res,str1,str2:string; ch1,ch2:char; begin Str1:=SourceStr1; Str2:=SourceStr2; res:=''; m:=0; k:=0; j:=pos(DecPoint,str1)+1; for i:=length(str1) downto j do begin ch1:=str1[i]; ch2:=str2[i]; try k:=(StrToInt(ch1)+StrToInt(ch2)+m) mod 10; m:=(StrToInt(ch1)+StrToInt(ch2)+m) div 10; except on EConvertError do exit end; res:=IntToStr(k)+res end; res:=DecPoint+res; for i:=j-2 downto 2 do begin ch1:=str1[i]; ch2:=str2[i]; try k:=(StrToInt(ch1)+StrToInt(ch2)+m) mod 10; m:=(StrToInt(ch1)+StrToInt(ch2)+m) div 10; except on EConvertError do exit end; res:=IntToStr(k)+res end; if m<>0 then res:=IntToStr(m)+res; result:=res end;

Думаю, ничего сложного. Если нужны комментарии, смотри статью «двоичный код 2». Единственное различие: суммирование здесь происходит в 2 этапа. Сначала дробная часть (...for i:=length(str1) downto j do...), затем целая (...for i:=j-2 downto 2 do...).

Теперь очередь «правильного вычитания». Все аналогично. Сначала вычитаем дробную часть, затем целую. Отличие появляется только тогда, когда надо «занимать» 10 из последующего разряда. Для этого мы опять используем переменную m. В общем, все одинаково.

Function sub(SourceStr1, SourceStr2: string ):string; var i,j,k,m:integer; res,str1,str2:string; ch1,ch2:char; begin Str1:=SourceStr1; Str2:=SourceStr2; res:=''; m:=0; k:=0; j:=pos(DecPoint,str1)+1; for i:=length(str1) downto j do //дробная часть. begin ch1:=str1[i]; ch2:=str2[i]; try if (StrToInt(ch1)-StrToInt(ch2)-m)>=0 //проверка: надо ли брать взаймы then begin k:=(StrToInt(ch1)-StrToInt(ch2)-m); m:=0 end else begin k:=(10+StrToInt(ch1)-StrToInt(ch2)-m); m:=1 end; except on EConvertError do exit end; res:=IntToStr(k)+res end; res:=DecPoint+res; for i:=j-2 downto 2 do //целая часть. Аналогично. begin ch1:=str1[i]; ch2:=str2[i]; try if (StrToInt(ch1)-StrToInt(ch2)-m)>=0 then begin k:=(StrToInt(ch1)-StrToInt(ch2)-m); m:=0 end else begin k:=(10+StrToInt(ch1)-StrToInt(ch2)-m); m:=1 end; except on EConvertError do exit end; res:=IntToStr(k)+res end; if m<>0 then res:=''; result:=res end; //КОНЕЦ!!! Осторожней, мало ли что у него на уме! //Получается, что у конца есть ум!...хм, надо с ним поосторожней! (прим. Автора)

Ура! Осталась ссущая мелочь . Нам надо написать процедуру, которая будет управлять процессом сложения/вычитания. По комбинаторике (раздел математики изучающий различные комбинации элементов) получается, что возможны 8 различных вариантов сумм и 8 вариантов разности (я не беру во внимание варианты когда модули операндов равны). Нам надо предусмотреть их все.

a > b > 0, a + b = s, a - b = r Для суммы: Для разности: a + b = s a - b = r -a + b = -r -a - b = -s a +(-b) = r a -(-b) = s -a +(-b) = -s -a -(-b) = -r b + a = s b - a = -r -b + a = r -b - a = -s b +(-a) = -r b -(-a) = s -b +(-a) = -s -b -(-a) = r

Как видно, модуль результата может быть либо «правильной суммой», либо «правильной разностью». Теперь наша задача сводится к тому, чтобы определить, какой из вариантов нам попался, и, посчитав сумму или разность, дополнить ее нужным знаком. Этим и займемся.

Function SumSTR(Str1, Str2:string):string; var s1,s2:string; i:integer; begin Normaliz(Str1,Str2,s1,s2); //присутствует нормализация, //значит, можно складывать любые строки! i:=STRCheck(s1,s2); //сравнение строк и запись результата в переменную i. //проверка разных вариантов. if (i = 0) and (s1[1] <> s2[1]) then begin Result:='0'; exit end; if (s1[1] = s2[1]) then begin Result:=s1[1]+sum(s1,s2); exit end; if (i >= 0) and (s1[1] < s2[1]) then begin Result:=s1[1]+sub(s1,s2); exit end; if (i >= 0) and (s1[1] > s2[1]) then begin Result:=s1[1]+sub(s1,s2); exit end; if (i < 0) and (s1[1] < s2[1]) then begin Result:=s2[1]+sub(s2,s1); exit end; if (i < 0) and (s1[1] > s2[1]) then begin Result:=s2[1]+sub(s2,s1); exit end; end; //...

Абсолютно аналогичным способом делаем разность. Я даже комментировать не буду.

Function SubSTR(Str1, Str2:string):string; var s1,s2:string; i:integer; begin Normaliz(Str1,Str2,s1,s2); i:=STRCheck(s1,s2); if (i = 0) and (s1[1] = s2[1]) then begin Result:='0'; exit end; if (s1[1] <> s2[1]) then begin Result:=s1[1]+sum(s1,s2); exit end; if (i >= 0) then begin Result:=s1[1]+sub(s1,s2); exit end; if (i < 0) then if (s2[1]='+') then begin Result:='-'+sub(s2,s1); exit end else begin Result:='+'+sub(s2,s1); exit end end;

Осталось только собрать все то, что мы сделали и запихнуть в юнит. Кстати, настоятельно рекомендую создать новый проект. На этот проект надо закинуть 13 батонов, 2 эдита и 2 лабела. Этот проект будет постепенно заполняться функциями. Две из которых мы уже написали (+ и -). Остальные будем дописывать в следующих статьях (на очереди * и /).

Итак, надо проверить наш код. Для того, чтобы не было разногласий в проектах операции, + и – надо поставить на батон3 и батон4 соответственно. Почему? Батон1 и батон2 у меня заняты другим делом. Позже и до них дойдем. А пока надо сделать так.

procedure TForm1.Button3Click(Sender: TObject); begin label1.Caption:=SumSTR(edit1.Text,edit2.Text) end; procedure TForm1.Button4Click(Sender: TObject); begin label1.Caption:=SubSTR(edit1.Text,edit2.Text) end;

P.S.:На выводимое число можно натравить функцию Standartiz. Так будет еще красивей. Забегая далеко вперед, скажу, после написания всех функций мы займемся оптимизацией кода. Переделаем все. Спросите, зачем тогда пишем этот? Отвечаю: в образовательных целях. С неоптимизированным кодом разобраться на порядок проще, поэтому сначала так.