Apskritimo Euklido algoritmo užimtumo pristatymas. Pristatymas tema "Euklido algoritmas". Euklido algoritmo idėja

Klasė: 6

Pamokos tikslai:

• nustatyti didžiausio bendro daliklio paieškos algoritmą naudojant faktorizaciją;
• kartoti susijusius apibrėžimus ir sąvokas;
• supažindinti mokinius su Euklido algoritmu;
• formuoti matematinės kultūros įgūdžius

Įranga: kompiuteris, projektorius, ekranas.

Per užsiėmimus

1. Organizavimo momentas (mokinių pasirengimo pamokai tikrinimas, pažyma, kad nėra) (1 min.)

2. Darbas žodžiu: (6 min.)

1. Pakeiskite gaminį laipsniu:

d) a * a * a * a * a

1. Apskaičiuokite: 2 3 ; 52; 3 3 ; 10 4 .
2. Raskite išraiškos reikšmę: (3?3?5?11): (3?11). Kokią išvadą galima padaryti?
3. Atlikite padalijimą a ant b jei a=170, b=35. Užrašykite lygybę, kas lygi a.

Parašykite šią lygybę bendra forma: a dalijasi, o b bus daliklis. Tegul koeficientas yra q, o liekana r, tada: a = bq + r , o q gali būti natūralusis skaičius arba nulis. Ar r gali būti bet koks skaičius? [r yra natūralusis skaičius, o 0 < r < b .] Ką galima pasakyti apie skaičius a ir b, jei r = 0? Sveikųjų skaičių padalijimas yra ypatingas padalijimo su liekana atvejis.

4. Išsiaiškinkite ir paaiškinkite, ar skaičius a dalijasi iš skaičiaus b be liekanos, jei:

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. Pagrindinių žinių atnaujinimas(10 minučių)

1) Klausimai:

Kas yra skaičių daliklis a ?

Kas yra pirminis skaičius?

Ką reiškia įtraukti skaičių į pirminius veiksnius?

Suformuluokite dalijimosi iš 2, 3, 5, 9,10 ženklus;

Pateikite vienženklio sudėtinio skaičiaus pavyzdį;

Ar tiesa, kad skaičius 77 yra pirminis skaičius?

Kodėl, jei vieną skaičių galima išskaidyti į 2 pirminius veiksnius, o kitą į 3 pirminius veiksnius, tai šie skaičiai nėra lygūs?

Kuris skaičius, pirminis ar sudėtinis, yra dviejų pirminių skaičių sandauga?

Koks yra didžiausias dviejų ar daugiau skaičių bendras daliklis?

Kokie skaičiai vadinami koprime?

Pakartokite būdus, kaip rasti GCD: Yra įvairių algoritmų, kaip rasti natūraliųjų skaičių GCD.

1 būdas: Jei pateikiami du skaičiai ir jie yra palyginti maži, tada geriausias algoritmas yra brute-force paieška. Tačiau dideliems skaičiams raskite gcd(a;b) išvardydami visus skaičių daliklius a ir b Procesas yra sunkus ir nepatikimas.

Naudinga atsiminti, kad bet kurio skaičių gcd neviršija mažiausio iš jų.

2 būdai: pagal faktoringo skaičius (dažniausiai) (priedas, 1 skaidrė)

2) Apskaičiuokite skaičių 24 ir 16 GCD.

3) Suskaičiuokite skaičius: 875 ir 8000 ir apskaičiuokite šių skaičių GCD.

(Naudodami skaičių 8000 kaip pavyzdį, pakartokite paprastesnį skaičių, kurie baigiasi nuliais, faktoringo būdą: kadangi 10=2 *5, tada 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 * 5 3)

4) Ar trijų skaičių GCD gali būti lygus 15, jei jų sandauga lygi 3000? [ Nr, kaip

15 \u003d 3 * 5, o tai reiškia, kad skaičius 3 turi būti įtrauktas į kiekvieno iš trijų skaičių išplėtimą. Tačiau 3000 = 2 3 * 3 * 5 3 .]

5) P valgyk užduotį„Į klasę buvo atnešti vadovėliai: matematikos – 24, istorijos – 36, geografijos – 48. Kokį daugiausiai rinkinių galima pagaminti iš šių knygų, kad kiekvienoje būtų tiek pat matematikos, istorijos ir geografijos knygų? Kiek knygų bus kiekviename rinkinyje?

4. Patikrinimo darbas (priedas, 2 skaidrė) (6 min.)

5. Naujos medžiagos mokymasis (10 min.)

Mokytojas: Ištirtas GCD(a, b) radimo būdas yra paprastas, suprantamas ir patogus, tačiau turi reikšmingą trūkumą: jei pateikti skaičiai yra dideli ir net nelabai lengvai faktorinuojami, tada užduotis rasti GCD(a, b) tampa gana sunku. Be to, gali pasirodyti, kad daug padirbėję įsitikinsime, kad GCD(a, b) = 1 ir atrodo, kad visas darbas atliktas veltui.

Euklidas rado nuostabų būdą rasti gcd(a, b) be išankstinio skaičių apdorojimo. (Priedas, 3 ir 4 skaidrės) Vėliau šis algoritmas tapo žinomas kaip Euklido algoritmas)

Susipažinkime su Euklido algoritmu. Tegul reikia rasti gcd(102;84). Padalinkite vieną skaičių iš kito ir raskite likutį.

Dabar atlikime tą pačią operaciją su skaičiais 84 ir 18:

Kitas žingsnis skirtas 18 ir 12 m.:

Dabar – 12 ir 6:

0-likutis. Procesas baigėsi.

Šis procesas negali būti begalinis, nes likučiai mažėja, lieka neneigiami sveikieji skaičiai, kurių aibė, kaip žinoma, apribota iš apačios:

84 >18 > 12> 6 >0

Jei atidžiai pažvelgsite į rašytines lygybes, galite nustatyti, kad visų skaičių porų GCD yra vienodos (pakvieskite mokinius pagalvoti - kodėl?),

y., gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. Tačiau skaičius 6 yra paskutinis ne 0 likutis .

Iš tiesų, jei c yra savavališkas bendras skaičių a ir b daliklis, tai r = a - bq dalijasi iš c; ir atvirkščiai, jei c yra savavališkas bendrasis b ir r daliklis, tai a dalijasi iš c. Tai reiškia, kad visi bendrieji porų (a; b) ir (b; r) dalikliai sutampa, taigi sutampa ir jų didžiausi bendrieji dalikliai.

Euklido algoritmo patogumas tampa ypač pastebimas, jei žymėjimo formą taikome lentelės pavidalu:

Šioje planšetėje pirmiausia užrašomi pirminiai skaičiai, dalinami mintyse, likučiai užrašomi dešinėje, o privatūs – apačioje, kol procesas baigiasi. Paskutinis daliklis yra GCD.

Taigi didžiausias bendras dviejų skaičių daliklis yra paskutinis, nelygus 0, likutis, kai didesnį skaičių dalija iš mažesnio, tai yra jei a = b*q + r, tada gcd(a; b) = gcd(b; r)

Ši operacijų seka vadinama Euklido algoritmas. Šis algoritmas leidžia rasti skaičių GCD jų neįvertinus (priedas, 5 skaidrė)

6. Pratimai (10 min.)

1. Patartina apsvarstyti pavyzdį. Tegul reikia rasti skaičių 323 ir 437 GCD. Tai nėra lengva padaryti parenkant arba išskaidant į pirminius veiksnius, nes nė vienas iš šių skaičių nėra 2, 3, 5, 7, 11 kartotinis. elkitės taip (

Tema: Euklido algoritmas ieškant GCD.

Tikslai:pakartokite anksčiau studijuotas temas Didžiausias bendras daliklis ir Mažiausias bendras kartotinis, pristatykite Euklido algoritmą.

Mokymosi tikslai – kartoti didžiausio bendrojo daliklio ir mažiausio bendro kartotinio sąvokas, jų radimo taisyklę. Įvadas į Euklido algoritmą. Pataisykite Euklido algoritmą spręsdami atitinkamas užduotis.

Ugdymo uždaviniai – loginio mąstymo, dėmesio, kalbos atminties, gebėjimo savarankiškai atrasti naujas žinias, matematinės smalsumo, pažintinio domėjimosi dalyku ugdymas.

Ugdymo uždaviniai – ugdyti matematinio mąstymo, savitarpio pagalbos, savęs tikrinimo ir klaidų analizės kultūrą.

Darbas su kortomis

Raskite GCD arba LCM numerius ir iššifruokite frazę:

34

16

300

6

1

12

2

34

11

17

D: GCD(33.88)

H: NOC(9,40)

A: NOK (14,42)

E: GCD(48.18)

R: NOC(17,5)

C: GCD(48.24)

K: GCD (72.12)

L: GCD(20.14)

E: GCD(30.18)

M: NOC(25.12)

T: NOC(4;8;16)

H: NOC(12,40)

B: GCD(18.35)

A: GCD(17.34)

Aš: gcd (102.68)

E: GCD(18,12)

Paskutinėje lentelėje užrašykite likusias skaičių poras

Atsakymai:

34

16

300

6

1

12

2

34

11

17

BET

L

G

O

R

Ir

T

M

E

AT

Į

L

Ir

D

BET

D: GCD(33.88)=11

G: LCM(9.40)=360

A: LCM(14.42)=42

E: GCD(48,18)=6

P: LCM(17,5)=85

C: GCD(48,24)=24

K: GCD (72,12) = 12

L: GCD(20,14)=2

E: GCD(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: GCD(17.34)=17

IR: GCD(102.68)=34

E: GCD(18,12)=6

Atspėk dar 2 žodžius

Ką galima pasakyti apie skaičius paskutinėje lentelėje? Jie yra koprime, t.y. jei šiuos skaičius išskaidysime į pirminius veiksnius, tada jie neturės tų pačių veiksnių. Kaip rasti tokių skaičių GCD? Tokių skaičių linktelėjimas =1. Ir kaip rasti LCM, norėdami rasti LCM, turite padauginti šiuos skaičius vieną iš kito.

Pirmajame stulpelyje yra skaičių poros, kuriose vienas iš jų visiškai nesidalina iš kito. Tie. likusi dalis nėra 0.

Kaip radote tokių skaičių GCD ir LCM? (Išskaidžius šiuos skaičius į pirminius veiksnius)

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

Prisiminkite GCD ir LCM radimo taisyklę, suraskite ir patikrinkite formulę LCM (a, c) \u003d (a * b): 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

GCD(12,40)=2 2 =4

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

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

Naujos temos tyrinėjimas:

Kokių skaičių porų GCD yra 6?

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

ką pastebėjai? Kaip gavai 30? 48-18

Kaip gavai 12? 30-18

Kai a> b \u003d GCD (a-b, c)

Tie. GCD (a, c) Kai v> a = GCD (a, c-a)

Kas gali tęsti šią lygybę?

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

Šia taisykle pagrįstas Euklido algoritmas.

Euklido algoritmas- efektyvus ieškant dviejų. Algoritmas pavadintas tuo, kas pirmą kartą jį aprašė VII ir X knygose "".

Paprasčiausiu atveju Euklido algoritmas taikomas teigiamų sveikųjų skaičių porai ir sukuria naują porą, kurią sudaro mažesnis skaičius ir tarp didesnio ir mažesnio skaičiaus. Procesas kartojamas tol, kol skaičiai bus lygūs. Rastas skaičius yra didžiausias bendras pradinės poros daliklis.

Senovės Graikijos matematikai šį algoritmą pavadino „abipusiu atimimu“.

Šio metodo esmė tokia: iš didesnio skaičiaus atimkite mažesnį skaičių, kol skaičiai bus lygūs, didesnį pakeičiant skirtumu. Kai tai atsitiks, GCD randamas. (Pavyzdys lentoje – skaičiai 48 ir 18)

Pirmas klausimas – ar šie skaičiai lygūs? Ne, jie nėra lygūs, todėl iš didesnio atimame mažesnįjį 48-18 = 30. 30 nelygu 18, vadinasi, 30-18= 12, 18-12=6, 12-6=6. Tai yra, atliekame šiuos veiksmus tol, kol skaičiai bus lygūs. Taigi gcd(48,18)=6

Žinodami skaičių 48 ir 18 GCD, raskite NOC. LCM(48,18)=(48*18):6=48*3=144

Raskime GCD(102;68) naudodami Euklido algoritmą.

Raskime NOD (357; 273)

Čia mes atėmėme skaičių 84 3 kartus ir skaičių 21 tris kartus.

Kaip neatimant atimčių sužinoti, kiek atimčių bus vienoje serijoje ir koks bus rezultatas? Kokius atvejus reikia apsvarstyti? ( indikacija: prisiminkite padalijimą.)

Bendrąją taisyklę galima suformuluoti taip: jei skaičius a nedalomas iš b, tada jis pakeičiamas jo likučiu, padalijus iš b(kada a< bši likutis yra a); jeigu a padalytą b, tada pakeiskite jį skaičiumi b. Lygiai ta pati taisyklė su permutacija a ir b, taip pat galioja b. Didesnis skaičius padalinti į mažesnę likutį, tada mažesnę - į pirmą likutį, tada pirmoji liekana į antrąją likutį ir taip toliau, kol gausite 0. Tadapaskutinė nelygi 0 liekana yra GCD .

Raskite GCD (357;273).

357 273 273 84 84 21 GCD (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

Euklido algoritmo patogumas tampa ypač pastebimas, jei žymėjimo formą taikome lentelės pavidalu:

Šioje planšetėje pirmiausia užrašomi pirminiai skaičiai, dalinami mintyse, likučiai užrašomi dešinėje, o privatūs – apačioje, kol procesas baigiasi. Paskutinis daliklis yra GCD.

Taigi, didžiausias bendras dviejų skaičių daliklis yra paskutinė ne nulis liekana, kai didesnį skaičių dalijant iš mažesnio., t.yjei a = b *q + r, tada gcd(a; b) = gcd(b; r)

Ši operacijų seka vadinama Euklido algoritmas.

1) Naudodami Euklido algoritmą suraskite skaičių GCD:

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

GCD(703;481)=37

GCD(2112;1680)=48

GCD(5075;1450)=

Patikrinkite rezultatus kompiuteryje.

Vaikų užduotis kompiuteryje yra surasti GCD ir LCM trims skaičiams naudojant GCD ir LCM paieškos programą.

gcd(150, ____) = ____

GCD(450,315,135)=____

GCD(135; ____) = ____

GCD(2160,1350,1080)=____

GCD (1080, ____) = ____

GCD(5300,3180,2120)=____

GCD (2120, ____) = ____

(Norėdami rasti trijų ar daugiau skaičių GCD, pirmiausia suraskite bet kurių dviejų iš jų GCD, tada rasto daliklio GCD ir trečiojo nurodyto skaičiaus.

ir trečiasis duotas skaičius.

7. Rezultatų tikrinimas kompiuteriu. Savarankiškas problemų sprendimas.

1) Tokios pat dovanos buvo paruoštos ir klasės mokiniams. Visų dovanų buvo 120 šokoladinių saldainių, 280 saldainių ir 320 riešutų. Kiek mokinių yra pirmoje klasėje, jei žinoma, kad yra daugiau nei 30?

Atsakymas:____________________________

2) Stotyje yra trys keleiviniai traukiniai: pirmame - 418 vietų kupiniuose vagonuose, antrajame - 494, o trečiame - 456. Kiek kupė vagonų yra kiekviename traukinyje, jei yra tiek pat sėdimų vietų kiekviename automobilyje ir bendras jų skaičius yra didesnis nei 20? Atsakymas _________________________

3) Puokštės buvo padarytos iš 156 arbatinių, 234 baltų ir 390 raudonų rožių, o visose kiekvienos rūšies rožių puokštėse buvo po lygiai ir tokių puokščių skaičius viršijo 50. Kiek puokščių iš šių rožių pagaminta ir kiek kiekvienos rūšies rožės buvo vienoje puokštėje? Atsakymas__________________

Pamokos santrauka. Su kokiu būdu rasti GCD ir LCM mes susipažinome pamokoje. Euklido algoritmas. Koks kitas šio metodo pavadinimas? (atimties metodas). Kaip šis metodas buvo patobulintas? Dalijant, didesnis skaičius dalijamas iš mažesnio skaičiaus, tada mažesnis skaičius iš pirmosios liekanos, tada pirmasis liekanas iš antrosios liekanos ir taip toliau, kol gaunamas 0. Paskutinė ne nulis liekana yra GCD numeriai.

Norėdami naudoti pristatymų peržiūrą, susikurkite „Google“ paskyrą (paskyrą) ir prisijunkite: https://accounts.google.com

Skaidrių antraštės:

Euklido algoritmas Euklidas, senovės graikų matematikas. III amžiuje dirbo Aleksandrijoje. pr. Kr e. Pagrindinis veikalas „Pradžia“ (15 knygų), kuriame yra senovės matematikos pagrindai, elementarioji geometrija, skaičių teorija, bendroji santykių teorija ir plotų bei tūrių nustatymo metodas, į kurį įeina ribų teorijos elementai. Jis padarė didelę įtaką matematikos raidai. Dirba su astronomija, optika, muzikos teorija. Euklidas (365–300 m. pr. Kr.)

EUKLIDO ALGORITMAS Euklido algoritmas yra dviejų neneigiamų sveikųjų skaičių didžiausio bendro daliklio (gcd) radimo algoritmas. Euklidas (365-300 m. pr. Kr.) Senovės graikų matematikai šį algoritmą pavadino ἀνθυφαίρεσις arba ἀνταναίρεσις – „abipusis atimtis“.

Skaičiavimas GCD GCD = didžiausias bendras dviejų natūraliųjų skaičių daliklis yra didžiausias skaičius, iš kurio abu pradiniai skaičiai dalijasi be liekanos. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Didesnįjį iš dviejų skaičių pakeiskite skirtumu tarp didesnio ir mažesnio, kol jie bus lygūs. Tai NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Pavyzdys:

ŽINGSNIS Veikimas M N Sąlyga 1 Įvestis M 48 2 Įvestis N 18 3 M  N 48  18, taip 4 M>N 48>18, taip 5 M:=M-N 30 6 M  N 30  18, taip 30 7 M>N >18, taip 8 M:=M-N 12 9 M  N 12 18, taip 10 M>N 12 >18, ne 11 N:=N-M 6 12 M  N 12  6, taip 13 M>N 12 >6 , taip 14 M:=M-N 6 15 M  N 6  6, ne 16 Išėjimas M

programa Evklid ; var m, n: sveikasis skaičius; begin writeln("vved 2 chisla"); readln(m,n); tuo tarpu mn prasideda, jei m>n tada m:=m-n else n:= n-m ; pabaiga; rašyti("nod=",m); skaitymo pabaiga.

0. Kompiuteryje paleiskite programą Evklid. Išbandykite su M=32, N=24; M = 696, N = 234. vienas . Patikrinkite, ar du pateikti skaičiai yra pirminiai. Pastaba. Sakoma, kad du skaičiai yra pirminiai, jei jų didžiausias bendras daliklis yra 1. 2 . Raskite skaičių n ir m mažiausiąjį bendrąjį kartotinį (LCM), jei LCM(n, m) = n * m / gcd(n, m). 3 . Pateikiami natūralieji skaičiai m ir n. Raskite natūraliuosius skaičius p ir q, kurie neturi bendrų daliklių, kad p/q = m/n. 4. Raskite trijų skaičių GCD. Pastaba. GCD(a , b , c)= GCD(gcd(a , b), c) Užduotys

Peržiūra:

Tema: "Euklido algoritmas"

Pamokos tikslai:

1. Švietimas:

1. išmokite naudoti Euklido algoritmą dviejų ir trijų skaičių gcd rasti
2. įtvirtinti įgūdžius naudojant algoritmines struktūras „Šakojimai“ ir „Cycle“
3. įgyti patirties rašant ir derinant programas Pascal programavimo kalba

1. Švietimas:

1. savarankiškumo ir atsakomybės formavimas studijuojant naują medžiagą

1. Kuriama:

1. dėmesingumo ir analitinio mąstymo ugdymas

Pamokos planas:

1. Laiko organizavimas
2. Žinių atnaujinimas
3. Naujos temos paaiškinimas
4. Praktinė dalis
5. Apibendrinant pamoką
6. Namų darbai.

Laiko organizavimas

Sveikinimai. Kurio nėra. Skaičius. Pamokos tema. Klausimai apie namų darbus.

Žinių atnaujinimas.

Klausimai:

Kokius algoritminių struktūrų tipus žinote?

Kas yra linijinė struktūra? (Bl-sh)

Kas yra išsišakojusi struktūra? (Bl-sh)

Kas yra ciklinė struktūra? (Bl-sh)

Kokius ciklų tipus žinote?

Kaip Pascal programavimo kalba realizuojamas ciklas su žinomu pakartojimų skaičiumi?

Kaip Pascal programavimo kalba realizuojamas ciklas su nežinomu pakartojimų skaičiumi?

Naujos temos paaiškinimas (pristatymas)

Apie Euklidą;

Euklido algoritmo idėja

Šio algoritmo idėja pagrįsta:

1. Savybė, kad jei M>N, tai GCD(M, N) = GCD(M - N, N).

Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo gcd (jų skirtumo moduliui) ir mažesniam skaičiui.

Įrodymas: tegul K yra bendras M ir N daliklis (M > N). Tai reiškia, kad M \u003d mK, N \u003d nK, kur m, n yra natūralūs skaičiai, o m > n. Tada M - N \u003d K (m - n), o tai reiškia, kad K yra skaičiaus M - N daliklis. Taigi visi bendrieji skaičių M ir N dalikliai yra jų skirtumo M - N dalikliai, įskaitant didžiausią bendras daliklis.

2. Antra akivaizdi savybė:

GCD(M, M) = M.

„Rankiniam“ skaičiavimui Euklido algoritmas atrodo taip:

1) jei skaičiai lygūs, kaip atsakymą paimkite bet kurį iš jų, kitu atveju tęskite algoritmą;

2) pakeisti didesnį skaičių skirtumu tarp didesnio ir mažesnio skaičių;

3) grįžti prie 1 dalies įgyvendinimo.

Euklido algoritmo blokinė schema

Programa JS Pascal

programa Evklid;

var m, n: sveikasis skaičius;

pradėti

writeln("vved 2 skaičiai");

readln(m,n);

Nors mn daro

Pradėkite

Jei m>n

Tada m:=m-n

Kitaip n:=n-m;

pabaiga;

Write("nod=",m);

readln

pabaiga.

Praktinė dalis

Klausimai ir užduotys:

1. Savo kompiuteryje paleiskite programą Evklid. Išbandykite M=32, N=24; M = 696, N = 234.
2. Patikrinkite, ar du pateikti skaičiai yra pirminiai. Pastaba. Sakoma, kad du skaičiai yra pirminiai, jei jų didžiausias bendras daliklis yra 1.

Apibendrinant pamoką

Šiandien pamokoje susipažinome su Euklido algoritmu, leidžiančiu rasti dviejų neneigiamų sveikųjų skaičių GCD, parašėme programą Pascal programavimo kalba, kuri realizuoja šį algoritmą. Namuose gausite užduotį, kurioje taikydami šį algoritmą rasite trijų skaičių GCD ir dviejų skaičių LCM.

Namų darbai.

1. Parašykite programą, kuri pagal šią formulę rastų didžiausią bendrą trijų skaičių daliklį:

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

2. Parašykite programą dviejų skaičių mažiausiajam bendrajam kartotiniui (LCM) rasti naudodami formulę:

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

Uždavinio teiginys Apsvarstykite šią problemą: reikia parašyti programą dviejų natūraliųjų skaičių didžiausiam bendrajam dalikliui (GCD) nustatyti. Prisiminkime matematiką. Didžiausias bendras dviejų natūraliųjų skaičių daliklis yra didžiausias natūralusis skaičius, iš kurio jie dalijasi tolygiai. Pavyzdžiui, skaičiai 12 ir 18 turi bendrus daliklius: 2, 3, 6. Didžiausias bendras daliklis yra skaičius 6. Tai rašoma taip: gcd(12,18) = 6. Pradinius duomenis pažymėkite kaip M ir N Problemos teiginys yra toks: Duota: M, N Rasti: GCD(M, N).

N, tada GCD(M,N) = GCD(M – N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd." title="(!LANG:Algoritmo idėja Šio algoritmo idėja pagrįsta savybė, kad jei M>N, tai gcd(M,N) = gcd( M - N, N) Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesniojo skaičiaus gcd." class="link_thumb"> 4 !} Algoritmo idėja Šio algoritmo idėja pagrįsta savybe, kad jei M>N, tai GCD(M,N) = GCD(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd. N, tada GCD(M,N) = GCD(M – N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd."> N, tada gcd(M,N) = gcd(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd."> N, tada GCD(M,N) = GCD(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd." title="(!LANG:Algoritmo idėja Šio algoritmo idėja pagrįsta savybė, kad jei M>N, tai gcd(M,N) = gcd( M - N, N) Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesniojo skaičiaus gcd."> title="Algoritmo idėja Šio algoritmo idėja pagrįsta savybe, kad jei M>N, tai GCD(M,N) = GCD(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd."> !}

N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N = K(m - n), iš to išplaukia, kad K yra M - N daliklis. Vadinasi, visi bendrieji M ir N dalikliai yra dalikliai" title="(!LANG:Proof Tegu K yra bendras M ir. N daliklis (M > N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m> n. Tada M - N = K(m - n), iš kur jis iš to seka, kad K yra skaičiaus M – N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai" class="link_thumb"> 5 !}Įrodymas Tegul K yra bendras M ir daliklis. N (M>N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N = K(m - n), iš ko išplaukia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra jų skirtumo M - N dalikliai, įskaitant didžiausią bendras daliklis. Vadinasi: GCD(M,N) = GCD(M – N,N). Antroji akivaizdi savybė: GCD(M,M) = M. N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N \u003d K (m - n), iš to išplaukia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai "\u003e N). Tai reiškia, kad M \u003d mK, N \u003d pK , kur m, n yra natūralūs skaičiai, o m > n. Tada M - N = K(m - n), tai reiškia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra jų skirtumo M-N dalikliai, įskaitant didžiausią bendrąjį daliklį. Vadinasi: GCD(M, N) = GCD(M - N, N). Antroji akivaizdi savybė: GCD(M) , M) = M."> N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N = K(m - n), iš to išplaukia, kad K yra M - N daliklis. Vadinasi, visi bendrieji M ir N dalikliai yra dalikliai" title="(!LANG:Proof Tegu K yra bendras M ir. N daliklis (M > N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m> n. Tada M - N = K(m - n), iš kur jis iš to seka, kad K yra skaičiaus M – N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai"> title="Įrodymas Tegul K yra bendras M ir daliklis. N (M>N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N \u003d K (m - n), o tai reiškia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai"> !}

Programa Pascal programoje Evklid; var M, N: sveikasis skaičius; begin writeln ("Įveskite M ir N"); readln(M,N); tuo tarpu MN prasideda, jei M>N, tada M:=M-N kitaip N:=N-M pabaiga; rašyti("HOD=",M) pabaiga. N, tada M:=M-N, kitaip N:=N-M galas; rašyti("HOD=",M) pabaiga."> N, tada M:=M-N kitaip N:=N-M pabaiga; rašyti("HOD=",M) pabaiga."> N, tada M:=M-N kitaip N:=N-M pabaiga; write("HOD=",M) end." title="(!LANG:Pascal programa Program Evklid; var M, N: integer; begin 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, tada M:=M-N, kitaip N:=N-M galas; write("HOD=",M) end." title="(!LANG:Pascal programa Program Evklid; var M, N: integer; begin 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."> !}

skaidrė 1

skaidrė 2

EUKLIDO ALGORITMAS Euklido algoritmas yra dviejų neneigiamų sveikųjų skaičių didžiausio bendro daliklio (gcd) radimo algoritmas. Euklidas (365-300 m. pr. Kr.) Senovės graikų matematikai šį algoritmą pavadino ἀνθυφαίρεσις arba ἀνταναίρεσις – „abipusis atimtis“.

skaidrė 3

Skaičiavimas GCD GCD = didžiausias bendras dviejų natūraliųjų skaičių daliklis yra didžiausias skaičius, iš kurio abu pradiniai skaičiai dalijasi be liekanos. gcd(a, b)= gcd(a-b, b)= gcd(a, b-a) Didesnįjį iš dviejų skaičių pakeiskite skirtumu tarp didesnio ir mažesnio, kol jie bus lygūs. Tai NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27)=gcd(18, 9) ==gcd(9,9)=9 Pavyzdys:

skaidrė 4

ŽINGSNIS Veikimas M N Sąlyga 1 ĮvestisM 48 2 ĮvestisN 18 3 M N 48 18,taip 4 M>N 48>18,taip 5 M:=M-N 30 6 M N 30 18,taip 7 M>N 30>18,taip 8 M:= M-N 12 9 M N 12 18 taip 10 M>N 12>18 ne 11 N:=N-M 6 12 M N 12 6 taip 13 M>N 12>6 taip 14 M:=M-N 6 15 M N 6 6 ne 16 Išvada

skaidrė 5

programa Evklid; var m, n: sveikasis skaičius; begin writeln("vved 2 numeriai"); readln(m,n); o mn prasideda, jei m>n tada m:=m-n else n:=n-m; pabaiga; rašyti("nod=",m); skaitymo pabaiga.

skaidrė 6

0. Kompiuteryje paleiskite programą Evklid. Išbandykite su M=32, N=24; M = 696, N = 234. 1. Patikrinkite, ar du pateikti skaičiai yra pirminiai. Pastaba. Du skaičiai vadinami santykinai pirminiais, jei jų didžiausias bendras daliklis yra 1. 2. Raskite skaičių n ir m mažiausiąjį bendrąjį kartotinį (LCM), jei LCM(n, m) = n * m / gcd(n, m). 3. Duoti natūralieji skaičiai m ir n. Raskite natūraliuosius skaičius p ir q be bendrųjų daliklių, kad p / q = m / n. 4. Raskite trijų skaičių GCD. Pastaba. gcd(a, b, c)= gcd(gcd(a, b), c) Užduotys

7 skaidrė

Euklidas, senovės graikų matematikas. III amžiuje dirbo Aleksandrijoje. pr. Kr e. Pagrindinis veikalas „Pradžia“ (15 knygų), kuriame yra senovės matematikos pagrindai, elementarioji geometrija, skaičių teorija, bendroji santykių teorija ir plotų bei tūrių nustatymo metodas, į kurį įeina ribų teorijos elementai. Jis padarė didelę įtaką matematikos raidai. Dirba su astronomija, optika, muzikos teorija.