Лекции - Структуры и алгоритмы компьютерной обработки данных / 3.Числовые алгоритмы. Длинная арифметика. Теоретико-числовые алгоритмы. Проверка чисел на простоту
..docЧисловые алгоритмы
-
Алгоритмы, связанные с записью числа
-
Алгоритмы, связанные со значением числа (теоретико-чиcловые)
Получение цифр числа
Определить сумму цифр десятичной записи натурального числа.
Будем отделять от числа цифры и считать их сумму.
function DigitSum (n: longint) : word; {Подсчет суммы цифр
натурального числа.}
var sum: word;
begin
sum: = 0;
while n>0 do
begin
sum: = sum + n mod 10;
n: = n div 10
end;
DigitSum:= sum
end;
Получение числа из строки цифр
function str2int(s:string; base:integer) : word;
var
n: word; {преобразованное число}
i: integer; {счетчик символов}
digit: integer; {очередная цифра}
begin
n:=0;
for i:=1 to length(s) do
begin
digit:= char2digit(s[i]);
if digit in [0..base-1]
then n:=base*n + digit;
else break; {обнаружен неверный символ -
досрочное прекращение обработки}
end;
str2int: =n
end;
Длинная арифметика
Представление длинного числа 123456
Хранение либо 00123456, либо 65432100, не правильная запись 12345600
Type item = longint;
Long = array [1..N] of item;
Оценка длины числа
K = [lg n]+1
N=2300
N = (23)100=8100<10100.
Ввод числа
procedure StringToLong(s:String; var x:Long);
Var l,i,k:integer;
begin
l:=length(s);
for i:=1 to N do x[i]:=0;
for i:=1 to l do Val(s[i],x[i+N-l],k);
end;
Сложение длинных чисел
procedure AddLong(x,y:Long; var z:Long);
Var i,c:integer;
begin
c:=0;
for i:=N downto 1 do
begin
z[i]:=(x[i]+y[i]+c) mod 10;
c:=(x[i]+y[i]+c) div 10;
end;
end;
Сравнение и вычитание
-
Сравнение длинных чисел.
Перебираем цифры с начала массива, пока не найдем две различные цифры. Больше то число, которому принадлежит большая из этих цифр.
-
Вычитание длинных целых.
На каждом шаге из цифры одного числа вычитается цифра другого и перенос. Если результат отрицательный, то к нему прибавляется 10 и перенос становится равным 1, иначе перенос обнуляется.
Умножение и деление
-
Умножение длинного целого на обычное целое.
Аналог сложения.
2. Умножение длинного целого на степень 10.
Эта операция заключается в дописывании к числу нескольких нулей. При этом все значащие цифры сдвигаются влево.
3. Умножение длинных целых.
Реализуется с использованием процедур сложения, умножения на обычное целое число и умножения на степень 10.
4. Деление длинных чисел c остатком.
Сводится к вычитанию. Сначала обнулим остаток, далее будем добавлять к остатку по одной цифре делимого, взяв их слева. Каждый раз выполняем цикл: пока остаток не меньше делителя, вычитаем делитель из остатка и увеличиваем очередную цифру частного.
Возведение в степень
function Power(a,b:longint):longint;
begin
if b=0 then Power:=1
else if odd(b) then Power:=a*Power(a,b-1)
else Power:=sqr(Power(a,b div 2))
end;
Сложность Ө(log b)
Теоретико-числовые алгоритмы: перебор делителей
Делители n можно искать парами, если n = ab, то добавлять в сумму сразу слагаемое a+b. При этом нетрудно показать, что меньший из этих делителей не больше √n, а больший - не меньше √n. Действительно, предполагая, например, √n < a ≤ b, получим противоречие: ab > (√n)2 = n. Таким образом, можно перебирать делители до √n. Получаем функцию со сложностью Ө(√n ).
function SumDiv(n: longint):longint;
Var i,s: longint;
begin
s:= 0; i:= 1;
while ( i * i ) <= n do
begin
if n mod i = 0 then
if i = n div i then s:= s + i
else s:= s + i + n div i;
i:= i + 1;
end;
SumDiv:=s;
end;
Наибольший общий делитель
Алгоритм Евклида
function nod(a,b:integer):integer;
begin
if b=0 then nod:=a
else nod:=nod (b, a mod b)
end;
Сложность Ө(log max(a,b))