Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Деление больших чисел. Пмогите найти ошибку!

17K
08 июля 2006 года
garis
5 / / 08.07.2006
Ребят, прога как-то странно себя ведёт. Помгите найти ошибку. Программа основывается на последовательном вычитании. Некоторые числа делит нормально, например 124/4 или 98765432199/123456789, а вот если ввести 12345678900987654321/918273645, то выдает абракадабру :(

Вот код:
Код:
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.
242
08 июля 2006 года
Оlga
2.2K / / 04.02.2006
пожалуйста отформатируй текст отступами и самое главное напиши подробно коментарии, что бы легче было понять твою идею и цели
17K
08 июля 2006 года
garis
5 / / 08.07.2006
На другом форуме великий Volvo887 уже помог разобраться. :)

Переписываем условие вот так:

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;
18K
16 июля 2006 года
Exile
5 / / 16.07.2006
Чисто ради интереса - условие задачи предпологает, что искомые числа должны разделиться нацело?
17K
16 июля 2006 года
garis
5 / / 08.07.2006
Программа выдает целочисленное частное и целочисленный остаток
16K
24 июля 2006 года
task00
9 / / 17.07.2006
http://task00.by.ru/task417_index.htm

там есть что-то для работы с большими числами (с числами в символьном представлении). В ответах найдете целую библиотеку.
16K
24 июля 2006 года
vain
9 / / 18.07.2006
В твоём прекрасно отформатированном исходнике разобратся абсолютно невозможно. Кстати описанный тобой аглоритм не может работать, если первое число НАМНОГО больше второго. Представь сколько раз проге придётся вычитать из 12345678901234567890 число 1234567890. Ответ: 10^9 раз(!). Эффективнее работает деление "столбиком" и реализация не намного сложнее. Но если тебе интересно найти у себя ошибку, то прилагаю исходник правильно работающей проги, написанной по описанному тобой алгоритму. А вообще советую книгу Окулова "Программирование в алгоритмах". Кстати её можно найти в электронном варианте. Где - не помню(у меня она бумажная есть).
PS Если хочешь, могу выложить исходник деления "столбиком"
273
28 июля 2006 года
3A3-968M
1.2K / / 22.12.2005
Деление в "столбик" тоже особенной быстротой не отличается. Всё таки грамотный выход - вычитание. Пусть 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 (т.е. может быть определено априорно) в отличие от "чистого вычитания".
16K
28 июля 2006 года
vain
9 / / 18.07.2006
> стратегию определения стартового числа инкремента
Да, интересный метод. А почему столбиком - небыстро? Мне казалось, что это довольно приемлемый способ.
273
28 июля 2006 года
3A3-968M
1.2K / / 22.12.2005
[quote=vain]> стратегию определения стартового числа инкремента
Да, интересный метод. А почему столбиком - небыстро? Мне казалось, что это довольно приемлемый способ.[/quote]
Почему? Потому что опять же при делении очень большого числа на какое-нибудь простое, например число 7 или 3 оно будет медленно. Сам алгоритм прост, но его реализация довольно громоздкая. Единственную грамотную реализацию такого метода я видел в книге Г. Уоррена "Алгоритмические трюки" на языке C, там она занимала около 80 строк кода.
17K
25 августа 2006 года
Yar4
15 / / 10.07.2006
А не проще заюзать fpu?
53K
29 ноября 2009 года
shaker
1 / / 25.09.2009
Не знаю, есть ли ты все еще на этом форуме, 3A3-968M, но спасибо тебе огромное за алгоритм деления через вычитание! Все отлично работает, и гораздо быстрее, чем через деление столбиком!
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог