Daire Öklid algoritmasının işgali için sunum. "Öklid'in algoritması" konulu sunum. Öklid'in algoritması fikri

Sınıf: 6

Dersin Hedefleri:

• çarpanlara ayırma kullanarak en büyük ortak böleni bulmak için algoritmayı düzeltin;
• ilgili tanım ve kavramları tekrar eder;
• öğrencilere Öklid algoritmasını tanıtmak;
• matematik kültürünün becerilerini oluşturmak için

Ekipman: bilgisayar, projektör, ekran.

Dersler sırasında

1. Düzenleme anı (öğrencilerin derse hazır olup olmadığını kontrol etme, yok işaretleme) (1 dk)

2. Sözlü çalışma: (6 dk)

1. Ürünü bir derece ile değiştirin:

d) a * a * a * a * a

1. Hesapla: 2 3 ; 52; 3 3 ; 10 4 .
2. (3?3?5?11): (3?11) ifadesinin değerini bulun. Hangi sonuca varılabilir?
3. Bölmeyi gerçekleştir aüzerinde b a=170 ise, b=35. A'ya eşit olan eşitliği yazın.

Bu eşitliği genel formda yazın: a bölünebilir ve b bir bölen olacaktır. Bölüm q ve kalan r olsun, o zaman: a = bq + r , ve q bir doğal sayı veya sıfır olabilir. r herhangi bir sayı olabilir mi? [ r bir doğal sayıdır ve 0 < r < b .] r = 0 ise a ve b sayıları hakkında ne söylenebilir? Tamsayılı bölme, kalanlı bölme işleminin özel bir durumudur.

4. Aşağıdaki durumlarda a sayısının b sayısına kalansız bölünüp bölünemeyeceğini öğrenin ve açıklayın:

a) a = 2 3 * 3 * 5 * 7;

b) a \u003d 2 4 * 3 * 5 7;

b = 2 7 * 3 * 5 4

c) a \u003d 2 * 3 4 * 5 * 13;

b = 2 * 3 3 * 5 * 11.

3. Temel bilgilerin güncellenmesi(10 dakika)

1) Sorular:

sayı bölen nedir a ?

Asal sayı nedir?

Bir sayıyı asal çarpanlara ayırmak ne demektir?

2, 3, 5, 9,10 ile bölünebilme işaretlerini formüle edin;

Tek basamaklı bir bileşik sayıya bir örnek verin;

77 sayısının asal sayı olduğu doğru mu?

Neden bir sayı 2 asal çarpana, diğeri 3 asal çarpana ayrılabiliyorsa, bu sayılar eşit değil mi?

Hangi sayı, asal veya bileşik, iki asal sayının çarpımıdır?

İki veya daha fazla sayının en büyük ortak böleni nedir?

Hangi sayılara asal denir?

OBEB'i bulmanın tekrar yolları: Doğal sayıların OBEB'ini bulmak için çeşitli algoritmalar vardır.

1 yol:İki sayı verilmişse ve bunlar nispeten küçükse, en iyi algoritma kaba kuvvet aramasıdır. Ancak, büyük sayılar için, sayıların tüm bölenlerini listeleyerek gcd(a;b) öğesini bulun. a ve b Süreç zahmetli ve güvenilmez.

Herhangi bir sayıdaki sayının gcd'sinin en küçüğünü geçmediğini hatırlamakta fayda var.

2 yol: sayıları çarpanlarına ayırarak (en yaygın) (Ek, slayt1)

2) 24 ve 16 sayılarının GCD'sini hesaplayın.

3) 875 ve 8000 sayılarını çarpanlarına ayırın ve bu sayıların EBOB'unu hesaplayın.

(Örnek olarak 8000 sayısını kullanarak, sıfırlarla biten daha basit bir çarpanlara ayırma yöntemini tekrarlayın: 10=2 *5 olduğundan, 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6*5 3)

4) Çarpımları 3000'e eşitse, üç sayının EBOB'u 15'e eşit olabilir mi? [ Numara, gibi

15 \u003d 3 * 5, bu, 3 sayısının üç sayının her birinin genişlemesine dahil edilmesi gerektiği anlamına gelir. Ancak 3000 = 2 3 * 3 * 5 3 .]

5) P görevi ye"Sınıfa ders kitapları getirildi: 24 matematik, 36 tarih ve 48 coğrafya. Her biri aynı sayıda matematik, tarih ve coğrafya kitabı içerecek şekilde bu kitaplardan yapılabilecek en fazla set sayısı nedir? Her sette kaç kitap olacak?"

4. Doğrulama çalışması (Ek, slayt 2) (6 dk)

5. Yeni materyal öğrenmek (10 dk)

Öğretmen: OBEB(a, b) bulma yöntemi basit, anlaşılır ve kullanışlıdır, ancak önemli bir dezavantajı vardır: eğer verilen sayılar büyükse ve hatta çok kolay çarpanlara ayrılmıyorsa, o zaman OBEB(a, b) bulma görevi oldukça zor hale gelir. Ek olarak, çok çalıştıktan sonra, OBEB(a, b) = 1 olduğundan emin olacağız ve görünen o ki tüm çalışmalar boşuna yapılmış gibi görünüyor.

Euclid, sayılara herhangi bir ön işlem yapmadan gcd(a, b) bulmanın harika bir yolunu buldu. (Ek, slayt 3 ve 4) Daha sonra, bu algoritma olarak bilinir hale geldi. Öklid'in algoritması)

Öklid algoritmasını tanıyalım. gcd(102;84) bulunması istensin. Bir sayıyı diğerine bölün ve kalanı bulun.

Şimdi aynı işlemi 84 ve 18 sayıları için yapalım:

Bir sonraki adım 18 ve 12 içindir:

Şimdi - 12 ve 6 için:

0-kalıntı. Süreç sona erdi.

Bu süreç sonsuz olamaz, çünkü artıklar azalır, kalanlar azalır. Kümesi bilindiği gibi aşağıdan sınırlanan negatif olmayan tam sayılar:

84 >18 > 12> 6 >0

Yazılı eşitliklere yakından bakarsanız, tüm sayı çiftlerinin GCD'lerinin birbirine eşit olduğunu belirleyebilirsiniz (öğrencileri düşünmeye davet edin - neden?),

yani gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. Ama 6 sayısı 0 olmayan son kalandır. .

Gerçekten de, eğer c, a ve b sayılarının rastgele bir ortak böleni ise, o zaman r = a - bq, c'ye bölünebilir; ve bunun tersi, eğer c, b ve r'nin rastgele bir ortak böleni ise, o zaman a, c'ye bölünebilir. Yani, (a; b) ve (b; r) çiftlerinin tüm ortak bölenleri çakışır ve dolayısıyla onların en büyük ortak bölenleri de çakışır.

Öklid'in algoritmasının rahatlığı, gösterim biçimini bir tablo biçiminde uygularsak özellikle fark edilir hale gelir:

Bu tablette, işlem bitene kadar orijinal sayılar önce yazılarak, zihinde bölünerek kalanlar sağa, özel sayılar en alta yazılır. Son bölen GCD'dir.

Böylece, iki sayının en büyük ortak böleni, daha büyük bir sayıyı daha küçük bir sayıya bölerken 0'a eşit olmayan son kalandır, yani eğer a = b*q + r, sonra gcd(a; b) = gcd(b; r)

Bu işlem dizisine denir Öklid'in algoritması. Bu algoritma, sayıları çarpanlarına ayırmadan GCD'yi bulmanızı sağlar (Ek, slayt 5)

6. Alıştırmalar (10 dk)

1. Bir örnek düşünmeniz tavsiye edilir. 323 ve 437 sayılarının OBEB'ini bulmamız gereksin. Bu sayıların hiçbiri 2, 3, 5, 7, 11'in katı olmadığından, seçme veya asal çarpanlara ayırma yoluyla bunu yapmak kolay değildir. aşağıdaki gibi devam edin (

Konu: Öklid'in GCD'yi bulma algoritması.

Hedefler:Daha önce çalışılan En Büyük Ortak Bölen ve En Küçük Ortak Kat konularını tekrar edin, Öklid algoritmasını tanıtın.

Öğrenme hedefleri - en büyük ortak bölen ve en küçük ortak kat kavramlarını tekrarlamak, onları bulma kuralı. Euclid algoritmasına giriş. İlgili görevleri çözerek Euclid'in algoritmasını düzeltin.

Geliştirme görevleri - mantıksal düşünme, dikkat, konuşma hafızasının gelişimi, bağımsız olarak yeni bilgileri keşfetme yeteneği, matematiksel merak, konuya bilişsel ilgi.

Eğitimin görevleri, bir matematiksel düşünme, karşılıklı yardımlaşma, kendi kendini inceleme ve birinin hatalarını analiz etme kültürünü geliştirmektir.

Kartlar üzerinde çalışın

GCD veya LCM numaralarını bulun ve şu ifadeyi deşifre edin:

34

16

300

6

1

12

2

34

11

17

D: OBEB(33.88)

H: NOC(9.40)

C: NOK(14.42)

E: EBOB(48.18)

R: NOC(17.5)

C: EBOB(48.24)

K: OGD (72.12)

L: OBEB(20.14)

E: EBOB(30.18)

M: NOC(25.12)

T: NOC(4,8,16)

H: NOC(12.40)

B: EBOB(18.35)

A: OBEB(17.34)

ben: gcd(102.68)

E: EBOB(18,12)

Son tabloya kalan sayı çiftlerini yazın.

Yanıtlar:

34

16

300

6

1

12

2

34

11

17

ANCAK

L

G

Ö

R

Ve

T

M

E

AT

İle

L

Ve

D

ANCAK

D: OBEB(33.88)=11

G: LCM(9.40)=360

A: LCM(14.42)=42

E: OBEB(48,18)=6

P: LCM(17.5)=85

C: OBEB(48,24)=24

K: OBEB (72.12)=12

L: OBEB(20,14)=2

E: EBOB(30,18)=6

M: LCM(25,12)=300

T: LCM(4,8,16)=16

H: LCM(12.40)=120

B: gcd(18,35)=1

A: OBEB(17.34)=17

VE: OBEB(102.68)=34

E: EBOB(18,12)=6

2 kelime daha tahmin et

Son tablodaki sayılar hakkında ne söylenebilir? Onlar asaldır, yani. Bu sayıları asal çarpanlarına ayırırsak, aynı çarpanlara sahip olmayacaklardır. Bu tür sayıların GCD'si nasıl bulunur? Bu tür sayıların başı =1. Ve LCM nasıl bulunur, LCM'yi bulmak için bu sayıları birbiriyle çarpmanız gerekir.

İlk sütunda, biri diğerine tam olarak bölünemeyen sayı çiftleri bulunur. Onlar. kalan 0 değil.

Bu tür sayıların GCD ve LCM'sini nasıl buldunuz? (Bu sayıları asal çarpanlarına ayırarak)

LCM(12,40)=2 3 *3*5=120

GCD ve LCM bulma kuralını hatırlayın, LCM (a, c) \u003d (a * b) formülünü bulun ve kontrol edin: GCD (a, b)

3 *3*11=264

LCM (a, b) \u003d (a * b ): GCD (a, b )

264=(33*88):11=3*88=264

LCM(20,14)=2 2 *5*7=140

LCM (a, b) \u003d (a * b ): GCD (a, b )

140=(20*14):2=10*14=140

OBEB(12,40)=2 2 =4

LCM (a, b) \u003d (a * b ): GCD (a, b )

120=(12*40):4=3*4=120

Yeni bir konu keşfetmek:

Hangi sayı çiftlerinin GCD'si 6'dır?

6=gcd(48.18)=gcd(30.18)=gcd(12.18)

Ne fark ettin? 30'u nasıl aldın? 48-18

12'yi nasıl buldun? 30-18

a> b \u003d GCD (a-b, c) olduğunda

Onlar. OBEB (a, c) v> a = OBEB (a, c-a) olduğunda

Bu eşitliği kim devam ettirebilir?

6=gcd(48.18)=gcd(30.18)=gcd(12.18) = gcd(12.6)=gcd(6.6)=6

Euclid'in algoritması bu kurala dayanmaktadır.

Öklid'in algoritması- iki tane bulmak için verimli. Algoritma, onu ilk kez VII ve X kitaplarında "" tanımlayanın adını almıştır.

En basit haliyle, Euclid'in algoritması bir çift pozitif tamsayıya uygulanır ve daha küçük sayıdan oluşan ve daha büyük ve daha küçük sayı arasında yeni bir çift oluşturur. Sayılar eşit olana kadar işlem tekrarlanır. Bulunan sayı, orijinal çiftin en büyük ortak bölenidir.

Antik Yunan matematikçiler bu algoritmaya "karşılıklı çıkarma" adını verdiler.

Bu yöntemin özü şudur: büyük sayıdan küçük sayıyı sayılar eşit olana kadar çıkarın, büyük olanı farkla değiştirin. Bu olduğunda, GCD bulunur. (Tahtadaki örnek - 48 ve 18 sayıları)

İlk soru, bu sayılar eşit mi? Hayır, eşit değiller, bu yüzden büyük olan 48-18 = 30'dan küçüğü çıkarıyoruz. 30, 18'e eşit değil, yani 30-18= 12, 18-12=6, 12-6=6. Yani sayılar eşit olana kadar bu işlemleri yapıyoruz. Dolayısıyla gcd(48,18)=6

48 ve 18 numaralarının GCD'sini bilerek, NOC'yi bulun. LCM(48,18)=(48*18):6=48*3=144

Öklid'in algoritmasını kullanarak OBEB(102;68)'i bulalım.

Bulalım NOD (357;273)

Burada 84 sayısını 3 kez ve 21 sayısını üç kez çıkardık.

Çıkarma yapmadan, bir seride kaç çıkarma olacağını ve sonuç ne gibi bir fark olacağını nasıl öğrenebiliriz? Hangi davaların değerlendirilmesi gerekiyor? ( gösterge: bölmeyi hatırla.)

Genel kural şu ​​şekilde formüle edilebilir: eğer sayı a bölünemez b, daha sonra bölündüğünde kalanı ile değiştirilir b(ne zaman a< b bu kalan a); Eğer a bölü b, ardından bir sayı ile değiştirin b. Tam olarak aynı kural, bir permütasyon ile a ve b, için de geçerlidir b. daha büyük sayı bölmek küçüğe, sonra küçük olana ilk kalana, sonra ilk kalanı ikinci kalana ve bu şekilde, 0 elde edene kadar. Sonra0'a eşit olmayan son kalan GCD'dir .

GCD'yi (357;273) bulun.

357 273 273 84 84 21 OBEB (357; 273) = 21

273 1 252 3 21 4

84 21 0

357=1*273+84 273=3*84+21 84=4*21

gcd(357.273)=gcd(273.84)=gcd(84.21)=21

Öklid'in algoritmasının rahatlığı, gösterim biçimini bir tablo biçiminde uygularsak özellikle fark edilir hale gelir:

Bu tablette, işlem bitene kadar orijinal sayılar önce yazılarak, zihinde bölünerek, kalanlar sağda, özel sayılar en altta yazılır. Son bölen GCD'dir.

Böylece, iki sayının en büyük ortak böleni, büyük sayı küçük sayıya bölündüğünde sıfır olmayan son kalandır., yanieğer a = b *q + r, sonra gcd(a; b) = gcd(b; r)

Bu işlem dizisine denir Öklid'in algoritması.

1) Öklid algoritmasını kullanarak sayıların GCD'sini bulun:

A) 703, 481; B) 2112 ve 1680; B) 5075 ve 1450

OBEB(703;481)=37

EBOB(2112;1680)=48

EBOB(5075;1450)=

Sonuçları bir bilgisayarda kontrol edin.

Bilgisayardaki çocukların görevi, GCD ve LCM bulma programını kullanarak üç sayı için GCD ve LCM'yi bulmaktır.

gcd(150, ____) = ____

EBOB(450,315,135)=____

OBEB(135, ____) = ____

EBOB(2160,1350,1080)=____

OBEB (1080, ____) = ____

EBOB(530,3180,2120)=____

EBOB (2120, ____) = ____

(Üç veya daha fazla sayının OBEB'ini bulmak için önce herhangi ikisinin OBEB'ini, sonra bulunan bölenin OBEB'ini ve verilen üçüncü sayıyı bulun.

ve verilen üçüncü sayı.

7. Bilgisayarda sonuçları kontrol etme. Bağımsız problem çözme.

1) Sınıftaki öğrencilere de aynı hediyeler hazırlandı. Tüm hediyeler 120 çikolata, 280 tatlı ve 320 fındık içeriyordu. 30'dan fazla olduğu biliniyorsa birinci sınıfta kaç öğrenci vardır?

Cevap:________________________

2) İstasyonda üç yolcu treni var: ilk - 418 kompartıman vagonunda, ikinci - 494 ve üçüncü - 456. Aynı sayıda koltuk varsa, her trende kaç kompartıman vagonu var Her arabada ve toplam sayısı 20'den fazla mı? Cevap _________________________

3) 156 çay, 234 beyaz ve 390 kırmızı gülden buketler yapılmış ve her türden gül buketlerinin hepsinde eşit sayıda olup 50'den fazla gül buketi yapılmıştır. Bu güllerden kaç tane buket yapılmıştır? her türden gül bir buket içinde miydi? Cevap_________________

Dersin özeti. Derste GCD ve LCM'yi bulmanın hangi yolu ile tanıştık. Öklid'in algoritması. Bu yöntemin diğer adı nedir? (çıkarma yöntemi). Bu yöntem nasıl iyileştirildi? Bölme işleminde, büyük sayı küçük sayıya bölünür, sonra küçük sayı ilk kalana, ardından ilk kalan ikinci kalana bölünür ve bu şekilde 0 elde edilene kadar devam edilir. Sıfır olmayan son kalan, OBEB'dir. sayılar.

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 aralarında 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)

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 sayıya eşittir." title="(!LANG:Algoritma fikri Bu algoritmanın fikri, 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, 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), bu da K'nin M - N'nin bir böleni olduğu anlamına gelir. Dolayısıyla, M ve N'nin tüm ortak bölenleri bölendir" title="(!LANG:Kanıt K bir ortak bölen olsun M ve. 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, M - N farklarının bölenleridir, en büyüğü de dahil. 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ölenidir. Dolayısıyla, 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), bu da K'nin M - N'nin bir böleni olduğu anlamına gelir. Dolayısıyla, M ve N'nin tüm ortak bölenleri bölendir" title="(!LANG:Kanıt K bir ortak bölen olsun M ve. 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."> !}

slayt 1

slayt 2

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.

slayt 3

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:

slayt 4

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 M:= E-H 12 9 E H 12 18 evet 10 E>H 12>18 hayır 11 N:=N-E 6 12 E H 12 6 evet 13 E>H 12>6 evet 14 E:=E-H 6 15 E H 6 6 hayır 16 SonuçM

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 ise iki sayıya görece asal denir. 2. 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. Verilen m ve n doğal sayıları. 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.