Задача: даны два числа, найти их наибольший общий делитель

Содержание

Слайд 2

Вычисление НОД

НОД = наибольший общий делитель двух натуральных чисел – это наибольшее

Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это
число, на которое оба исходных числа делятся без остатка.

НОД(a, b)= НОД(a-b, b)= НОД(a, b-a)

Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.

НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) = =НОД(9,9)=9

Пример :

Слайд 3

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

Ввести N,M
Пока N≠M повторять
Если N>M то N=N-M иначе M=N-M
Конец цикла
Вывести М

Алгоритм Евклида: Ввести N,M Пока N≠M повторять Если N>M то N=N-M иначе

Слайд 4

program Evklid;
var m, n: integer;
begin
write(‘введите 2 числа');
read(m,n);
while m<>n do
begin
if

program Evklid; var m, n: integer; begin write(‘введите 2 числа'); read(m,n); while
m>n
then m:=m-n
else n:=n-m;
end;
write (‘НОД=',m);
end.

Слайд 5

Исполним алгоритм для M=18, N=12

нет

6

6

6≤12(да)

да

12

6

да

12

18

M≤N

M≠N

N

M

18≤12(нет)

На экране: М=6

Исполним алгоритм для M=18, N=12 нет 6 6 6≤12(да) да 12 6

Слайд 6

33. Дано n целых чисел. Найти среди них пару чисел, для которых

33. Дано n целых чисел. Найти среди них пару чисел, для которых
наибольший общий делитель имеет максимальное значение.

План решения задачи:
Заполнить массив А, ввести с клавиатуры количество чисел в массиве – k
Найти НОДы для соседних элементов, обозначим их m, поместить их в массив В.
Найти максимальное среди элементов массива В max.
Найти два соседних элемента массива A, для которых соответствующий элемент в В = max

Слайд 7

Заполняем массив А:

program a1;
var i,m,n,k,max:integer;
a,b:array[1..10] of integer;
begin
read(k); {количество

Заполняем массив А: program a1; var i,m,n,k,max:integer; a,b:array[1..10] of integer; begin read(k);
чисел в массиве}
for i:=1 to k do begin
a[i]:=random(100); write(a[i]:3)end;

Слайд 8

Находим НОДы для двух соседних элементов

for i:=1 to k-1 do begin {

Находим НОДы для двух соседних элементов for i:=1 to k-1 do begin
до предпоследнего элемента }
n:=a[i]; m:=a[i+1];{ вводим обозначения элементов}
while m<>n do
begin
if m>n
then m:=m-n
else n:=n-m;
end;
b[i]:=m; {помещаем найденный НОД в массив В}
end; writeln;
for i:=1 to k-1 do write(b[i]:3); { печатаем массив В}

Часть программы из предыдущей задачи

Слайд 9

Находим максимальный элемент в массиве В

max:=b[1];
for i:=1 to k-1 do if b[i]>max

Находим максимальный элемент в массиве В max:=b[1]; for i:=1 to k-1 do
then max:=b[i];
writeln; write('максимальный из НОДов двух соседних элементов=', max)

Слайд 10

Найдем два соседних элемента массива A (a[i] и a[i+1]), для которых соответствующий

Найдем два соседних элемента массива A (a[i] и a[i+1]), для которых соответствующий
элемент в В = max

For i:=1 to k-1 do
If b[i]=max then writeln (‘a[‘,i,’]=‘,a[i],’a[‘,i+1,’]=‘,a[i+1])
end. {Конец всей программы}

Слайд 11

Результаты работы программы:

9 { возьмем 9 чисел – это к}
66

Результаты работы программы: 9 { возьмем 9 чисел – это к} 66
18 51 84 57 42 48 54 96 { это числа их 9}
6 3 3 3 3 6 6 6 {первое число 6 – это НОД для чисел 66 и 18}
максимальный из НОДов двух соседних элементов=6 { это максимальное из 2-ой строки}
a[1]=66 a[2]=18
a[6]=42 a[7]=48
a[7]=48 a[8]=54
a[8]=54 a[9]=96

Пары элементов с максимальными НОДами

Слайд 12

Задача: даны 2 числа найти наименьшее общее кратное.

Наименьшее кратное двух чисел M

Задача: даны 2 числа найти наименьшее общее кратное. Наименьшее кратное двух чисел
и N следует понимать как минимальное число делящееся без остатка одновременно на M и на N.
Для решения задачи нам помогут следующие закономерности:
1. Произведение двух чисел M и N будет кратно обоим числам.
2. Если одно из чисел равно нулю, то наименьшее общее кратное найти нельзя, т.к. на ноль делить нельзя.

Слайд 13

План решения задачи

1. Проверим не равно ли одно из чисел нулю. Если

План решения задачи 1. Проверим не равно ли одно из чисел нулю.
равно, то решения нет.
2. Примем произведение чисел за наименьшее общее кратное.
3. В цикле от произведения чисел до 1 проверяем равенство остатка от деления ключа цикла на первое число и на второе. Если остатки равны нулю – принимаем данный ключ цикла за наименьшее кратное и продолжаем цикл.
Имя файла: Задача:-даны-два-числа,-найти-их-наибольший-общий-делитель.pptx
Количество просмотров: 284
Количество скачиваний: 0