На головну

алгоритм Евкліда

  1.  A. Жадібний алгоритм
  2.  Amp; && 412. Алгоритми підрозділяються на наступні типи
  3.  Адаптивні (динамічні) алгоритми маршрутизації по вектору відстані
  4.  АЛГОРИТМ
  5.  АЛГОРИТМ
  6.  Алгоритм ??ими, ?асіеттері, т?рлері
  7.  Алгоритм 1: Догляд за знімними зубними протезами і порожниною рота

Алгоритм Евкліда -метод для знаходження найбільшого загального дільника двох цілих чисел, а також двох многочленів від одного змінного. Він спочатку був викладений в «Засадах» Евкліда в геометричній формі як спосіб знаходження загальної міри двох відрізків. Алгоритм Евкліда для знаходження найбільшого загального дільника, як в кільці цілих чисел, так і в кільці многочленів від одного змінного є окремим випадком нікого загального алгоритму в евклідових кільцях.

Алгоритм Евкліда для знаходження найбільшого загального дільника двох многочленів и  складається в послідовному розподілі із залишком  на , потім  на перший залишок , потім на другий залишок  і так далі. Так як ступеня залишків весь час знижуються, то в цьому ланцюжку послідовних поділів ми дійдемо до такого місця, на якому поділ здійсниться без остачі і процес зупиниться. Останній відмінний від нуля залишок  , На який без остачі ділиться попередній залишок  , І є найбільшим загальним дільником многочленів и .

Для доказу запишемо викладене у вигляді такої ланцюжка рівностей:

(2.4)

Остання рівність показує, що  служить дільником для  . Звідси випливає, що обидва доданків правої частини передостаннього рівності діляться на  , А тому  буде дільником і для  . Далі, таким же шляхом, піднімаючись вгору, ми отримаємо, що  є дільником і для  , ..., ,  . Звідси через другого рівності, буде слідувати, що  служить дільником для  , А тому, на підставі першого рівності, - і для .

Візьмемо тепер довільний загальний дільник  многочленів и  . Так як ліва частина і перший доданок правої частини першого з рівності діляться на  , то  також буде ділиться на  . Переходячи до другого і наступного равенствам, таким же способом отримаємо, що на  діляться многочлени ,  ... Нарешті, якщо вже буде доведено, що и  поділяються на  , То з передостаннього рівності отримаємо, що  ділиться на  . Таким чином,  насправді буде найбільшим спільним дільником для и .

Ми довели, що будь-які два многочлена володіють найбільшим спільним дільником, і отримали спосіб його обчислення. Цей спосіб показує, що якщо многочлени и мають обидва раціональні або дійсні коефіцієнти, то і коефіцієнти їх найбільшого загального дільника також будуть раціональними або, відповідно, дійсними, хоча у цих многочленів можуть існувати і такі подільники, не всі коефіцієнти яких раціональні (дійсні).

якщо  є найбільший спільний дільник многочленів и  , То, як показують властивості 8. і 9., як найбільшого спільного дільника цих многочленів можна було б вибрати також многочлен  , де  - Довільне число, відмінне від нуля. Іншими словами, їх найбільший спільний дільник двох многочленів визначений лише з точністю до множника нульовий ступеня. Зважаючи на це можна домовитися, що старший коефіцієнт найбільшого загального дільника двох многочленів буде завжди вважатися рівним одиниці. Використовуючи цю умову можна сказати, що два многочлена тоді і тільки тоді взаємно прості, якщо їх найбільший спільний дільник дорівнює одиниці. Справді, як найбільшого спільного дільника двох взаємно простих многочленів можна взяти будь-яке число, відмінне від нуля, але, множачи його на зворотний елемент, отримаємо одиницю.

Застосовуючи алгоритм Евкліда до многочленів з цілими коефіцієнтами, можемо, щоб уникнути дрібних коефіцієнтів, помножити ділене або скоротити дільник на будь-який не рівне нулю число, причому не тільки починаючи будь-яка з послідовних поділів, але і в процесі самого цього поділу. Це буде призводити до спотворення приватного, але цікаві для нас залишки будуть купувати лише деякий множник нульової ступеня, що при розвідці найбільшого загального дільника допускається.

Приклад.Знайти найбільший спільний дільник многочленів и .

1. и

Зробимо необхідні ділення із залишком:

|

|

|

Побудова послідовності Евкліда закінчено. Її останній член  є найбільший спільний дільник вихідних многочленів.

2. и

Зробимо необхідні ділення із залишком:

¦

 || ?

¦

¦

Побудова послідовності Евкліда закінчено. Її останній член  є найбільший спільний дільник вихідних многочленів.

Я склала програму для знаходження найбільшого загального дільника двох многочленів:

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class (TForm)

Label1: TLabel;

Label2: TLabel;

Edit1: TEdit;

Edit2: TEdit;

SGd1: TStringGrid;

Label3: TLabel;

Button1: TButton;

Label4: TLabel;

Edit4: TEdit;

Label5: TLabel;

Label6: TLabel;

procedure Button1Click (Sender: TObject);

private

{Private declarations}

public

{Public declarations}

end;

var

Form1: TForm1;

st1, st2: integer;

kof1, kof2, k1, k2: array [0..10] of integer;

implementation

{$ R * .dfm}

procedure TForm1.Button1Click (Sender: TObject);

var i, j, k_1, st3, l: integer;

sokr: boolean;

k2_2, k1_1: array [0..10] of integer;

begin

st1: = StrToInt (Edit1.Text);

st2: = StrToInt (Edit2.Text);

for i: = 0 to st1 do begin

kof1 [i]: = StrToInt (SGd1.Cells [i, 0]);

k1 [i]: = StrToInt (SGd1.Cells [i, 0]);

end;

for i: = 0 to st2 do begin

kof2 [i]: = StrToInt (SGd1.Cells [i, 1]);

k2 [i]: = StrToInt (SGd1.Cells [i, 1]);

end;

while kof2 [0] <> 0 do begin

repeat

Edit4.Text: = '';

k_1: = k1 [0];

if k1 [0] <> kof2 [0] then begin

if (k1 [0] mod kof2 [0]) = 0 then begin

for j: = 0 to st2 do

k2 [j]: = (k1 [0] div kof2 [0]) * kof2 [j];

end

else begin

if k2 [0] <> 1 then

for j: = 0 to st1 do

k1 [j]: = kof2 [0] * k1 [j];

if k_1 <> 1 then begin

for j: = 0 to st2 do

k2 [j]: = k_1 * kof2 [j];

end;

end;

end;

for i: = 1 to st1 do begin

k1 [i-1]: = k1 [i] -k2 [i];

end;

st1: = st1-1;

until st1

if k1 [0] <> 0 then begin // Скорочення

sokr: = true;

for i: = 1 to st1 do

if k1 [i] <> 0 then begin

if (k1 [i] mod k1 [0]) <> 0 then sokr: = false;

end;

k_1: = k1 [0];

if sokr = true then

for i: = 0 to st1 do

k1 [i]: = k1 [i] div k_1;

end;

for i: = 0 to st2 do // Заміна многочленів

k2_2 [i]: = kof2 [i];

for i: = 0 to st1 do

k1_1 [i]: = k1 [i];

for i: = 0 to 10 do begin

kof1 [i]: = 0;

k1 [i]: = 0;

kof2 [i]: = 0;

k2 [i]: = 0;

end;

for i: = 0 to st2 do begin

k1 [i]: = k2_2 [i];

if k1 [i] <> 0 then

Edit4.Text: = Edit4.Text + IntToStr (k1 [i]) + 'x ^' + IntToStr (st2-i);

if (k2_2 [i + 1]> 0) and (i

end;

for i: = 0 to st1 do begin

k2 [i]: = k1_1 [i];

kof2 [i]: = k1_1 [i];

end;

st3: = st1;

st1: = st2;

st2: = st3;

end;

end;

end.

Використовуємо алгоритм Евкліда для доказу наступної теореми:

Теорема. якщо  є найбільший спільний дільник многочленів и  , То можна знайти такі многочлени и  , що

 . (2.5)

Можна вважати при цьому, якщо ступеня багаточленів и  більше нуля, що ступінь  менше ступеня  , А ступінь  менше ступеня .

Доведення засноване на рівності (2.4). Якщо врахуємо, що  , І покладемо ,  , То передостаннє з рівності (2.4) дасть:

.

Підставляючи сюди вираз  через и  з попереднього рівності (2.4), отримаємо:

,

де ,  . Продовжуючи підніматися вгору по равенствам (2.4), прийдемо до доказуваному рівності (2.5).

Для доказу другого твердження теореми припустимо, що многочлени и  , Що задовольняють рівності (2.5), вже знайдені, але, наприклад, ступінь  більше або дорівнює ступеню  . ділимо  на :

,

де ступінь  менше ступеня  , І підставляємо це вираз в (2). Отримаємо рівність:

.

Ступінь множника, що стоїть при  , Вже менше ступеня  . Ступінь многочлена, що стоїть в квадратних дужках, буде в свою чергу менше ступеня  , Так як в противному випадку ступінь другого доданка лівій частині була б не менше ступеня  , А так як ступінь першого доданка менше ступеня цього твору, то вся ліва частина мала б ступінь, велику або рівну ступеня  , Тоді як многочлен  свідомо має, при наших припущеннях, меншу ступінь.

Теорема доведена.

Одночасно отримуємо, що якщо многочлени и  мають раціональні або дійсні коефіцієнти, то і многочлени и  , Що задовольняють рівності (2.5), можна підібрати так, що їх коефіцієнти будуть раціональними або, відповідно дійсними.

Застосовуючи доведену теорему до взаємно простим многочленів, отримуємо такий результат:

багаточлени и тоді і тільки тоді взаємно прості, якщо можна знайти многочлени и  , Що задовольняють рівності

 . (2.6)

Спираючись на цей результат, можна довести кілька простих, але важливих теорем про взаємно простих многочленів:

Теорема 1.якщо многочлен  взаємно простий з кожним з многочленів и  , То він взаємно простий і з їх твором.

Доведення. Справді, існують, по (2.6), такі многочлени и  , що .

Помноживши цю рівність на  , Отримуємо:

,

звідки випливає, що кожен загальний дільник и  був би дільником і для  ; проте за умовою .

Теорема 2.якщо проізведеніемногочленов и  ділиться на  , але и  взаємно прості, то  ділиться на .

Доведення. Помноживши рівність  на  , Отримаємо: .

Обидва доданків лівої частини цієї рівності діляться на  ; на нього ділиться, отже, і .

Теорема 3. якщо многочлен  ділиться на кожен з многочленів и  , Які між собою взаємно прості, то  ділиться і на їх твір.

Доведення. дійсно,  , Так що твір, що стоїть праворуч, ділиться на  . Тому, за теоремою 2,  ділиться на ,  , звідки .

Визначення найбільшого загального дільника може бути поширений на випадок будь-якої кінцевої системи многочленів: найбільшим спільним дільником многочленів називається такий спільний дільник цих многочленів, який ділиться на будь-який інший загальний дільник цих многочленів. Існування найбільшого загального дільника для будь-якої кінцевої системи многочленів випливає з наступної теореми, що дає також спосіб його обчислення.

Теорема. Найбільший спільний дільник многочленів  дорівнює найбільшому загальному дільнику многочлена  і найбільшого загального дільника многочленів .

Доведення. Справді, при  теорема очевидна. Приймемо тому, що для випадку  вона справедлива, тобто, зокрема, вже доведено існування найбільшого загального дільника  многочленів  . позначимо через  найбільший спільний дільник многочленів и  . Він буде спільним дільником для всіх заданих многочленів. З іншого боку, будь-який інший загальний дільник цих многочленів буде дільником також і для  , А тому і для .

Зокрема, система многочленів  називається взаємно простий, Якщо загальними делителями цих многочленів є лише багаточлени нульової ступеня, тобто якщо їх найбільший спільний дільник дорівнює 1. Якщо  , То попарно ці многочлени можуть і не бути взаємно простими.




 Найбільший спільний дільник многочленів |  кратні коріння

 багаточлени |  Подільність многочленів. властивості подільності |  Розподіл многочленів із залишком |  Похідна від многочлена |  кратні множники |  Виділення кратних множників |

© um.co.ua - учбові матеріали та реферати