Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.97.14.84] |
|
Сообщ.
#1
,
|
|
|
Недавно решал задачи про длинную арифметику. Написал еще 2 процедуры - это длинное вычитание и деление длинного на короткое. Вот:
procedure longsub(a,b:tlong; var c:tlong); var k,i,p:longint; begin fillchar(c,sizeof(c),0); if a[0]>b[0] then k := a[0] else k := b[0]; p := 0; for i := 1 to k do begin c[i]:=a[i]-b[i]-p; if c[i]<0 then begin p := 1; inc(c[i],osn); end else p:=0; end; for i := k downto 1 do if c[i]<>0 then break; c[0]:=i; end; procedure longdiv(a:tlong; b:longint; var c:tlong); var p:longint; i,j,ost:integer; begin fillchar(c,sizeof(c),0);p:=0; i := 1; j := a[0]; while i<j do begin swap(a[i],a[j]); inc(i); dec(j); end; ost:=0; for i := 1 to a[0] do begin c[i]:=(Longint(ost)*osn+a[i])div b; ost :=(Longint(ost)*osn+a[i])mod b; end; if c[1]=0 then begin c[0]:=a[0]-1; for i := 1 to c[0] do c[i]:=c[i+1]; c[c[0]+1]:=0; end else c[0]:=a[0]; i := 1; j := c[0]; while i<j do begin swap(c[i],c[j]); inc(i); dec(j); end; end; Прошу приобщить все это к основной статье. |
Сообщ.
#2
,
|
|
|
А обьяснить принцип? Как ты пришёл к этим процедурам? Это всё желательно показать, т.к. готовых процедур и модулей в интернете полно, а вот нормального описания мало.
|
Сообщ.
#3
,
|
|
|
ну хорошо. начнем с вычитания.
Цитата Arsuit @ в этой строчке мы в переменную k записываем max(a[0],b[0]) - для границы цикла.if a[0]>b[0] then k := a[0] else k := b[0]; Затем мы запускаем цикл от 1 до k. Переменная p служит для того, чтобы мы знали, занимали ли мы из соседнего разряда, или нет. (Если занимали, то p=1, иначе p=0 (все помнят вычитание столбиком?)). Цитата Arsuit @ Текущему разряду ответа присваиваем разность текущих разрядов вычитаемого и ... ну как его... то, что вычитают. Не помнь я как оно называется. Скажите пожалуйста, кто помнит. Ну так вот. Текущему разряду разности присваиваем разности вичитаемого, то, что вычитают и, если мы из этого разряда занимали, то вычитаем еще и единицу. Затем мы проверяем, если разность получилась отрицательной (if c[i]<0) то занимаем из соседнего разряда, а к текущему разряду ответа прибавляем основание (т. к. он стал отрицатльным).c[i]:=a[i]-b[i]-p; и наконец вот эти Цитата Arsuit @ строки определяют кол-во цивр в ответе.for i := k downto 1 do if c[i]<>0 then break; c[0]:=i; Ну вот с вычитанием мы вроде немного разобрались. Теперь деление. (Чтобы понять все, что здесь написано, вы должны помнить, как делятся числа столбиком ) Цитата Arsuit @ i := 1; j := a[0]; while i<j do begin swap(a[i],a[j]); inc(i); dec(j); end; начнем с этих строк. Они переворачивают делимое. (если кто помнит, в длинной арифметике все числа записаны задом на перед - так с ними удобнее работать, в данном же случае (в случае деления) с длинным числом как раз таки удобнее работать, если оно записано в нормальном виде). В переменной ost хранится остаток от деления разряда делимого на делитель. На каждом шаге цикла от 1 до a[0] мы к текущему остатку приписываем цифру из текущего разряда делимого (Longint(ost)*osn+a[i]), и делим все это на делитель (div b) и записываем в разряд частного. А в переменную, хранящую остаток мы записываем остаток от деления (Longint(ost)*osn+a[i]) на делитель. Все. число поделено. if c[1]=0 then begin c[0]:=a[0]-1; for i := 1 to c[0] do c[i]:=c[i+1]; c[c[0]+1]:=0; end else c[0]:=a[0]; если a[1]<b то получится так, что c[1] будет равно 0. Ведущие нули нам не нужны, так что если это так, то сдвигаем все число на разряд влево. А заодно и опредиляем кол-во цифр в ответе. В конце алгоритма мы переворачиваем число обратно. Заметим, что этот алгоритм деления можно несколько усовершенствовать. Можно не переворачивать число, и начать деление с конца. Но выигрыш во времени от этого будет не значительный, а запутаться можно. Так что решайте сами, что вам важнее. Добавлено ну вот. заценивайте статейку. |
Сообщ.
#4
,
|
|
|
ну так это будут приобщать к общей статье?
|
Сообщ.
#5
,
|
|
|
Будут, когда ты это оформишь как следует. В таком виде ничего присоединяться не будет.
|
Сообщ.
#6
,
|
|
|
Хорошо, я уже работаю над этим.
|
Сообщ.
#7
,
|
|
|
Посмотрел я на свою бывшую статью и ужаснулся... Решил все полностью переписать. Вот гляньте, что я пока написал. Оформлю я все пото, когда допишу все до конца. пока прошу просто посмотреть, почитать, дополнить.
Длинная арифметика Что нужно знать, чтобы понять весь изложенный здесь материал: 1. Что такое одномерные массивы 2. Что такое системы счисления, остатки. 3. Уметь складывать, вычитать, умножать, делить числа столбиком. Начальные сведения. Когда вы пишите программы на каком либо языке программирования, бывает такое, что стандартных типов данных не хватает, для решения той или иной задачи. Такое бывает, например, если программа использует какой-либо комбинаторный алгоритм, или просто калькулятор длинных чисел.… Здесь уже стандартных типов данных (longint, int64 для паскаля/дельфи и long long для СИ) не хватит. Есть, конечно, типы с плавающей точкой (double, extended), но и их иногда может не хватить… Именно для таких случаев существует замечательный способ, который называется длинной арифметикой. Длинная арифметика подразумевает собой хранение длинного числа поразрядно, в одномерном массиве. При том способ хранения может быть разный. Некоторые хранят в одном элементе по одной цифре, другие же хранят в одном элементе несколько цифр в целях экономии памяти, т. к. процессор выполняет арифметические операции с различными числами за одно и то же время (это относится к сравнительно коротким числам, которые хранятся в стандартных типах). Я предпочитаю хранить несколько цифр (при этом я считаю, что оптимальное число цифр – 4), и ниже будут примеры, реализующие именно этот способ. Но выбирать, чем пользоваться, все же вам. Однако стоит отметить, что в этом способе ЗНАЧИТЕЛЬНО усложняется процедура чтения длинного числа. Кроме всего прочего, число в массиве записывается «задом на перед» - так удобнее. То есть если у меня есть число 123456789012345, и я храню в элементе по 4 цифры, то оно у меня будет выглядеть так: 2345’8901’4567’123. В паскале длинные числа стоит описывать так: const osn=10000; //основание. Так как в элементе массива мы храним 4 цифры, то можно сказать, что оно записано в osn-ичной системе счисления. max=100; //кол-во элементов массива type TLong=array[0..max] of integer; // собственно сам массив с длинным числом. Для удобства в нулевом элементе храним кол-во занятых элементов массива (как в стандартном типе string). Чтение/вывод Дальнейшее знакомство с длинными числами наверное стоит начать с процедур чтения/вывода длинного числа. Именно с этого как правило приходится начинать писать длинную арифметику (если конечно эти процедуры вообще нужны). Чтение. Для тех, кто хранит в одном элементе массива одну цифру тут все совсем просто. Читаем посимвольно число, преобразуем символы в цифры, записываем в массив. Затем массив переворачиваем (ведь мы храним число «задом на перед», вы не забыли?). Пример: Procedure Long_read(var a:tlong); var c:char; i,j:integer; a:array[1..100] of byte; begin fillchar(a,sizeof(a),0); repeat read(c); until c in ['0'..'9'];//пропускаем не цифры i := 1; while c in ['0'..'9'] do//пока цифры begin inc(i); a[i]:=ord(c)-ord('0'); //преобразуем символ в цифру read(c); //читаем еще символ. end; a[0]:=i; j := i; i := 1; while i<j do //переворачиваем. begin swap(a[i],a[j]); inc(i); dec(j); end; end; Процедура Swap меняет значения переменных. Если же вы все таки надумали хранить в одном элементе несколько цифр, то алгоритм чтения будет другой. Мы читаем из входного файла по одной цифре начиная с начала массива, и по ходу дела перемещаем все вправо. procedure longread(var a:tlong); var c:char; i:longint; begin fillchar(a,sizeof(a),0); //заполняем массив нулями. repeat read(c); until c in ['0'..'9']; //пропускаем не символы. while c in ['0'..'9'] do begin for i := a[0] downto 1 do //цикл смещения. begin a[i+1]:=a[i+1]+(Longint(a[i])*10) div osn; //добавляем одну цифру из текущего разряда в следующий. a[i] := (Longint(a[i])*10) mod osn; //убираем одну цифру из текущего. end; a[1]:=a[1]+ord(c)-ord('0'); // в конец первого разряда записываем полчтенную цифру. if a[a[0]+1]>0 then inc(a[0]); // если мы заняли еще один элемент массива, то увеличиваем нулевой элемент read(c); //читаем очередной символ. end; end; P.S. извиняюсь, что так долго пишу - я школу заканчиваю, экзамены, выпускные, поступление на носу... |