Pagtatanghal para sa trabaho ng bilog na Euclidean algorithm. Pagtatanghal sa paksang "Euclid's algorithm". Ideya ng algorithm ni Euclid

klase: 6

Layunin ng Aralin:

ayusin ang algorithm para sa paghahanap ng pinakadakilang karaniwang divisor gamit ang factorization;
ulitin ang mga kaugnay na kahulugan at konsepto;
ipakilala ang mga mag-aaral sa Euclid algorithm;
upang mabuo ang mga kasanayan ng kulturang matematika

Kagamitan: computer, projector, screen.

Sa panahon ng mga klase

1. Oras ng pag-aayos (pagsusuri sa kahandaan ng mga mag-aaral para sa aralin, pagmamarka ng absent) (1 min)

2. Oral na gawain: (6 min)

1. Palitan ang produkto ng isang degree:

d) a * a * a * a * a

Kalkulahin: 2 3 ; 52; 3 3 ; 10 4 .
Hanapin ang halaga ng expression: (3?3?5?11): (3?11). Anong konklusyon ang mabubuo?
Magsagawa ng dibisyon a sa b kung a=170, b=35. Isulat ang pagkakapantay-pantay, kung ano ang katumbas ng a.

Isulat ang pagkakapantay-pantay na ito sa pangkalahatang anyo: ang a ay mahahati, at ang b ay isang divisor. Hayaang ang quotient ay q at ang natitirang r, kung gayon: a = bq + r , at ang q ay maaaring natural na numero o zero. Maaari bang maging anumang numero? Ang [ r ay isang natural na numero, at 0 < r < b .] Ano ang masasabi tungkol sa mga numerong a at b kung r = 0? Ang integer division ay isang espesyal na kaso ng dibisyon na may natitira.

Alamin at ipaliwanag kung ang numero a ay nahahati sa bilang b na walang nalalabi kung:

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

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

b = 2 7 * 3 * 5 4

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

b = 2 * 3 3 * 5 * 11.

3. Pag-update ng mga pangunahing kaalaman(10 minuto)

1) Mga Tanong:

Ano ang number divisor a ?

Ano ang prime number?

Ano ang ibig sabihin ng pag-factor ng isang numero sa prime factor?

Bumuo ng mga palatandaan ng divisibility sa pamamagitan ng 2, 3, 5, 9,10;

Magbigay ng halimbawa ng isang solong digit na composite number;

Totoo bang prime number ang number 77?

Bakit, kung ang isang numero ay maaaring mabulok sa 2 prime factor, at ang isa sa 3 prime factor, kung gayon ang mga numerong ito ay hindi pantay?

Aling numero, prime o composite, ang produkto ng dalawang prime number?

Ano ang pinakamalaking karaniwang divisor ng dalawa o higit pang mga numero?

Anong mga numero ang tinatawag na coprime?

Ulitin ang mga paraan upang mahanap ang GCD: Mayroong iba't ibang mga algorithm para sa paghahanap ng GCD ng mga natural na numero.

1 paraan: Kung ang dalawang numero ay ibinigay at ang mga ito ay medyo maliit, kung gayon ang pinakamahusay na algorithm ay ang brute-force na paghahanap. Gayunpaman, para sa malalaking numero, hanapin ang gcd(a;b) sa pamamagitan ng paglilista ng lahat ng mga divisors ng mga numero a at b Ang proseso ay matrabaho at hindi mapagkakatiwalaan.

Kapaki-pakinabang na tandaan na ang gcd ng anumang bilang ng mga numero ay hindi lalampas sa pinakamaliit sa kanila.

2 paraan: sa pamamagitan ng mga numero ng factoring (pinakakaraniwan) (Appendix, slide1)

2) Kalkulahin ang GCD ng mga numero 24 at 16.

3) I-factor ang mga numero: 875 at 8000 at kalkulahin ang GCD ng mga numerong ito.

(Gamit ang numerong 8000 bilang halimbawa, ulitin ang isang mas simpleng paraan ng pag-factor ng mga numero na nagtatapos sa mga zero: dahil 10=2 *5, pagkatapos ay 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 *5 3)

4) Maaari bang ang GCD ng tatlong numero ay katumbas ng 15 kung ang kanilang produkto ay katumbas ng 3000? [ Hindi, bilang

15 \u003d 3 * 5, na nangangahulugan na ang numero 3 ay dapat isama sa pagpapalawak ng bawat isa sa tatlong numero. Ngunit, 3000 = 2 3 * 3 * 5 3 .]

5) P kainin ang gawain"Ang mga aklat-aralin ay dinala sa klase: 24 sa matematika, 36 sa kasaysayan at 48 sa heograpiya. Ano ang pinakamalaking bilang ng mga set na maaaring gawin mula sa mga aklat na ito upang ang bawat isa ay naglalaman ng parehong bilang ng mga libro sa matematika, kasaysayan at heograpiya? Ilang libro ang nasa bawat set?"

4. Pag-verify ng trabaho (Appendix, slide 2) (6 min)

5. Pag-aaral ng bagong materyal (10 min)

Guro: Ang pinag-aralan na paraan ng paghahanap ng GCD(a, b) ay simple, naiintindihan at maginhawa, ngunit ito ay may isang makabuluhang disbentaha: kung ang mga ibinigay na numero ay malaki, at kahit na hindi masyadong madaling i-factor, kung gayon ang gawain ng paghahanap ng GCD(a, b) nagiging medyo mahirap. Bilang karagdagan, maaaring lumabas na, kapag nagsumikap, titiyakin namin na ang GCD(a, b) = 1 at tila ang lahat ng gawain ay nagawa nang walang kabuluhan.

Nakakita si Euclid ng magandang paraan ng paghahanap ng gcd(a, b) nang walang anumang preprocessing ng mga numero. (Apendise, slide 3 at 4) Kasunod nito, ang algorithm na ito ay naging kilala bilang algorithm ni Euclid)

Kilalanin natin ang Euclid algorithm. Hayaang kailanganin na mahanap ang gcd(102;84). Hatiin ang isang numero sa isa pa at hanapin ang natitira.

Ngayon gawin natin ang parehong operasyon para sa mga numero 84 at 18:

Ang susunod na hakbang ay para sa 18 at 12:

Ngayon - para sa 12 at 6:

0-nalalabi. Natapos na ang proseso.

Ang prosesong ito ay hindi maaaring walang katapusan, dahil ang mga nalalabi ay bumababa, natitira non-negative integers, ang set kung saan, gaya ng nalalaman, ay bounded mula sa ibaba:

84 >18 > 12> 6 >0

Kung titingnan mong mabuti ang mga nakasulat na pagkakapantay-pantay, maaari mong itatag na ang GCD ng lahat ng pares ng mga numero ay pantay sa isa't isa (imbitahan ang mga mag-aaral na mag-isip - bakit?),

ibig sabihin, gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. Ngunit ang numero 6 ay ang huling hindi-0 na natitira .

Sa katunayan, kung ang c ay isang di-makatwirang karaniwang divisor ng mga numerong a at b, kung gayon ang r = a - bq ay nahahati sa c; at kabaliktaran, kung ang c ay isang arbitraryong karaniwang divisor ng b at r, kung gayon ang a ay mahahati ng c. Ibig sabihin, lahat ng karaniwang divisors ng mga pares (a; b) at (b; r) ay nagtutugma, at samakatuwid ang kanilang pinakadakilang karaniwang divisors ay nag-tutugma din.

Ang kaginhawahan ng algorithm ng Euclid ay nagiging lalong kapansin-pansin kung ilalapat natin ang anyo ng notasyon sa anyo ng isang talahanayan:

Sa tablet na ito, ang mga orihinal na numero ay unang isinulat, hinati sa isip, isinusulat ang mga natitira sa kanan, at mga pribado sa ibaba, hanggang sa matapos ang proseso. Ang huling divisor ay ang GCD.

Kaya, ang pinakamalaking karaniwang divisor ng dalawang numero ay ang huli, hindi katumbas ng 0, ang natitira kapag hinahati ang isang mas malaking numero sa isang mas maliit, iyon ay kung a = b*q + r, pagkatapos ay gcd(a; b) = gcd(b; r)

Ang pagkakasunud-sunod ng mga operasyon na ito ay tinatawag Ang algorithm ni Euclid. Binibigyang-daan ka ng algorithm na ito na mahanap ang GCD ng mga numero nang hindi isinaalang-alang ang mga ito (Appendix, slide 5)

6. Mga Pagsasanay (10 min)

1. Maipapayo na isaalang-alang ang isang halimbawa. Hayaang kailanganin na hanapin ang GCD ng mga numerong 323 at 437. Hindi madaling gawin ito sa pamamagitan ng pagpili o pag-decomposition sa prime factor, dahil wala sa mga numerong ito ang multiple ng 2, 3, 5, 7, 11. Kami magpatuloy tulad ng sumusunod (

Paksa: Euclid's algorithm para sa paghahanap ng GCD.

Mga layunin:ulitin ang mga naunang pinag-aralan na paksa Greatest Common Divisor at Least Common Multiple, ipakilala ang algorithm ni Euclid.

Mga layunin sa pag-aaral - upang ulitin ang mga konsepto ng pinakamalaking karaniwang divisor at ang hindi bababa sa karaniwang maramihang, ang panuntunan para sa paghahanap ng mga ito. Panimula sa algorithm ni Euclid. Ayusin ang algorithm ng Euclid sa pamamagitan ng paglutas ng mga kaukulang gawain.

Mga gawain sa pag-unlad - ang pag-unlad ng lohikal na pag-iisip, atensyon, memorya ng pagsasalita, ang kakayahang nakapag-iisa na tumuklas ng bagong kaalaman, pag-usisa sa matematika, interes sa pag-iisip sa paksa.

Ang mga gawain ng edukasyon ay upang linangin ang isang kultura ng matematikal na pag-iisip, pagtulong sa isa't isa, pagsusuri sa sarili at pagsusuri ng mga pagkakamali ng isang tao.

Magtrabaho sa mga card

Maghanap ng mga GCD o LCM na numero at tukuyin ang parirala:

300

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)

Ako: gcd(102.68)

E: GCD(18,12)

Sa huling talahanayan, isulat ang natitirang mga pares ng mga numero

Mga sagot:

300

PERO

Upang

PERO

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

AT: GCD(102.68)=34

E: GCD(18,12)=6

Hulaan ang 2 pang salita

Ano ang masasabi tungkol sa mga numero sa huling talahanayan? Sila ay coprime, i.e. kung ibubulok natin ang mga numerong ito sa mga pangunahing kadahilanan, kung gayon hindi magkakaroon sila ng parehong mga kadahilanan. Paano mahahanap ang GCD ng mga naturang numero? Tango ng mga naturang numero =1. At kung paano hanapin ang LCM, upang mahanap ang LCM, kailangan mong i-multiply ang mga numerong ito sa bawat isa.

Sa unang hanay ay may mga pares ng mga numero kung saan ang isa sa mga ito ay hindi nahahati nang buo. Yung. ang natitira ay hindi 0.

Paano mo nahanap ang GCD at LCM ng mga naturang numero. (Sa pamamagitan ng pag-decompose ng mga numerong ito sa mga pangunahing kadahilanan)

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

Alalahanin ang panuntunan para sa paghahanap ng GCD at LCM, hanapin at suriin ang formula LCM (a, b) \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

Paggalugad ng bagong paksa:

GCD ng anong pares ng mga numero ang 6?

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

Ano ang napansin mo? Paano ka nakakuha ng 30? 48-18

Paano ka nakakuha ng 12? 30-18

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

Yung. GCD (a, c) Kapag v> a = GCD (a, c-a)

Sino ang maaaring magpatuloy sa pagkakapantay-pantay na ito?

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

Ang algorithm ng Euclid ay batay sa panuntunang ito.

Ang algorithm ni Euclid- mahusay para sa paghahanap ng dalawa. Ang algorithm ay pinangalanan pagkatapos, na unang inilarawan ito sa VII at X na mga libro "".

Sa pinakasimpleng kaso nito, inilapat ang algorithm ng Euclid sa isang pares ng mga positive integer at bumubuo ng bagong pares na binubuo ng mas maliit na numero at sa pagitan ng mas malaki at mas maliit na numero. Ang proseso ay paulit-ulit hanggang ang mga numero ay pantay. Ang nahanap na numero ay ang pinakamalaking karaniwang divisor ng orihinal na pares.

Tinawag ng mga sinaunang Greek mathematician ang algorithm na ito na "mutual subtraction".

Ang kakanyahan ng pamamaraang ito ay ang mga sumusunod: ibawas ang mas maliit na numero mula sa mas malaking bilang hanggang sa magkapantay ang mga numero, palitan ang mas malaki ng pagkakaiba. Kapag nangyari ito, makikita ang GCD. (Halimbawa sa pisara - mga numero 48 at 18)

Ang unang tanong ay, pantay ba ang mga numerong ito? Hindi, hindi sila pantay, kaya ibawas natin ang mas maliit sa mas malaking 48-18 = 30. Ang 30 ay hindi katumbas ng 18, ibig sabihin ay 30-18= 12, 18-12=6, 12-6=6. Ibig sabihin, ginagawa namin ang mga pagkilos na ito hanggang sa magkapantay ang mga numero. Kaya gcd(48,18)=6

Pag-alam sa GCD ng mga numero 48 at 18, hanapin ang NOC. LCM(48,18)=(48*18):6=48*3=144

Hanapin natin ang GCD(102;68) gamit ang algorithm ng Euclid.

Hanapin natin NOD (357;273)

Dito ay ibinawas natin ang bilang na 84 3 beses at ang bilang na 21 ng tatlong beses.

Paano, nang hindi gumagawa ng mga pagbabawas, upang malaman kung gaano karaming mga pagbabawas ang magkakaroon sa isang serye, at anong pagkakaiba ang magiging resulta? Anong mga kaso ang kailangang isaalang-alang? ( indikasyon: tandaan ang paghahati.)

Ang pangkalahatang tuntunin ay maaaring mabalangkas tulad ng sumusunod: kung ang numero a hindi mahahati ng b, pagkatapos ay papalitan ito ng natitira kapag hinati ng b(kailan a< b ang natitira ay a); kung a hinati ng b, pagkatapos ay palitan ito ng numero b. Eksaktong parehong panuntunan, na may permutasyon a at b, ay may bisa din para sa b. Mas malaking numero hatiin sa mas maliit, pagkatapos ay mas mababa sa unang nalalabi, pagkatapos ang unang nalalabi sa pangalawang nalalabi, at iba pa, hanggang sa makakuha ka ng 0. Pagkataposang huling natitirang hindi katumbas ng 0 ay GCD .

Hanapin ang 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

Ang kaginhawahan ng algorithm ng Euclid ay nagiging lalong kapansin-pansin kung ilalapat natin ang anyo ng notasyon sa anyo ng isang talahanayan:

Kaya, ang pinakamalaking karaniwang divisor ng dalawang numero ay ang huling hindi-zero na natitira kapag hinahati ang mas malaking bilang sa mas maliit., ibig sabihinkung a = b *q + r, pagkatapos ay gcd(a; b) = gcd(b; r)

Ang pagkakasunud-sunod ng mga operasyon na ito ay tinatawag Ang algorithm ni Euclid.

1) Gamit ang Euclid algorithm, hanapin ang GCD ng mga numero:

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

GCD(703;481)=37

GCD(2112;1680)=48

GCD(5075;1450)=

Suriin ang mga resulta sa isang computer.

Ang gawain ng mga bata sa computer ay maghanap ng GCD at LCM para sa tatlong numero gamit ang program para sa paghahanap ng GCD at LCM.

gcd(150, ____) = ____

GCD(450,315,135)=____

GCD(135, ____) = ____

GCD(2160,1350,1080)=____

GCD (1080, ____) = ____

GCD(5300,3180,2120)=____

GCD (2120, ____) = ____

(Upang mahanap ang GCD ng tatlo o higit pang mga numero, hanapin muna ang GCD ng alinman sa dalawa sa mga ito, pagkatapos ay ang GCD ng natagpuang divisor at ang ikatlong ibinigay na numero.

at ang ikatlong ibinigay na numero.

7. Sinusuri ang mga resulta sa isang computer. Malayang paglutas ng problema.

1) Ang parehong mga regalo ay inihanda para sa mga mag-aaral ng klase. Kasama sa lahat ng regalo ang 120 tsokolate, 280 matamis, at 320 mani. Ilang estudyante ang nasa unang baitang kung malalaman na higit sa 30?

Sagot: ___________________________

2) May tatlong pampasaherong tren sa istasyon: sa una - 418 na upuan sa mga compartment na kotse, sa pangalawa - 494, at sa pangatlo - 456. Ilang mga compartment na kotse ang nasa bawat tren kung may parehong bilang ng mga upuan sa bawat kotse at ang kanilang kabuuang bilang ay higit sa 20? Sagot _______________________

3) Ang mga bouquet ay ginawa mula sa 156 na tsaa, 234 na puti at 390 na pulang rosas, at sa lahat ng mga bouquet ng mga rosas ng bawat uri ay may pantay-pantay at ang bilang ng mga naturang bouquet ay higit sa 50. Ilang mga bouquet ang ginawa mula sa mga rosas na ito at kung gaano karaming mga rosas ng bawat uri ay nasa isang palumpon? Sagot________________

Buod ng aralin. Sa anong paraan ng paghahanap ng GCD at LCM nakilala natin sa aralin. Ang algorithm ni Euclid. Ano ang isa pang pangalan para sa pamamaraang ito? (paraan ng pagbabawas). Paano napabuti ang pamamaraang ito? Sa paghahati, ang mas malaking numero ay hinahati sa mas maliit na numero, pagkatapos ay ang mas maliit na numero sa unang natitira, pagkatapos ang unang natitira sa pangalawang natitira, at iba pa, hanggang sa makakuha ka ng 0. Ang huling hindi-zero na natitira ay ang GCD ng numero.

Upang gamitin ang preview ng mga presentasyon, lumikha ng isang Google account (account) at mag-sign in: https://accounts.google.com

Mga slide caption:

Euclid's Algorithm Euclid, sinaunang Greek mathematician. Nagtrabaho sa Alexandria noong ika-3 siglo. BC e. Ang pangunahing gawain na "Mga Simula" (15 mga libro), na naglalaman ng mga pundasyon ng sinaunang matematika, elementarya na geometry, teorya ng numero, pangkalahatang teorya ng mga relasyon at ang pamamaraan para sa pagtukoy ng mga lugar at volume, na kasama ang mga elemento ng teorya ng mga limitasyon. Malaki ang impluwensya niya sa pag-unlad ng matematika. Gumagana sa astronomiya, optika, teorya ng musika. Euclid (365-300 BC)

ALGORITHM NG EUCLID Ang algorithm ng Euclid ay isang algorithm para sa paghahanap ng pinakamalaking karaniwang divisor (GCD) ng dalawang di-negatibong integer. Euclid (365-300 BC) Tinawag ng mga sinaunang Greek mathematician ang algorithm na ito na ἀνθυφαίρεσις o ἀνταναίρεσις - "mutual subtraction".

Pagkalkula GCD GCD = ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking bilang kung saan ang parehong orihinal na mga numero ay nahahati nang walang natitira. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Palitan ang mas malaki sa dalawang numero ng pagkakaiba sa pagitan ng mas malaki at mas maliit hanggang sa magkapantay ang mga ito. Ito ay NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Halimbawa:

HAKBANG Operasyon M N Kondisyon 1 Input M 48 2 Input N 18 3 M  N 48 18, oo 4 M>N 48>18, oo 5 M:=M-N 30 6 M  N 30  18, oo 7 M>N 30 >18, oo 8 M:=M-N 12 9 M  N 12 18, oo 10 M>N 12 >18, hindi 11 N:=N-M 6 12 M  N 12  6, oo 13 M>N 12 >6 , oo 14 M:=M-N 6 15 M  N 6  6, hindi 16 Output M

programa Evklid ; var m, n: integer; simulan writeln("vved 2 chisla"); readln(m,n); habang mn magsisimula kung m>n pagkatapos m:=m-n iba n:= n-m ; wakas; write("nod=",m); matapos basahin.

0. Patakbuhin ang Evklid program sa computer. Subukan ito ng M=32, N=24; M=696, N=234. isa. Suriin kung ang dalawang ibinigay na numero ay coprime. Tandaan. Ang dalawang numero ay sinasabing coprime kung ang kanilang pinakamalaking karaniwang divisor ay 1. 2 . Hanapin ang least common multiple (LCM) ng mga numero n at m kung LCM(n, m) = n * m / gcd(n, m). 3 . Ang mga natural na bilang na m at n ay ibinibigay. Maghanap ng mga natural na numerong p at q na walang karaniwang divisors na p / q = m / n . 4. Hanapin ang GCD ng tatlong numero. Tandaan. GCD(a , b , c)= GCD(gcd(a , b), c) Mga Gawain

Preview:

Paksa: "Euclid's Algorithm"

Layunin ng Aralin:

Pang-edukasyon:

alamin kung paano gamitin ang Euclid algorithm upang mahanap ang gcd ng dalawa at tatlong numero
pagsama-samahin ang mga kasanayan sa paggamit ng mga istrukturang algorithm na "Branching" at "Cycle"
magkaroon ng karanasan sa pagsulat at pag-debug ng mga programa sa wikang programming ng Pascal

Pang-edukasyon:

pagbuo ng kalayaan at pananagutan sa pag-aaral ng bagong materyal

Pagbuo:

pag-unlad ng atensyon at analytical na pag-iisip

Plano ng aralin:

Oras ng pag-aayos
Pag-update ng kaalaman
Pagpapaliwanag ng bagong paksa
Praktikal na bahagi
Pagbubuod ng aralin
Takdang aralin.

Oras ng pag-aayos

Pagbati. Sino ang absent. Numero. Paksa ng aralin. Mga tanong sa takdang-aralin.

Pag-update ng kaalaman.

Mga Tanong:

Anong mga uri ng algorithmic na istruktura ang alam mo?

Ano ang isang linear na istraktura? (Bl-sh)

Ano ang istrakturang sumasanga? (Bl-sh)

Ano ang cyclic structure? (Bl-sh)

Anong mga uri ng cycle ang alam mo?

Paano ipinapatupad ang isang loop na may kilalang bilang ng mga pag-uulit sa wikang programming ng Pascal?

Paano ipinapatupad ang isang loop na may hindi kilalang bilang ng mga pag-uulit sa wikang programming ng Pascal?

Pagpapaliwanag ng bagong paksa (pagtatanghal)

Tungkol kay Euclid;

Ideya ng algorithm ni Euclid

Ang ideya ng algorithm na ito ay batay sa:

1. Ang property na kung M>N, pagkatapos ay GCD(M, N) = GCD(M - N, N).

Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba (ang modulus ng kanilang pagkakaiba) at ang mas maliit na numero.

Patunay: hayaang ang K ay isang karaniwang divisor ng M at N (M > N). Nangangahulugan ito na ang M \u003d mK, N \u003d nK, kung saan ang m, n ay mga natural na numero, at m > n. Pagkatapos M - N \u003d K (m - n), na nagpapahiwatig na ang K ay isang divisor ng numero M - N. Samakatuwid, ang lahat ng mga karaniwang divisors ng mga numero M at N ay mga divisors ng kanilang pagkakaiba M - N, kabilang ang pinakamalaking karaniwang divisor.

2. Pangalawang halatang ari-arian:

GCD(M, M) = M.

Para sa "manual" na pagbibilang, ganito ang hitsura ng algorithm ni Euclid:

1) kung ang mga numero ay pantay, pagkatapos ay kunin ang alinman sa mga ito bilang isang sagot, kung hindi man ay ipagpatuloy ang algorithm;

2) palitan ang mas malaking numero ng pagkakaiba sa pagitan ng mas malaki at mas maliit ng mga numero;

3) bumalik sa pagpapatupad ng talata 1.

Block diagram ng Euclid algorithm

Programa sa JS Pascal

programa Evklid;

var m, n: integer;

magsimula

writeln("vved 2 numero");

readln(m,n);

Habang ginagawa ko

Magsimula

Kung m>n

Pagkatapos m:=m-n

Iba n:=n-m;

wakas;

Write("nod=",m);

readln

wakas.

Praktikal na bahagi

Mga tanong at gawain:

Patakbuhin ang Evklid program sa iyong computer. Subukan ito sa M=32, N=24; M = 696, N = 234.
Suriin kung ang dalawang ibinigay na numero ay coprime. Tandaan. Dalawang numero ang sinasabing coprime kung ang kanilang pinakamalaking karaniwang divisor ay 1.

Pagbubuod ng aralin

Ngayon sa aralin nakilala namin ang Euclid algorithm, na nagbibigay-daan sa amin upang mahanap ang GCD ng dalawang hindi negatibong integer, nagsulat kami ng isang programa sa Pascal programming language na nagpapatupad ng algorithm na ito. Sa bahay, makakatanggap ka ng isang gawain kung saan ilalapat mo ang algorithm na ito upang mahanap ang GCD ng tatlong numero at ang LCM ng dalawang numero.

Takdang aralin.

1. Sumulat ng isang programa upang mahanap ang pinakamalaking karaniwang divisor ng tatlong numero gamit ang sumusunod na formula:

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

2. Sumulat ng programa para sa paghahanap ng least common multiple (LCM) ng dalawang numero gamit ang formula:

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

Paglalahad ng Problema Isaalang-alang ang sumusunod na problema: kinakailangan na magsulat ng isang programa para sa pagtukoy ng pinakamalaking karaniwang divisor (GCD) ng dalawang natural na numero. Alalahanin natin ang matematika. Ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking natural na bilang kung saan sila ay pantay na nahahati. Halimbawa, ang mga numero 12 at 18 ay may mga karaniwang divisors: 2, 3, 6. Ang pinakamalaking karaniwang divisor ay ang numero 6. Ito ay nakasulat tulad ng sumusunod: gcd(12,18) = 6. Tukuyin ang inisyal na data bilang M at N Ang pahayag ng problema ay ang mga sumusunod : Ibinigay: M, N Hanapin: GCD(M, N).

N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang." title="(!LANG:Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa property na kung M>N, pagkatapos ay gcd(M,N) = gcd( M - N, N) Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero." class="link_thumb"> 4 !} Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa pag-aari na kung M>N, pagkatapos GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero. N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang."> N, pagkatapos ay gcd(M,N) = gcd(M - N,N). Sa madaling salita, ang Ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at mas maliit na numero."> N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang." title="(!LANG:Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa property na kung M>N, pagkatapos ay gcd(M,N) = gcd( M - N, N) Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero."> title="Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa pag-aari na kung M>N, pagkatapos GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero."> !}

N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), na nagpapahiwatig na ang K ay isang divisor ng M - N. Samakatuwid, ang lahat ng karaniwang divisors ng M at N ay mga divisors" title="(!LANG:Proof Let K be a common divisor ng M at. N (M > N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m> n. Pagkatapos M - N = K(m - n), kung saan ito sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors" class="link_thumb"> 5 !} Patunay Hayaan ang K na maging karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), kung saan sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors ng kanilang pagkakaiba M - N, kabilang ang pinakamalaking karaniwang divisor. Kaya naman: GCD(M,N) = GCD(M - N,N). Ang pangalawang halatang property: GCD(M,M) = M. N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N \u003d K (m - n), kung saan sumusunod na ang K ay isang divisor ng numero M - N. Samakatuwid, ang lahat ng mga karaniwang divisors ng mga numerong M at N ay mga divisors "\u003e N). Nangangahulugan ito na M \u003d mK, N \u003d pK , kung saan ang m, n ay mga natural na numero, at m > n. Pagkatapos M - N = K(m - n), kung saan sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors ng kanilang pagkakaiba M-N, kabilang ang pinakamalaking common divisor. Kaya: GCD(M, N) = GCD(M - N, N). Ang pangalawang halatang property: GCD(M) , M) = M."> N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), na nagpapahiwatig na ang K ay isang divisor ng M - N. Samakatuwid, ang lahat ng karaniwang divisors ng M at N ay mga divisors" title="(!LANG:Proof Let K be a common divisor ng M at. N (M > N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m> n. Pagkatapos M - N = K(m - n), kung saan ito sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors"> title="Patunay Hayaan ang K na maging karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N \u003d K (m - n), na nagpapahiwatig na ang K ay isang divisor ng numero M - N. Samakatuwid, ang lahat ng mga karaniwang divisors ng mga numero M at N ay mga divisors"> !}

Programa sa Pascal Program Evklid; var M, N: integer; simulan writeln("Ipasok ang M at N"); readln(M,N); habang ang MN ay nagsisimula kung M>N pagkatapos M:=M-N iba pa N:=N-M dulo; write("HOD=",M) dulo. N pagkatapos M:=M-N iba N:=N-M dulo; write("HOD=",M) end."> N tapos M:=M-N iba N:=N-M end; write("HOD=",M) end."> N tapos M:=M-N iba N:=N-M wakas; write("HOD=",M) end." title="(!LANG:Pascal program 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 pagkatapos M:=M-N iba N:=N-M dulo; write("HOD=",M) end." title="(!LANG:Pascal program 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."> !}

slide 1

slide 2

ALGORITHM NG EUCLID Ang algorithm ng Euclid ay isang algorithm para sa paghahanap ng pinakamalaking karaniwang divisor (GCD) ng dalawang hindi negatibong integer. Euclid (365-300 BC) Tinawag ng mga sinaunang Greek mathematician ang algorithm na ito na ἀνθυφαίρεσις o ἀνταναίρεσις - "mutual subtraction".

slide 3

Pagkalkula GCD GCD = ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking bilang kung saan ang parehong orihinal na mga numero ay nahahati nang walang natitira. gcd(a, b)= gcd(a-b, b)= gcd(a, b-a) Palitan ang mas malaki sa dalawang numero ng pagkakaiba sa pagitan ng mas malaki at mas maliit hanggang sa magkapantay ang mga ito. Ito ay NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27)=gcd(18, 9) ==gcd(9,9)=9 Halimbawa:

slide 4

STEP Operation M N Kondisyon 1 InputM 48 2 InputN 18 3 M N 48 18,oo 4 M>N 48>18,oo 5 M:=M-N 30 6 M N 30 18,oo 7 M>N 30>18,oo 8 M:= M-N 12 9 M N 12 18 oo 10 M>N 12>18 hindi 11 N:=N-M 6 12 M N 12 6 oo 13 M>N 12>6 oo 14 M:=M-N 6 15 M N 6 6 hindi 16 KonklusyonM

slide 5

programa Evklid; var m, n: integer; simulan writeln("vved 2 numero"); readln(m,n); habang mn magsisimula kung m>n pagkatapos m:=m-n iba n:=n-m; wakas; write("nod=",m); matapos basahin.

slide 6

0. Patakbuhin ang Evklid program sa computer. Subukan ito ng M=32, N=24; M=696, N=234. 1. Suriin kung ang dalawang ibinigay na numero ay coprime. Tandaan. Dalawang numero ang tinatawag na relatibong prime kung ang kanilang pinakamalaking karaniwang divisor ay 1. 2. Hanapin ang least common multiple (LCM) ng mga numero n at m kung LCM(n, m) = n * m / gcd(n, m). 3. Ibinigay ang mga natural na bilang na m at n. Maghanap ng mga natural na numerong p at q na walang karaniwang divisors na p / q = m / n. 4. Hanapin ang GCD ng tatlong numero. Tandaan. gcd(a, b, c)= gcd(gcd(a, b), c) Mga Gawain

Slide 7

Euclid, sinaunang Greek mathematician. Nagtrabaho sa Alexandria noong ika-3 siglo. BC e. Ang pangunahing gawain na "Mga Simula" (15 mga libro), na naglalaman ng mga pundasyon ng sinaunang matematika, elementarya na geometry, teorya ng numero, pangkalahatang teorya ng mga relasyon at ang pamamaraan para sa pagtukoy ng mga lugar at volume, na kasama ang mga elemento ng teorya ng mga limitasyon. Malaki ang impluwensya niya sa pag-unlad ng matematika. Gumagana sa astronomiya, optika, teorya ng musika.

Pagtatanghal para sa trabaho ng bilog na Euclidean algorithm. Pagtatanghal sa paksang "Euclid's algorithm". Ideya ng algorithm ni Euclid

Mga slide caption:

Preview:

Paksa: "Euclid's Algorithm"

Oras ng pag-aayos

Pag-update ng kaalaman.