|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Eugeny Malkov 2:5002/62.13 20 Sep 2001 08:10:49
To : Denis Petrushenko
Subject : Деление 50-ти значных чисел
--------------------------------------------------------------------------------
Здравствуй, братец Denis ! Давно не виделись.
Чет 20/09/2001, Aleksey Malov писал письмо для Denis Petrushenko:
DP>> Даны два 50-ти значных(или менее значных числа).Известно, что одно
DP>> является делителем другого. Hеобходимо разделить их не используя
DP>> оператора деления. Результат - целое число(максимум
DP>> пятидесятизначное). Вычисление любого результата за 15 или менее
DP>> секунд(обязательно).
DP>> Может у кого-нибудь есть идеи?(желательно поподробнее)
AM> Переводишь их (делимое и делитель) в двоичный вид (займет около 160
AM> бит).
А зачем извращаться-то - времени 15 секунд. За это время в столбик в ACSII
кодах можно навскидку на 286 посчитать сотни тысяч знаков.
....
Вот недавно писал кому-то лабу: на самом деле ограничение на строки по-моему
128 знаков из-за особенностей ввода паскалевских строк, хотя это легко
преодолимо (да и не требуется в конкретной задаче)
uses crt;
var
d1:string; { Делимое }
d2:string; { Делитель }
result:string; { Частное }
ost:string; { Остаток }
{ Убирает первые незначащие цифры в числе }
function GetNormal(a:string):string;
var i,first,len:byte;
r:string;
begin
first:=0;
repeat
inc(first);
until ((a[first]>'0') and (a[first]<='9')) or (first=length(a));
r:='';
len:=length(a);
for i:=first to len do r:=r+a[i];
getnormal:=r;
end;
{ Возвращает true, если a<b }
{ a,b - нормализованы }
function less(a,b:string):boolean;
var
len1,len2,
i:byte;
fl:boolean;
begin
len1:=length(a);
len2:=length(b);
if len1>len2 then
less:=False
else
if len1<len2 then
less:=True
else
begin
fl:=false;
i:=1;
while (not fl) and (i<=len1) do
begin
if a[i]<b[i] then
fl:=true
else
if a[i]>b[i] then
begin
fl:=false;
i:=len1+1;
end
else { a[i]=b[i] }
i:=i+1;
end;
less:=fl;
end
end;
{ возвращает разность a-b, при условии, что a>=b }
function minus(a,b:string):string;
var
len1,len2,
i:byte;
flcarry:byte;
r:string;
c1,c2,r1:shortint;
begin
len1:=length(a);
len2:=length(b);
flcarry:=0;
r:='';
for i:=0 to len1-1 do
begin
c1:=ord(a[len1-i])-ord('0')-flcarry;
if i<len2 then
c2:=ord(b[len2-i])-ord('0')
else
c2:=0;
r1:=c1-c2;
if r1<0 then
begin
r1:=r1+10;
flcarry:=1;
end
else
flcarry:=0;
r:=chr(ord('0')+r1)+r;
end;
minus:=getnormal(r);
end;
{ Выполняет целочисленное деление d1 на d2 с остатком}
{ result - Частное, ost - Остаток }
procedure DivLong(d1,d2:string);
var s1:string; { текущий остаток }
len1, { длина делимого }
i, { счетчик цифр }
c: byte; { текущая цифра частного }
fl0: boolean; { флаг добавления в результат 0 при сносе }
begin
len1:=length(d1);
s1:='';
i:=1;
result:='0';
while i<=len1 do { проходим все цифры числа }
begin
fl0:=false; { флаг добавления в результат 0 при сносе }
{ добавляем цифры из делимого в остаток, пока он меньше делителя
или пока не кончится делимое}
while less(s1,d2) and (i<=len1) do
begin
s1:=s1+d1[i];
inc(i);
if fl0 then result:=result+'0'; { если снесли более одной цифры,
добавляем 0 в частное }
fl0:=true;
s1:=getnormal(s1); { удаляем первые нули из s1 (для сравнения) }
end;
if less(s1,d2) then { делимое кончилось }
begin
if fl0 then result:=result+'0';
ost:=s1;
end
else { считаем очередную цифру путем вычитания делителя из остатка }
begin
c:=0;
while not less(s1,d2) do { s1>=d2 }
begin
s1:=minus(s1,d2);
inc(c);
end;
result:=result+chr(ord('0')+c);
s1:=getnormal(s1);
end;
end;
ost:=s1;
end;
begin
clrscr;
Writeln('Эта программа выполняет целочисленное деление с остатком');
Writeln('десятичных чисел произвольной длины (до 255 знаков).');
writeln;
Writeln('Введите делимое:');
readln(d1);
d1:=getnormal(d1);
writeln;
Writeln('Введите делитель:');
readln(d2);
d2:=getnormal(d2);
DivLong(d1,d2);
result:=getnormal(result);
writeln;
writeln('Частное равно: ');
writeln(result);
writeln;
writeln('Остаток равен: ');
writeln(ost);
writeln;
writeln('Hажмите клавишу для выхода');
repeat until keypressed;
end.
Чет 20/09/2001, 09:10 С любовью, Буратино.
--- GoldED+/W32 1.1.4.3
* Origin: It's a simplest life. (2:5002/62.13)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Деление 50-ти значных чисел 