Курсовая работа: Нод и нок многочленов

в равенство , будем иметь:



Итак, любое любое общее кратное многочленов и ) делится на ). Следовательно, ) есть НОК многочленов и ). Теорема доказана. [1,2,11]

Пример 1. Найти НОК многочленов.



Решение:

1. 
   Найдем НОД
   

А) . Получаем, что ;Б) . Получаем, что ;Итак, НОД .

2. 
   
   
3. 
   
   

По схеме Горнера Ответ: .

2.3 Алгоритм Евклида нахождения наибольшего общего делителя двух чисел

Пусть даны целые числа . Для вычисления наибольшего делителя существует хорошо известный алгоритм Евклида. , , Тогда и для его нахождения требуется выполнить делений с остатком. Оценим сначала количество шагов алгоритма Евклида.[4]Определение 3. Последовательностью чисел Фибоначчи называется рекуррентная последовательность видаОбозначим также через положительный корень квадратного уравнения Лемма 1. При любом справедливо неравенство .Доказательство проведем индукцией по . При неравенство проверяется непосредственно. Далее, используя предположение индукции и определение последовательности Фибоначчи, имеем Теорема 1.3. Число делений с остатком в алгоритме Евклида для нахождения наибольшего общего делителя чисел не превосходят величины Доказательство. Индукцией по докажем, что

. При данное неравенство выполнено, так как . Для в силу предположения индукции имеем .В силу доказанного или Из последнего неравенства следует оценка числа шагов алгоритма Евклида. Теперь оценим сложность алгоритма Евклида. Пусть , где - число шагов алгоритма. Очевидно, выполняются условия . Тогда, учитывая сложность деления с остатком, можно оценить сложность алгоритма Евклида величиной .Так как оценивается теоремой 1.3 как , то сложность всего алгоритма можно оценивать величиной . Если длина чисел не превосходит , то полученная оценка имеет вид .Без доказательства приведем еще одну оценку для количества шагов алгоритма Евклида. [7]Теорема 1.4. Число делений с остатком в алгоритме Евклида для нахождения наибольшего общего делителя не превосходит величины .Замечание. Оценка теоремы Ламе достижима. Так , и для нахождения наибольшего общего делителя требуется ровно 5 шагов алгоритма Евклида. Приведем также без доказательства теорему о среднем числе шагов алгоритма Евклида.

Теорема 1.5. Если целочисленные случайные величины равномерно и независимо распределены на множестве , и - случайная величина, равная числу шагов алгоритма Евклида нахождения , то .При переходе к десятичным логарифмам имеем . Значит, полученные выше оценки числа шагов алгоритма Евклида в среднем завышены примерно в два с половиной раза. [4]

2.4 Расширенный алгоритм Евклида

Пусть алгоритм Евклида на каждом шаге, кроме частного и остатка , вычисляет еще два значения по правилуТакой алгоритм будет называться расширенным алгоритмом Евклида. В расширенном алгоритме Евклида для всех выполняется равенство . Значение расширенного алгоритма Евклида состоит в том, что он дает линейное разложение наибольшего общего делителя , которое играет важнейшую роль в операциях модульной арифметики.Легко показать, что длина чисел оценивается величиной . Значит, сложность расширенного алгоритма Евклида отличается от сложности обычного алгоритма Евклида не более чем на константный множитель, т.е. для расширенного алгоритма Евклида сохраняется оценка сложности . [6]

2.5 Другие алгоритмы вычисления наибольшего общего делителя

Рассмотрим сначала один из простейших способов ускорения работы алгоритма Евклида. Пусть в ходе выполнения алгоритма вычисляются величины , Здесь на