'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

Исполним алгоритм для M=18, N=12 нет 6 6 6?12(да) да 12 6 да 12 18 M?N M?N N M 18?12(нет) На экране: М=6


Слайд 5

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


Слайд 6

Заполняем массив А: 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;


Слайд 7

Находим НОДы для двух соседних элементов 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); { печатаем массив В} Часть программы из предыдущей задачи


Слайд 8

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


Слайд 9

Найдем два соседних элемента массива 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. {Конец всей программы}


Слайд 10

Результаты работы программы: 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 Пары элементов с максимальными НОДами


Слайд 11

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


Слайд 12

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


Слайд 13

program NOK; var n,m:integer; i,k:integer; begin write('введите N: '); readln(n); write('введите M: '); readln(m); if (m<>0) and (n<>0) 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.


×

HTML:





Ссылка: