| И в библиотеке бывают рекламные паузы. |
Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое делит эти два числа. По определению НОД(0,0)=0.
Данный алгоритм вычисления НОД двух целых чисел a и b состоит в следующем: если хотя бы одно из чисел равно нулю, то НОД(a,b)=|a+b|, в других случаях последовательно находятся остатки ri от делений:
a на b-a=bq1+r1, b на r1-b=r1q2+r2, r1 на r2-r1=r2q3+r3, . . . . . .и т.д., пока rn+1 не станет равно нулю. Тогда НОД(a,b)=НОД(b,r1)=НОД(r1 ,r2)=...=НОД(rn-1 ,rn )=rn.
Данный алгоритм вычисления НОД(a,b) основан на бинарном алгоритме Евклида. Вычисления проводятся на основании следующих свойств НОД:
НОД(2m,2n)=2 НОД(m,n), НОД(2m,2n+1)= НОД(m,2n+1), НОД(-m,n)= НОД(m,n).
Алгоритм, кроме поиска НОД двух целых чисел a,b также находит величины x,y, т.ч. ax+by=НОД(a,b). Алгоритм включает в себя алгоритм Евклида и похож на алгоритм решения диофантового уравнения, который рассматривается здесь. Привожу его поскольку часто возникает необходимость отыскать именно x,y удовлетворяющие приведенному выше условию.
Наименьшим общим кратным двух целых чисел a и b называется наименьшее положительное число, которое делится на a и b.
Известно, что
НОК(a,b)=ab/НОД(a,b).
Сначала в функцие вычисляется НОД(a,b), затем НОК по предыдущей формуле. При a=0 или b=0 НОК полагается равным 0.
В последовательности чисел 2,3, ... , n последовательно вычеркиваем каждое второе число после 2. Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор, пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n неравное 1 не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.
Колличество простых чисел r не превышает:
trunc(1.6n/ln n+1), если n<=200; trunc(n/(lnn-2)+1), если n>200.
Процедура заполняет массив P простыми числами меньшими n, элемент массива является последним, если следующий за ним элемент равен 0.
Алгоритм складывает два целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.
A=anpn+an-1pn-1+...+a0, B=bmpm+bm-1pm-1+...+b0.
Элементы массивов - целые в промежутке от 0 до p-1. Сумма помещается в массив C, а колличество разрядов суммы представленно переменной l.
Алгоритм достаточно простой и приводится только потому, что в дальнейшем я буду его использовать. Всю информацию об алгоритме можно получить из блок-схемы.
Алгоритм сравнивает два целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.
A=anpn+an-1pn-1+...+a0, B=bmpm+bm-1pm-1+...+b0.
Элементы массивов - целые в промежутке от 0 до p-1. Результат работы функции -1,0,1 соответствует случаям A < B, A=B, A > B.
Алгоритм достаточно простой и приводится только потому, что в дальнейшем я буду его использовать. Всю информацию об алгоритме можно получить из блок-схемы.
Алгоритм вычисляет разность двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.
A=anpn+an-1pn-1+...+a0, B=bmpm+bm-1pm-1+...+b0.
Элементы массивов - целые в промежутке от 0 до p-1. Результат работы помещается в массив С, колличество разрядов разности представленно переменной l, знак разности совпадает с знаком sign.
Всю информацию об алгоритме можно получить из блок-схемы.Используется описанный ранее алгоритм сравнения.
Алгоритм вычисляет произведение двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.
A=anpn+an-1pn-1+...+a0, B=bmpm+bm-1pm-1+...+b0.
Элементы массивов - целые в промежутке от 0 до p-1. Результат работы помещается в массив С, колличество разрядов произведения представленно переменной l.
Всю информацию об алгоритме можно получить из блок-схемы.
Алгоритм вычисляет частное и остаток при делении двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.
A=anpn+an-1pn-1+...+a0, B=bmpm+bm-1pm-1+...+b0.
Элементы массивов - целые в промежутке от 0 до p-1. Частное помещается в массив С, колличество разрядов частного представленно переменной l. Остаток помещается в массив D, колличество разрядов остатка представленно переменной k.
Всю информацию об алгоритме можно получить из блок-схемы. Используются описанные ранее алгоритмы вычитания и сравнения.
Алгоритм переводит число представленное в системе счисления с основанием p в систему счисления с основанием q. Цифры p-ичного разложения числа хранятся в массиве a при этом число в этой системе имеет n разрядов. Полученное представление в системе с основанием q помещается в массив b и имеет m разрядов:
A=anpn+an-1pn-1+...+a0=bmqm+bm-1qm-1+...+b0.
Элементы массива a - целые в промежутке от 0 до p-1, элементы массива b - целые в промежутке от 0 до q-1. В зависимости от того основание какой системы счисления больше, применяется разные алгоритмы перевода:
1. В случае p > q алгоритм перевода заключается в последовательном делении исходного числа на q (операция осуществляется в системе с основанием p) и заполнения массива b остатками от деления (заполнять начинаем с младшего разряда). Т.е.
A = A1*q+b0 A1 = A2*q+b1 ...Понятно, что для некоторого k получим Ak=0 и алгоритм завершится.
2. В случае p < q алгоритм перевода заключается в вычислении:
A=an*pn+an-1*pn-1+a0при этом операции производим в системе счисления с основанием q.
В принципе в обоих случаях можно использовать алгоритм 2, но если во-втором случае известно представление p в системе с основанием q, то в случае p > q его вначале необходимо получить. Использование алгоритма 1 в случае 2, так же не слишком привлекательно, т.к. если в случае 1, остаток всегда представляется одной цифрой, то в случае 2 такое свойство нарушается.
Полною информацию об алгоритме можно получить из блок-схемы. Используются описанные ранее алгоритмы сложения,сравнения, умножения и деления с остатком.
|