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


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

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


Slide 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.


Slide 4

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


Slide 5

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


Slide 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;


Slide 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); { печатаем массив В} Часть программы из предыдущей задачи


Slide 8

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


Slide 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. {Конец всей программы}


Slide 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 Пары элементов с максимальными НОДами


Slide 11

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


Slide 12

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


Slide 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:





Ссылка: