Целочисленная арифметика.
П1) Поиск делителей числа. Простые числа.
Говорят, что натуральное число b является делителем натурального числа a, если существует натуральное число c, такое что a = bc (1). Если b – делитель a, то, очевидно, a mod b = 0 и наоборот.
Найдем количество делителей и сами делители числа а. Для этого будем перебирать все числа i, подходящие на роль делителя. Очевидно, что 1 <= i <= a. Чтобы ускорить работу алгоритма заметим, что если i – делитель а, то a/i – тоже делитель a, и к тому же одно из чисел i и a/i не превышает Sqrt(a) (если предположить противное, то получим a = i*(a/i) > Sqrt(a)*Sqrt(a) = a – противоречие). Поэтому достаточно перебирать числа i в пределах от 1 до Trunc(Sqrt(a)) и при нахождении, что некоторое i – делитель выдавать, что a/i – тоже делитель и увеличивать количество делителей на 2. Этот алгоритм не будет работать, когда a – точный квадрат (почему?), что легко исправляется (как?).
Приведенные соображения реализованы в алгоритме (2):
c:= 0;
For i:= 1 to Trunc(Sqrt(a)) do
If a mod i = 0 then begin
If i*i = a then begin
c:= c+1;
WriteLn(‘Найден делитель ’, i);
end (2)
else begin
c:= c+2;
WriteLn(‘Найден делитель ‘, i);
WriteLn(‘Найден делитель ‘, a div i);
end;
end;
WriteLn(‘Количество делителей ‘, c);
Очевидно, что любое натуральное число a имеет хотя бы 2 делителя: 1 и a. Если число a не имеет никаких других делителей, кроме этих, то будем говорить, что a – простое. Для того, чтобы проверить, является ли число простым, нужно посчитать количество его делителей (алгоритм (2)).
Найдем все простые числа, не превосходящие заданного N.
Возможны несколько подходов к решению этой задачи:
1) Метод Эратосфена. Выпишем все числа от 2 до N. Затем, пока есть числа, которые не вычеркнуты и не обведены, делаем следующий набор операций: обводим минимальное из оставшихся чисел, вычеркиваем все числа, кратные ему. После окончания работы алгоритма все простые числа будут обведены.
Доказательство. Данный алгоритм не может вычеркнуть простое число, так как если число вычеркивается, то оно заведомо делится на какое-то другое, не равное ему. Теперь докажем по индукции, что для любого N алгоритм обводит все простые числа, не превосходящие N. База: при N = 2 утверждение верно, так как 2 будет обведено на 1-м шаге. Индуктивный переход: пусть утверждение верно при 2 <= N <= k-1. Рассмотрим N = k. Если N – составное, то у числа N есть простой делитель t, в качестве которого можно взять, например, его минимальный делитель (почему?). По индукции, на каком-то шаге число t будет обведено, на этом же шаге будет вычеркнуто N. Если же N – простое, то оно не может быть вычеркнуто, поэтому на каком-то шаге станет минимальным из оставшихся и будет обведено. Утверждение доказано.
Приведенные соображения реализованы в алгоритме (3):
FillChar(B, SizeOf(B), True);
For j:= 2 to N do
If B[j] then
Begin
WriteLn(j, ‘ – простое’);
i:= 2*j;
While i <= N do begin (3)
B[i]:= False;
i:= i+j;
End;
end;
2) Будем хранить в массиве уже найденные простые числа. Рассматривая очередное число X, будем делить его на все уже полученные простые числа, не превосходящие Trunc(Sqrt(X)).
Доказательство. Корректность работы алгоритма следует из того, что, если число – составное, то оно обязательно имеет простой делитель, не превосходящий корня из этого числа (почему?).
Упражнение. Реализовать данный подход и получить некоторый алгоритм (4). Сравнить алгоритмы (3) и (4) по быстродействию и использованию памяти.
П2) Основная теорема алгебры.
Верна следующая ТЕОРЕМА (основная теорема алгебры). Всякое число Nпредставимо в виде произведения простых сомножителей, причем такое представление единственно с точностью до порядка сомножителей.
Доказательство. Для доказательства существования разложения воспользуемся индукцией по N с учетом, что любое число либо является простым, либо имеет простой делитель (проведите сами). Докажем единственность. Предположим, что N = p1p2…pk = t1t2…tl, где все сомножители – простые числа, причем p1<=…<=pk и t1<=…<=tl. С учетом соображений индукции, достаточно доказать, что p1 = t1 (почему?). Предположим противное и пусть, для определенности, p1 < t1. Так как t1, …, tl – простые, то p1 не является делителем каждого из этих чисел. Тем не менее p1 – делитель их произведения. Поэтому должны существовать числа a1, b1, …, al, bl такие, что a1b1 = t1, …, albl = tl, a1a2…ak = p1 (почему?). Но, так как любое ai = 1 или ai = ti (ведь ti – простое число), то a1a2…ak либо равно 1, либо не меньше t1, что заведомо меньше, чем p1. Противоречие.
Из доказательства теоремы следует следующий алгоритм (5) нахождения разложения числа на простые множители:
D:= 2;
While d <= Trunc(Sqrt(N)) do begin
While N mod d = 0 do begin
WriteLn(d);
N:= N div d; (5)
end;
If d = 2 then d:= 3
else d:= d+2;
end;
If N <> 1 then WriteLn(N);
Объединяя равные простые множители в разложении числа N, получим представление числа N в виде: N = (6), где a1, …, ak – произвольные натуральные числа. (6) называют каноническим разложением числа N. Переход к каноническому разложению упрощает решение многих задач.
Важные примеры.
1) Пусть N задано в виде (6). Тогда для количества c делителей числа Nверно: c = (a1+1)…(ak+1) (7).
Доказательство. Любой делитель t числа N можно представить в виде t = , где 0 <= b1 <= a1, …, 0 <= bk <= ak. Так как существует ровно a1+1 способ выбора числа b1, …, ak+1 способ выбора числа bk, то формула (7) верна.
2) Пусть N задано в виде (6). Тогда для суммы s делителей числа N верно: s = (8).
Доказательство. Представляя делители так же, как и в предыдущем примере, суммируя их и применяя распределительный закон, получаем s = (1+p1+…+)…(1+pk+…+). Сворачивая каждую скобку по формуле суммы геометрической прогрессии, получаем (8).
П3) НОД и НОК. Взаимно простые числа.
Если число c является делителем a и b, то говорят, что число c является общим делителем чисел a и b. Число d называют наибольшим общим делителем (НОД) чисел a и b, если d – общий делитель a и b и любой общий делитель a и bявляется делителем d.
Если числа a и b являются делителями числа c, то говорят, что число cявляется общим кратным чисел a и b. Число d называют наименьшим общим кратным (НОК) чисел a и b, если d – общее кратное a и b и d – делитель любого общего кратного a и b.
Если a = , b = , где ai, bi >= 0, то, очевидно, что НОД(a, b) = и НОК(a, b) = . Отсюда, учитывая, что max{x,y}+min{x,y} = x+y (почему?), получаем ab = НОД(a, b)НОК(a, b) (9).
Найдем НОД(a, b). Верны следующие равенства:
1) НОД(a, b) = НОД(b, a) – следует из определения.
2) НОД(a, 0) = a – очевидно.
3) НОД(a, b) = НОД(a mod b, b).
Доказательство. Докажем сначала, что НОД(a, b) = НОД(a-b, b). Пусть c – общий делитель a и b. Тогда a = kc, b = lc, a-b = (k-l)c, поэтому с – общий делитель a-b и b. Аналогично показывается, что если c – общий делитель a-b и b, то с – общий делитель a и b. Поэтому множества общих делителей пар (a, b) и (a-b, b) совпадают. А значит НОД(a,b) = НОД(a-b, b). Применяя эту формулу adiv b раз, получим требуемое (почему?).
Для нахождения НОД можно использовать следующий алгоритм (10) Евклида:
While (a<>0) and (b<>0) do
If a>b then a:= a mod b (10)
else b:= b mod a;
nod:= a+b;
Корректность этого алгоритма следует из вышеуказанных свойств НОДа.
Для нахождения НОК можно использовать формулу (9) (как?).
Справедливо следующее утверждение: существует целые числа u и v такие, что au+bv = НОД(a, b).
Доказательство. Находя НОД по алгоритму Евклида, мы, по сути дела, записали следующие равенства: a = q1b+r1, b = q2r1+r2, …, rn = qn+2rn+1+rn+2, rn+1 = qn+3rn+2. Причем НОД(a, b) = rn+2. Развернем эту цепочку равенств в другую сторону: НОД(a, b) = rn+2 = rn-qn+2rn+1 = rn-qn+2(rn-1-qn+1rn) = -qn+2rn-1+(1+qn+2qn+1)rn = krn-1+lrn = … = Ab+Br1 = Ab + B(a-q1b) = Ba + (A-Bq1)b = au + bv, что и требовалось доказать.
Из этого доказательства следует алгоритм (11) нахождения u и v по a и b.
Упражнение. Записать алгоритм (11).
Числа a и b называются взаимно простыми, если НОД(a, b). Обозначим через (N) количество чисел, взаимно простых с N. Пусть N задано в виде (6). Чему равно (N)?
Оказывается, (N) = N(1-)…(1-) (12).
Доказательство. Рассмотрим все числа от 1 до N. Докажем, что если вычеркнуть числа, кратные каким-то , то для любого i такого, что i <> i1, …., i <> it, доля оставшихся чисел, кратных pi равна . Действительно, количество оставшихся чисел, кратных pi равно количеству ci чисел от 1 до , не делящихся ни на одно из , а количество оставшихся чисел равно количеству c чисел от 1 до N, не делящихся ни на одно из . Вместе с тем, так как кратно , то для любого j от 1 до верно, что (j mod , …, j mod ) = ((j+)mod , …, (j+) mod ) = … = ((j+) mod , …, (j+) mod ). Поэтому , что и требовалось доказать. Теперь пусть N записано в виде (6). Вычеркнем все числа, кратные p1. Останется N(1-число. Продолжим вычеркивать числа: кратные p2, …, pk. Останется N(1-)…(1-) число, и все они, очевидно, будут взаимно простыми с N. Поэтому формула (12) верна.
П4) Системы счисления.
Рассмотрим произвольные натуральные числа N и p. Существуют единственные числа с0, с1, ..., сn такие, что сnpn+…+c1p+c0 = N, причем 0 <= ci < p (13). Здесь n = [logpN].
Доказательство. Предположим, есть еще одно разложение dnpn+…+d1p+d0 = N. Тогда, (dn-cn)pn+…+(d1-c1)p+(d0-c0) = 0. Пусть, di-ci – самый левый ненулевой коэффициент и пусть, для определенности, di-ci < 0, тогда di-ci <= -1. Тогда, (dn-cn)pn+…+(d1-c1)p+(d0-c0) = (di-ci)pi+…+(d1-c1)p+(d0-c0) <= -pi+(p-1)(pi-1+…+p+1) = -pi + (p-1) = -1 < 0. Противоречие.
Набор (с0, с1, ..., сn) однозначно описывает число N. В таком случае говорят, что N представлено в системе счисления с основанием p и пишут N = (cn…c1c0)p.
Как по числу N определить числа сi? Из (13) следует, что с0 = N mod p и сnpn-1+…+c1 = N div p. Повторяя указанный процесс до тех пор, пока N <> 0, получим искомое разложение. Данную идею реализовывает алгоритм (14):
i:= 0;
While N<>0 do begin
c[i]:= N mod p;
N:= N div p; (14)
i:= i+1;
end;
n:= i-1;
Обратная задача: по числам c0, c1, …, cn найти N. Для ее решения воспользуемся формулой (13), переписанной в виде: N = p(…(p(pcn+cn-1)+cn-2)+….)+c0 (для чего?). Задачу решает алгоритм (15):
N:= 0;
For i:= n downto 0 do (15)
N:= p*N+c[i];
Важным частным случаем является p = 10, при котором мы получаем алгоритмы разбиения числа на цифры и сворачивания массива цифр в число. Применение систем счисления часто упрощает решение различных задач.
П5) Метод остатков.
Часто, для решения задачи нам нужно вычислить не само число, а остаток от деления этого числа на какое-то другое. Идея метода остатков состоит в том, чтобы работать не с самим числом, а только с остатком. Для этого полезно обзавестись некоторыми тождествами.
Итак, верны следующие равенства:
1) (c+d) mod n = ((c mod n) + (d mod n)) mod n (16.1)
2) (c-d) mod n = ((c mod n) – (d mod n)) mod n (16.2)
3) (cd) mod n = ((c mod n)(d mod n)) mod n. (16.3)
Доказательство. Докажем 1-е равенство, 2-е и 3-е доказываются аналогично. Итак, пусть cr = c mod n, то есть c = qrn+cr; dr = c mod n, то есть c = prn+dr. Тогда (c+d) mod n = ((qr+pr)n+cr+dr) mod n = (cr+dr) mod n = ((c modn)+(d mod n)) mod n, что и требовалось доказать.
Применим этот метод для разработки «универсального признака делимости»: алгоритма, позволяющего выяснить делится ли число N на число k, причем число N записано в системе счисления с основанием p. Нам поможет алгоритм (15), только теперь, вместо числа N, мы, руководствуясь (16.1) и (16.3), будем вычислять N mod k. «Универсальный признак делимости» реализовывает алгоритм (17):
t:= 0;
For i:= n downto 0 do (17)
t:= (p*t+c[i]) mod k;
П6) Длинная арифметика.
Под длинной арифметикой будем понимать набор алгоритмов работы с числами, заданными в табличной форме в системе счисления с основанием p. Реализация арифметических действий над такими числами по сути дела представляет собой простую реализацию сложения, вычитания, умножения и деления «столбиком». Поэтому далее без пояснений приводятся алгоритмы (18) сложения, (19) вычитания и (20) умножения «длинных» чисел A = (an…a1a0)p и B = (bm…b1b0)p.
p:= 0;
For i:= 0 to max(m, n)+1 do begin
R[i]:= (A[i]+B[i]+p) mod 10; (18)
p:= (A[i]+B[i]+p) div 10;
end;
FillChar(R, SizeOf(R), 0);
For i:= 0 to max(m, n) do begin
R[i]:= R[i]+A[i]-B[i];
If R[i] < 0 then begin (19)
R[i]:= R[i]+10;
R[i+1]:= R[i+1]-1;
End;
end;
FillChar(R, SizeOf(R), 0);
For i:= 0 to n do
For j:= 0 to m do
R[i+j]:= R[i+j]+A[i]*B[j];
i:= 0; (20)
While R[i] <> 0 do begin
R[i+1]:= R[i+1]+(R[i] div 10);
R[i]:= R[i] mod 10;
i:= i+1;
End;
Упражнение. Разработать алгоритмы (21) сравнения длинных чисел, (22) умножения длинного числа на короткое и (23) деления длинных чисел (нахождения частного и остатка). Особое внимание обратите на последний алгоритм, который является сложным, но важным.
Немає коментарів:
Дописати коментар