Düğümleri bulmak için Öklid algoritması dersinin özeti ve sunumu. "Öklid algoritması" konulu sunum Konu: Öklid'in GCD bulma algoritması

Sunumların önizlemesini kullanmak için bir Google hesabı (hesap) oluşturun ve oturum açın: https://accounts.google.com

Slayt başlıkları:

Öklid'in Algoritması Öklid, antik Yunan matematikçisi. 3. yüzyılda İskenderiye'de çalıştı. M.Ö e. Ana çalışma "Başlangıçlar" (15 kitap), eski matematiğin temellerini, temel geometriyi, sayı teorisini, genel ilişkiler teorisini ve limit teorisinin unsurlarını içeren alanları ve hacimleri belirleme yöntemini içerir. Matematiğin gelişiminde büyük etkisi oldu. Astronomi, optik, müzik teorisi üzerine çalışır. Öklid (MÖ 365-300)

EUCLID'İN ALGORİTMASI Euclid'in algoritması, negatif olmayan iki tamsayının en büyük ortak bölenini (gcd) bulmak için bir algoritmadır. Öklid (MÖ 365-300) Antik Yunan matematikçiler bu algoritmaya ἀνθυφαίρεσις veya ἀνταναίρεσις - "karşılıklı çıkarma" adını verdiler.

Hesaplama OBEB OBEB = iki doğal sayının en büyük ortak böleni, her iki orijinal sayının da kalansız bölünebildiği en büyük sayıdır. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Eşit olana kadar iki sayıdan büyük olanı büyük ve küçük arasındaki farkla değiştirin. Bu NOD'dur. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Örnek:

ADIM Çalışma M N Koşul 1 Giriş M 48 2 Giriş N 18 3 M  N 48 18, evet 4 M>N 48>18, evet 5 M:=M-N 30 6 M  N 30  18, evet 7 M>N 30 >18, evet 8 E:=E-H 12 9 E  H 12 18, evet 10 E>H 12 >18, hayır 11 K:=N-E 6 12 E  H 12  6, evet 13 E>H 12 >6 , evet 14 M:=M-N 6 15 M  N 6  6, hayır 16 Çıkış M

program Evklid ; var m, n: tamsayı; start writeln("vved 2 chisla"); readln(m,n); while mn başlarsa m>n ise m:=m-n başka n:= n-m ; son; write("nod=",m); son oku.

0.Bilgisayarda Evklid programını çalıştırın. M=32, N=24 ile test edin; M=696, N=234. 1 . Verilen iki sayının aralarında asal olup olmadığını kontrol edin. Not. En büyük ortak böleni 1,2 ise iki sayının aralarında asal olduğu söylenir. LCM(n, m) = n * m / gcd(n, m) ise n ve m sayılarının en küçük ortak katını (LCM) bulun. 3. Doğal sayılar m ve n verilmiştir. p / q = m / n olacak şekilde ortak bölenleri olmayan p ve q doğal sayılarını bulun. 4. Üç sayının GCD'sini bulun. Not. OBEB(a , b , c)= OBEB(gcd(a , b), c) Görevler

Ön izleme:

Konu: "Öklid Algoritması"

Dersin Hedefleri:

1. eğitici:

1. iki ve üç sayının gcd'sini bulmak için Öklid algoritmasını nasıl kullanacağınızı öğrenin
2. "Dallanma" ve "Döngü" algoritmik yapılarını kullanma becerilerini pekiştirmek
3. Pascal programlama dilinde program yazma ve hata ayıklama konusunda deneyim kazanmak

1. eğitici:

1. yeni materyal çalışmasında bağımsızlık ve sorumluluk oluşumu

1. geliştirme:

1. dikkat ve analitik düşüncenin gelişimi

Ders planı:

1. zaman düzenleme
2. Bilgi güncellemesi
3. Yeni konunun açıklaması
4. pratik kısım
5. Dersi özetlemek
6. Ödev.

zaman düzenleme

Selamlar. Kim yok. Sayı. Ders konusu. Ev ödevi ile ilgili sorular.

Bilgi güncellemesi.

Sorular:

Ne tür algoritmik yapılar biliyorsunuz?

Doğrusal yapı nedir? (Bl-ş)

dallanma yapısı nedir? (Bl-ş)

döngüsel yapı nedir? (Bl-ş)

Ne tür döngüler biliyorsun?

Pascal programlama dilinde bilinen sayıda tekrarlı bir döngü nasıl uygulanır?

Pascal programlama dilinde bilinmeyen sayıda tekrarlı bir döngü nasıl uygulanır?

Yeni konu anlatımı (sunu)

Öklid Hakkında;

Öklid'in algoritması fikri

Bu algoritmanın fikri şunlara dayanmaktadır:

1. M>N ise, OBEB(M, N) = OBEB(M - N, N) özelliği.

Başka bir deyişle, iki doğal sayının gcd'si, pozitif farklarının (farklarının modülü) gcd'sine ve daha küçük sayıya eşittir.

Kanıt: K, M ve N'nin (M > N) ortak böleni olsun. Bu, M \u003d mK, N \u003d nK, burada m, n doğal sayılar ve m > n anlamına gelir. O zaman M - N \u003d K (m - n), bu da K'nin M - N sayısının bir böleni olduğu anlamına gelir. Bu nedenle, M ve N sayılarının tüm ortak bölenleri, en büyük dahil olmak üzere M - N farklarının bölenleridir. ortak bölen

2. İkinci bariz özellik:

OBEB(M, M) = M.

"Manuel" sayma için Euclid'in algoritması şöyle görünür:

1) sayılar eşitse, herhangi birini cevap olarak alın, aksi takdirde algoritmaya devam edin;

2) büyük sayıyı sayıların büyüğü ve küçüğü arasındaki farkla değiştirin;

3) 1. paragrafın uygulanmasına dönüş.

Öklid algoritmasının blok şeması

JS Pascal'da Program

Evklid programı;

var m, n: tamsayı;

başlamak

writeln("vved 2 sayı");

readln(m,n);

mn yaparken

Başlamak

m>n ise

Sonra m:=m-n

Başka n:=n-m;

son;

Write("nod=",m);

okumak

son.

pratik kısım

Sorular ve görevler:

1. Evklid programını bilgisayarınızda çalıştırın. M=32, N=24 üzerinde test edin; M = 696, N = 234.
2. Verilen iki sayının aralarında asal olup olmadığını kontrol edin. Not. En büyük ortak böleni 1 olan iki sayının asal olduğu söylenir.

Dersi özetlemek

Bugün, negatif olmayan iki tamsayının GCD'sini bulmamızı sağlayan Öklid algoritması ile tanıştığımız derste, bu algoritmayı uygulayan Pascal programlama dilinde bir program yazdık. Evde, üç sayının GCD'sini ve iki sayının LCM'sini bulmak için bu algoritmayı uygulayacağınız bir görev alacaksınız.

Ödev.

1. Aşağıdaki formülü kullanarak üç sayının en büyük ortak bölenini bulan bir program yazın:

gcd(A, B, C) = gcd(gcd(A, B), C)

2. Aşağıdaki formülü kullanarak iki sayının en küçük ortak katını (LCM) bulan bir program yazın:

A  B \u003d GCD (A, B)  LCM (A, B)

slayt 1

slayt 2

slayt 3

slayt 4

slayt 5

slayt 6

Slayt 7

slayt 2

Euclid'in algoritması, negatif olmayan iki tam sayının en büyük ortak bölenini (gcd) bulmak için bir algoritmadır. Öklid (MÖ 365-300) Antik Yunan matematikçiler bu algoritmaya ἀνθυφαίρεσις veya ἀνταναίρεσις - "karşılıklı çıkarma" adını verdiler.

slayt 3

GCD hesaplaması

OBEB = iki doğal sayının en büyük ortak böleni, her iki orijinal sayının da kalansız bölünebildiği en büyük sayıdır. OBEB(a,b)= OBEB(a-b, b)= OBEB(a, b-a) İki sayıdan büyük olanı, eşit olana kadar büyük ve küçük sayıların farkıyla değiştirin. Bu NOD'dur. OBEB (18, 45)= OBEB (18, 45-18)= OBEB (18, 27)= OBEB (18, 9)= = OBEB(9,9)=9 Örnek:

slayt 4

slayt 5

Evklid programı; var m, n: tamsayı; start writeln("vved 2 sayı"); readln(m,n); mn ise m>n ise başlar, o zaman m:=m-n başka n:=n-m; son; write("nod=",m); son oku.

slayt 6

0.Bilgisayarda Evklid programını çalıştırın. M=32, N=24 ile test edin; M=696, N=234. 1. Verilen iki sayının aralarında asal olup olmadığını kontrol edin. Not. En büyük ortak böleni 1 olan iki sayıya asal denir. 2. Eğer LCM(n, m) = n * m / gcd(n, m) ise n ve m sayılarının en küçük ortak katını (LCM) bulun. 3. m ve n doğal sayıları verilmiştir. p / q = m / n olacak şekilde ortak bölenleri olmayan p ve q doğal sayılarını bulun. 4. Üç sayının GCD'sini bulun. Not. gcd(a, b, c)= gcd(gcd(a, b), c) Görevler

Slayt 7

Öklid, antik Yunan matematikçisi. 3. yüzyılda İskenderiye'de çalıştı. M.Ö e. Ana çalışma "Başlangıçlar" (15 kitap), eski matematiğin temellerini, temel geometriyi, sayı teorisini, genel ilişkiler teorisini ve limit teorisinin unsurlarını içeren alanları ve hacimleri belirleme yöntemini içerir. Matematiğin gelişiminde büyük etkisi oldu. Astronomi, optik, müzik teorisi üzerine çalışır.

Tüm slaytları görüntüle

Problemin Açıklaması Aşağıdaki problemi ele alalım: iki doğal sayının en büyük ortak bölenini (GCD) bulan bir program yazmak gerekiyor. Matematiği hatırlayalım. İki doğal sayının en büyük ortak böleni, eşit olarak bölünebildiği en büyük doğal sayıdır. Örneğin, 12 ve 18 sayılarının ortak bölenleri vardır: 2, 3, 6. En büyük ortak bölen 6 sayısıdır. Bu şu şekilde yazılır: gcd(12,18) = 6. Başlangıç ​​verilerini M ve N olarak gösteriniz. Problem ifadesi aşağıdaki gibidir: Verilen: M, N Bul: OBEB(M, N).

N, sonra OBEB(M,N) = OBEB(M - N,N). Başka bir deyişle, iki doğal sayının gcd'si, pozitif farkının gcd'sine ve daha küçük olan sayıya eşittir." title="(!LANG:Algoritma fikri Bu algoritmanın fikri, özellik M>N ise, gcd(M,N) = gcd( M - N, N) Diğer bir deyişle, iki doğal sayının gcd'si, pozitif farkının gcd'sine ve daha küçük sayıya eşittir." class="link_thumb"> 4 !} Algoritma fikri Bu algoritmanın fikri, M>N ise OBEB(M,N) = OBEB(M - N,N) özelliğine dayanmaktadır. Başka bir deyişle, iki doğal sayının gcd'si, pozitif farklarının gcd'sine ve daha küçük sayıya eşittir. N, sonra OBEB(M,N) = OBEB(M - N,N). Başka bir deyişle, iki doğal sayının gcd'si, pozitif farklarının gcd'sine ve daha küçük sayıya eşittir."> N, sonra gcd(M,N) = gcd(M - N,N). Başka bir deyişle, iki doğal sayının gcd'si, pozitif farklarının ve daha küçük sayılarının gcd'sine eşittir."> N, ardından OBEB(M,N) = OBEB(M - N,N). Başka bir deyişle, iki doğal sayının gcd'si, pozitif farkının gcd'sine ve daha küçük olan sayıya eşittir." title="(!LANG:Algoritma fikri Bu algoritmanın fikri, özellik M>N ise, gcd(M,N) = gcd( M - N, N) Diğer bir deyişle, iki doğal sayının gcd'si, pozitif farkının gcd'sine ve daha küçük sayıya eşittir."> title="Algoritma fikri Bu algoritmanın fikri, M>N ise OBEB(M,N) = OBEB(M - N,N) özelliğine dayanmaktadır. Başka bir deyişle, iki doğal sayının gcd'si, pozitif farklarının gcd'sine ve daha küçük sayıya eşittir."> !}

N). Bu, M = mK, N = pK, burada m, n doğal sayılar ve m>n anlamına gelir. O zaman M - N = K(m - n), buradan K'nin M - N'nin bir böleni olduğu sonucu çıkar. Dolayısıyla, M ve N'nin tüm ortak bölenleri bölendir" title="(!LANG:İspat K bir ortak olsun M ve N'nin böleni (M > N).Bu, M = mK, N = pK anlamına gelir, burada m, n doğal sayılardır ve m> n Sonra M - N = K(m - n), buradan K, M - N sayısının bir bölenidir. Dolayısıyla, M ve N sayılarının tüm ortak bölenleri bölendir." class="link_thumb"> 5 !}İspat K, M ve'nin ortak böleni olsun. N (M>N). Bu, M = mK, N = pK, burada m, n doğal sayılar ve m>n anlamına gelir. O zaman M - N = K(m - n), buradan K'nin M - N sayısının bir böleni olduğu çıkar. Dolayısıyla, M ve N sayılarının tüm ortak bölenleri, en büyük dahil M - N farklarının bölenleridir. ortak bölen Dolayısıyla: OBEB(M,N) = OBEB(M - N,N). İkinci belirgin özellik: OBEB(M,M) = M. N). Bu, M = mK, N = pK, burada m, n doğal sayılar ve m>n anlamına gelir. O zaman M - N \u003d K (m - n), bundan dolayı K'nin M - N sayısının bir böleni olduğunu takip eder. Bu nedenle, M ve N sayılarının tüm ortak bölenleri bölenlerdir "\u003e N). Bu, şu anlama gelir: M \u003d mK, N \u003d pK , burada m, n doğal sayılardır ve m > n O zaman M - N = K(m - n), buradan K'nin M - N sayısının bir böleni olduğu anlaşılır. Dolayısıyla, M ve N sayılarının tüm ortak bölenleri, en büyük ortak bölen de dahil olmak üzere, M-N farklarının bölenleridir.Dolayısıyla: OBEB(M, N) = OBEB(M - N, N).İkinci bariz özellik: OBEB(M , M) = M."> N). Bu, M = mK, N = pK, burada m, n doğal sayılar ve m>n anlamına gelir. O zaman M - N = K(m - n), buradan K'nin M - N'nin bir böleni olduğu sonucu çıkar. Dolayısıyla, M ve N'nin tüm ortak bölenleri bölendir" title="(!LANG:İspat K bir ortak olsun M ve N'nin böleni (M > N).Bu, M = mK, N = pK anlamına gelir, burada m, n doğal sayılardır ve m> n Sonra M - N = K(m - n), buradan K, M - N sayısının bir bölenidir. Dolayısıyla, M ve N sayılarının tüm ortak bölenleri bölendir."> title="İspat K, M ve'nin ortak böleni olsun. N (M>N). Bu, M = mK, N = pK, burada m, n doğal sayılar ve m>n anlamına gelir. Sonra M - N \u003d K (m - n), bu da K'nin M - N sayısının bir böleni olduğu anlamına gelir. Dolayısıyla, M ve N sayılarının tüm ortak bölenleri bölendir."> !}

Pascal Programı Evklid'de Program; var M, N: tamsayı; start writeln("M ve N giriniz"); readln(M,N); MN başlarken M>N ise M:=M-N yoksa N:=N-M biter; write("HOD=",M) sonu. N sonra M:=M-N başka N:=N-M sonu; write("HOD=",M) end."> N sonra M:=M-N başka N:=N-M bitiş; write("HOD=",M) bitiş."> N sonra M:=M-N başka N:=N-M son; write("HOD=",M) end." title="(!LANG:Pascal Program Evklid; var M, N: tamsayı; start writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N sonra M:=M-N başka N:=N-M sonu; write("HOD=",M) end." title="(!LANG:Pascal Program Evklid; var M, N: tamsayı; start writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}