- Главная
- Информатика
- Алгоритм Евклида
Содержание
- 2. АЛГОРИТМ ЕВКЛИДА Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.
- 3. Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое
- 5. program Evklid; var m, n: integer; begin writeln ('vved 2 chisla'); readln (m,n); while m n
- 7. Скачать презентацию
Слайд 2
АЛГОРИТМ ЕВКЛИДА
Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД)
АЛГОРИТМ ЕВКЛИДА
Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД)
двух целых неотрицательных чисел.
Евклид
(365-300 до. н. э.)
Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание».
Слайд 3
Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это
Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это
наибольшее число, на которое оба исходных числа делятся без остатка.
НОД(a, b)= НОД(a-b, b)= НОД(a, b-a)
Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.
НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) = =НОД(9,9)=9
Пример :
Слайд 4
Слайд 5
program Evklid;
var m, n: integer;
begin
writeln ('vved 2 chisla');
readln (m,n);
while m<>n
program Evklid;
var m, n: integer;
begin
writeln ('vved 2 chisla');
readln (m,n);
while m<>n
do
begin
if m>n
then m:=m-n
else n:=n-m;
end;
write ('nod=',m);
readln
end.
begin
if m>n
then m:=m-n
else n:=n-m;
end;
write ('nod=',m);
readln
end.