Задача: даны два числа, найти их наибольший общий делитель. - презентация

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

2 Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. НОД(a, b)= НОД(a-b, b)= НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) = =НОД(9,9)=9 Пример :

3 Алгоритм Евклида: Ввести N,M Пока NM повторять Если N>M то N=N-M иначе M=N-M Конец цикла Вывести М НАЧАЛО ввод: N,M N=N-M данет M N конец вывод: M M=M-N MN

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

5 Исполним алгоритм для M=18, N=12 нет66 612(да)да126 да1218 MN NM 1812(нет) НАЧАЛО ввод: N,M N=N-M данет M N конец вывод: M M=M-N MN На экране: М=6

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

7 Заполняем массив А: 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 { до предпоследнего элемента } n:=a[i]; m:=a[i+1]; { вводим обозначения элементов} while mn 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 then max:=b[i]; writeln; write('максимальный из НОДов двух соседних элементов=', max)

10 Найдем два соседних элемента массива 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 чисел – это к} { это числа их 9} {первое число 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 и N следует понимать как минимальное число делящееся без остатка одновременно на M и на N. Для решения задачи нам помогут следующие закономерности: 1. Произведение двух чисел M и N будет кратно обоим числам. 2. Если одно из чисел равно нулю, то наименьшее общее кратное найти нельзя, т.к. на ноль делить нельзя.

13 План решения задачи 1. Проверим не равно ли одно из чисел нулю. Если равно, то решения нет. 2. Примем произведение чисел за наименьшее общее кратное. 3. В цикле от произведения чисел до 1 проверяем равенство остатка от деления ключа цикла на первое число и на второе. Если остатки равны нулю – принимаем данный ключ цикла за наименьшее кратное и продолжаем цикл.

14 program NOK; var n,m:integer; i,k:integer; begin write('введите N: '); readln(n); write('введите M: '); readln(m); if (m0) and (n0) then begin k:=n*m; i:=k; while i>0 do begin if (i mod n=0) and (i mod m=0) then k:=i; i:=i-1; end; writeln('НОК ',m,' и ',n,' равно ',k) end else writeln(на ноль делить нельзя); end.