Program Delenie;
Uses
Crt;
Const
Max=1000;
Type
Mas=Array[1..Max] Of ShortInt;
Var
S:Boolean;
M1,M2:String;
A1,A2,Mm1,Mm2,P:Mas;
Cod:Integer;
f,k,l,i,j,z,C,q:Integer;
M,N1,N2:Integer;
Function Sravn(M:Integer;A1,Mm2:Mas):Boolean;
Var
k:Integer;
Begin
If M>N2 Then Sravn:=True;
If M<N2 Then Sravn:=False;
If M=N2 Then
For k:=1 To M Do
Begin
If A1[k]<Mm2[k]
Then
Begin
k:=M;
Sravn:=False;
End;
If A1[k]>Mm2[k]
Then
Begin
Sravn:=True;
k:=M;
End;
If A1[k]=Mm2[k] Then Sravn:=True;
End;
End;
Begin
ClrScr;
WriteLn(' Vvedite delimoe');
Write(' -> ');
ReadLn(M1);
N1:=LengTh(M1);
For i:=1 To N1 Do Val(M1,Mm1,Cod);
WriteLn(' Vvedite delitel');
Write(' -> ');
ReadLn(M2);
N2:=LengTh(M2);
For i:=1 To N2 Do Val(M2,Mm2,Cod);
For i:=1 To N2-1 Do A1:=Mm1;
M:=N2-1;
i:=M;
While(i<N1)Do
Begin
for q:=1 to M do write(A1[q]);write(' ');
While ((Sravn(M,A1,Mm2)=False) And (i<N1)) Do
Begin
M:=M+1;
i:=i+1;
A1[M]:=Mm1;
for q:= 1 to M do write(A1[q]);write(' ');
End;
j:=0;
While(Sravn(M,A1,Mm2)=True)Do
Begin
f:=N2+1;
For k:=M DownTo M-N2 Do
Begin
f:=f-1;
If A1[k]>=Mm2[f]
Then
A2[k]:=A1[k]-Mm2[f]
Else
Begin
A1[k]:=A1[k]+10;
A1[k-1]:=A1[k-1]-1;
For l:=k DownTo 1 Do
If A1[l]<0 Then
Begin
A1[l-1]:=A1[l-1]-1;
A1[l]:=A1[l]+10;
End;
A2[k]:=A1[k]-Mm2[f];
End;
End;
For l:=M-N2-1 DownTo 1 Do A2[l]:=A1[l];
j:=j+1;
P[i-N2+1]:=j;
While((A2[1]=0)And(M>0))Do
Begin
For z:=1 To M-1 Do A2[z]:=A2[z+1];
M:=M-1;
A2[M+1]:=0;
End;
For z:=1 To M Do A1[z]:=A2[z];
End;
While((A1[1]=0)And(M>0))Do
Begin
For z:=1 To M-1 Do A1[z]:=A1[z+1];
M:=M-1;
A1[M+1]:=0;
End;
End;
WriteLn(' Chastnoe: ');
Write(' -> ');
j:=1;
While ((P[j]=0)And(j>=N1-N2)) Do j:=j+1;
For i:=j To N1-N2+1 Do Write(P);
WriteLn;
If M=0 Then
Begin
M:=1;
A1[M]:=0;
End;
WriteLn(' Ostatok');
Write(' -> ');
For i:=1 To M Do Write(A1);
ReadLn;
End.
Деление больших чисел. Пмогите найти ошибку!
Ребят, прога как-то странно себя ведёт. Помгите найти ошибку. Программа основывается на последовательном вычитании. Некоторые числа делит нормально, например 124/4 или 98765432199/123456789, а вот если ввести 12345678900987654321/918273645, то выдает абракадабру :(
пожалуйста отформатируй текст отступами и самое главное напиши подробно коментарии, что бы легче было понять твою идею и цели
Переписываем условие вот так:
var sum: integer;
...
While ((Sravn(M,A1,Mm2)=False) And (i<N1)) Do
Begin
sum := 0;
for q := 1 to M do begin
sum := sum + a1[q]; if sum <> 0 then break;
end;
if ((M > 0) and (sum <> 0)) or (M = 0) then M:=M+1; { <--- }
i:=i+1;
A1[M]:=Mm1;
for q:= 1 to M do write(A1[q]);write(' ');
End;
как убрать в ответе лишний ноль в начале?
WriteLn(' Chastnoe: ');
Write(' -> ');
j:=1;
While ((P[j]=0)And(j>=N1-N2)) Do j:=j+1;
while p[j]=0 do inc(j); { <--- Вот так }
For i:=j To N1-N2+1 Do Write(P);
WriteLn;
Чисто ради интереса - условие задачи предпологает, что искомые числа должны разделиться нацело?
Программа выдает целочисленное частное и целочисленный остаток
http://task00.by.ru/task417_index.htm
там есть что-то для работы с большими числами (с числами в символьном представлении). В ответах найдете целую библиотеку.
там есть что-то для работы с большими числами (с числами в символьном представлении). В ответах найдете целую библиотеку.
PS Если хочешь, могу выложить исходник деления "столбиком"
Деление в "столбик" тоже особенной быстротой не отличается. Всё таки грамотный выход - вычитание. Пусть a/b=c (rem d). Число c показывает, сколько раз нужно вычесть из делимого (т.е. a) делитель (т.е. b), пока a-b*c>=0. Но возникает проблема при делении большого числа на маленькое. Предлагаю использовать стратегию определения стартового числа инкремента. Пусть надо поделить 365762613 на 3. Очевидно, что начинать вычитать число 3 глупо. Не трудно догадаться, что при делении числа с количеством знаков N на число с количеством знаков M получится число с количеством знаков в целой части не больше N-M+1. Значит, результат от деления 365762613 на 3 будет занимать не больше 9 знаков. Далее, чтобы число для вычитания было не больше делимого, можно смело из числа сделать число, кратное 3 с восмью нулями. Таким образом на первом шаге деления получаем 365762613 и инкремент 300000000. Так, мы сэкономили 10000000 циклов вычитания, сделав его за один цикл. Теперь знаем, что результат деления 365762613 на 3 будет не меньше 100000000. Вычитаем 365762613 - 300000000, получаем 65762613. Теперь применяем туже стратегию: 65762613 - 30000000. И т.д.. Таким образом деление очень больших чисел на небольшие занимает не много времени. Количество циклов такого способа равно N-M+1 (т.е. может быть определено априорно) в отличие от "чистого вычитания".
Да, интересный метод. А почему столбиком - небыстро? Мне казалось, что это довольно приемлемый способ.
Да, интересный метод. А почему столбиком - небыстро? Мне казалось, что это довольно приемлемый способ.[/quote]
Почему? Потому что опять же при делении очень большого числа на какое-нибудь простое, например число 7 или 3 оно будет медленно. Сам алгоритм прост, но его реализация довольно громоздкая. Единственную грамотную реализацию такого метода я видел в книге Г. Уоррена "Алгоритмические трюки" на языке C, там она занимала около 80 строк кода.
А не проще заюзать fpu?
Не знаю, есть ли ты все еще на этом форуме, 3A3-968M, но спасибо тебе огромное за алгоритм деления через вычитание! Все отлично работает, и гораздо быстрее, чем через деление столбиком!