Eukleidilise algoritmi leidmiseks koostage plokkskeem. Eukleidiline algoritm

Eukleidese algoritm on täisarvude paari suurima ühisjagaja (GCD) leidmise algoritm.

Suurim ühine jagaja (GCD) on arv, mis jagab kahte arvu ilma jäägita ja jagub ise ilma jäägita antud kahe arvu ühegi teise jagajaga. Lihtsamalt öeldes on see suurim arv, millega saab kahte arvu, mille jaoks gcd otsitakse, ilma jäägita jagada.

Algoritm GCD leidmiseks jagamise teel

1. Jagage suurem arv väiksema arvuga.
2. Kui see jagatakse ilma jäägita, on väiksem arv GCD (peaksite tsüklist väljuma).
3. Kui on ülejääk, asendage suurem arv ülejäänud jaotusega.
4. Liigume edasi punkti 1 juurde.

Näide:
Leidke gcd 30 ja 18 jaoks.
30/18 = 1 (ülejäänud 12)
18/12 = 1 (ülejäänud 6)
12/6 = 2 (ülejäänud 0)
Lõpp: GCD on 6 jagaja.
GCD(30; 18) = 6

a = 50 b = 130, samas kui a != 0 ja b != 0 : kui a > b: a = a % b else : b = b % a print (a + b)

Tsüklis kirjutatakse jaotuse jääk muutujale a või b. Tsükkel lõpeb, kui vähemalt üks muutujatest on null. See tähendab, et teine ​​sisaldab gcd-d. Siiski me ei tea, milline neist täpselt. Seetõttu leiame GCD jaoks nende muutujate summa. Kuna üks muutujatest on null, ei mõjuta see tulemust.

Algoritm GCD leidmiseks lahutamise teel

1. Lahutage väiksem arv suuremast arvust.
2. Kui tulemus on 0, tähendab see, et arvud on üksteisega võrdsed ja on GCD (peaksite tsüklist väljuma).
3. Kui lahutamise tulemus ei ole 0, asendage suurem arv lahutamise tulemusega.
4. Liigume edasi punkti 1 juurde.

Näide:
Leidke gcd 30 ja 18 jaoks.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Lõpp: GCD on minuend või alamosa.
GCD(30; 18) = 6

a = 50 b = 130, samas kui a != b: kui a > b: a = a - b else : b = b - a print (a)

Eukleidese algoritm

Suurim ühine jagaja

Mõelge järgmisele probleemile: peate kirjutama programmi kahe naturaalarvu suurima ühisjagaja (GCD) määramiseks.

Meenutagem matemaatikat. Kahe naturaalarvu suurim ühisjagaja on suurim naturaalarv, millega need on võrdselt jagatavad. Näiteks arvudel 12 ja 18 on ühised tegurid: 2, 3, 6. Suurim ühine tegur on arv 6. See on kirjutatud järgmiselt:

GCD(12; 18) = 6.

Tähistame lähteandmeid kui M u N. Probleemi avaldus on järgmine:
Arvestades: M, N
Leia: GCD (M, N).

Sel juhul ei ole vaja täiendavat matemaatilist vormistamist. Ülesande sõnastus ise on formaalset matemaatilist laadi. Valemit GCD(M, N) arvutamiseks M ja N väärtustest ei ole olemas. Kuid üsna kaua aega tagasi, ammu enne arvutite tulekut, oli selle probleemi lahendamiseks tuntud algoritmiline meetod. Seda nimetatakse Eukleidiline algoritm .

Eukleidilise algoritmi idee

Selle algoritmi idee põhineb omadusel, et kui M>N, siis

GCD (M, N) = GCD (M - N, N).

Teisisõnu, kahe naturaalarvu gcd on võrdne nende positiivse erinevuse gcd-ga (nende erinevuse moodul) ja väiksema arvuga.

Seda omadust on lihtne tõestada. Olgu K väärtuse M u N (M> N) ühisjagaja. See tähendab, et M = mK, N = nK, kus m, n on naturaalarvud ja m > n. Siis M - N = K(m - n), mis tähendab, et K on arvu M - N jagaja. See tähendab, et kõik arvude M ja N ühised jagajad on nende erinevuse M - N jagajad, sealhulgas suurim. ühine jagaja.

Teine ilmne omadus:

GCD(M, M) = M.

"Käsitsi" loendamise jaoks näeb eukleidiline algoritm välja järgmine:

1) kui arvud on võrdsed, siis võta vastuseks ükskõik milline neist, vastasel juhul jätkake algoritmi täitmist;

2) asendada suurem arv suurema ja väiksema arvu vahega;

3) naaske 1. sammu juurde.

Vaatleme seda algoritmi, kasutades näidet M=32, N=24:

Algoritmi struktuur on pesastatud hargnemisega while-tsükkel. Tsüklit korratakse, kuni M ja N väärtused on üksteisega võrdsed. Hargnemisel asendatakse kahest väärtusest suurem nende erinevusega.

Nüüd vaadake algväärtuste M = 32, N = 24 algoritmi jälgimistabelit.

Samm	Operatsioon	M	N	Seisund
1	sisend M	32
2	sisend N		24
3	M¹N			32 nr 24, jah
4	M>N			32>24, jah
5	M: = M-N	8
6	M¹N			8¹24, jah
7	M>N			8>24, nr
8	N:=N-M		16
9	M¹N			8¹16, jah
10	M>N			8>16, nr
11	N:=N-M		8
12	M¹N			8¹8, nr
13	pin M	8
14	lõpp

Lõpuks oli tulemus õige.

Programm AY ja Pascal keeles

Kirjutame algoritmi AY-s ja programmi Pascalis.

Küsimused ja ülesanded

1. Käivitage arvutis programm Evklid. Katsetage seda väärtustel M = 32, N = 24; M = 696, N = 234.

2. Kirjutage programm kolme arvu suurima ühisjagaja leidmiseks järgmise valemi abil:

GCD(A, B, C) = GCD(GCD(A, B), C).

3. Kirjutage programm kahe arvu vähima ühiskordse (LCM) leidmiseks, kasutades valemit:

A × B = GCD(A, B) × GCD(A, B).

E. I. Ignatjev kirjutab oma esmaväljaande “Nuudluse kuningriigis” (1908) eessõnas: “... intellektuaalset initsiatiivi, kiiret vaimukust ja “leidlikkust” ei saa kellegi pähe “puurida” ega “sisse panna”. Tulemused on usaldusväärsed vaid siis, kui sissejuhatus matemaatiliste teadmiste valdkonda on tehtud lihtsal ja meeldival viisil, kasutades esemeid ja näiteid tavalistest ja igapäevastest olukordadest, mis on valitud sobiva vaimukuse ja meelelahutusega.

1911. aasta väljaande “Mälu roll matemaatikas” eessõnas E.I. Ignatjev kirjutab: "... matemaatikas ei tohiks meeles pidada valemeid, vaid mõtlemise protsess."

Ruutjuure eraldamiseks on kahekohaliste arvude jaoks ruutude tabelid; saate arvutada arvu algteguriteks ja eraldada korrutise ruutjuure. Ruudude tabelist mõnikord ei piisa, juure faktooringuga eraldamine on aeganõudev ülesanne, mis samuti ei vii alati soovitud tulemuseni. Proovige võtta ruutjuur arvust 209764? Algteguriteks faktoriteerimine annab korrutisele 2*2*52441. Katse-eksituse meetodil, valik - seda saab muidugi teha, kui olete kindel, et see on täisarv. Meetod, mida ma tahan välja pakkuda, võimaldab teil igal juhul võtta ruutjuure.

Kunagi instituudis (Permi Riiklik Pedagoogiline Instituut) tutvustati meile seda meetodit, millest ma nüüd tahan rääkida. Ma ei mõelnud kunagi, kas sellel meetodil on tõestus, nii et nüüd pidin osa tõestusest ise tuletama.

Selle meetodi aluseks on arvu = koostis.

=&, st. & 2 =596334.

1. Jagage arv (5963364) paarideks paremalt vasakule (5`96`33`64)

2. Ekstraheerige esimese vasakpoolse rühma ruutjuur ( - number 2). Nii saame & esimese numbri.

3. Leidke esimese numbri ruut (2 2 =4).

4. Leia vahe esimese rühma ja esimese numbri ruudu vahel (5-4=1).

5. Võtame maha järgmised kaks numbrit (saame numbri 196).

6. Kahekordistage esimene leitud number ja kirjutage see vasakule rea taha (2*2=4).

7. Nüüd peame leidma numbri & teise koha: kahekordistades leitud esimesest numbrist saab arvu kümnendkohaline number, mida ühikute arvuga korrutades peate saama arvu, mis on väiksem kui 196 (see on arv 4, 44*4=176). 4 on & teine ​​number.

8. Leia erinevus (196-176=20).

9. Lammutame järgmise rühma (saame numbri 2033).

10. Kahekordistame arvu 24, saame 48.

Arvus on 11,48 kümneid, korrutades üheliste arvuga, peaksime saama arvu, mis on väiksem kui 2033 (484*4=1936). Üks number, mille me leidsime (4) on arvu & kolmas number.

Olen esitanud tõendid järgmiste juhtumite kohta:

1. Kolmekohalise arvu ruutjuure eraldamine;

2. Neljakohalise arvu ruutjuure eraldamine.

Ligikaudsed meetodid ruutjuurte eraldamiseks (ilma kalkulaatorit kasutamata).

1. Vanad babüloonlased kasutasid oma arvu x ruutjuure ligikaudse väärtuse leidmiseks järgmist meetodit. Nad kujutasid arvu x summana a 2 + b, kus a 2 on arvule x lähima naturaalarvu a (a 2 ? x) täpne ruut ja kasutasid valemit . (1)

Kasutades valemit (1), eraldame ruutjuure näiteks arvust 28:

MK-ga 28 juure ekstraheerimise tulemus on 5.2915026.

Nagu näete, annab Babüloonia meetod juure täpsele väärtusele hea ligikaudse hinnangu.

2. Isaac Newton töötas välja meetodi ruutjuurte võtmiseks, mis pärineb Aleksandria Heronist (umbes 100 pKr). See meetod (tuntud kui Newtoni meetod) on järgmine.

Lase a 1- arvu esimene lähendus (1-na võite võtta naturaalarvu ruutjuure väärtused - täpne ruut, mis ei ületa X) .

Järgmiseks täpsem lähendus a 2 numbrid leitud valemiga .

Ring näitas, kuidas saate veerust ruutjuuri eraldada. Saate arvutada juure suvalise täpsusega, leida selle kümnendsüsteemis suvalise arvu numbreid, isegi kui see osutub irratsionaalseks. Algoritm jäi meelde, aga küsimused jäid. Ei olnud selge, kust meetod tuli ja miks see õige tulemuse andis. Seda polnud raamatutes või võib-olla ma lihtsalt otsisin valedest raamatutest. Lõpuks, nagu suur osa sellest, mida ma täna tean ja suudan, mõtlesin selle ise välja. Jagan siin oma teadmisi. Muide, ma ei tea ikka veel, kus on antud algoritmi põhjendus)))

Niisiis, kõigepealt räägin teile näitega, kuidas süsteem töötab, ja seejärel selgitan, miks see tegelikult töötab.

Võtame numbri (number on võetud "õhust", lihtsalt tuli meelde).

1. Jagame selle numbrid paarideks: koma vasakul olevad on rühmitatud kaks paremalt vasakule ja paremal olevad on rühmitatud kaks vasakult paremale. Saame.

2. Eraldame ruutjuure esimesest vasakpoolsest arvude rühmast - meie puhul on see nii (on selge, et täpset juurt ei pruugita välja võtta, võtame arvu, mille ruut on võimalikult lähedal meie arvule, mille moodustab esimene numbrirühm, kuid ei ületa seda). Meie puhul on see arv. Kirjutame vastuse üles - see on juure kõige olulisem number.

3. Me paneme ruutu, mis on juba vastuses - see - ja lahutame selle esimesest vasakpoolsest arvude rühmast - arvust. Meie puhul jääb see alles.

4. Määrame paremale järgmise kahe numbri rühma: . Korrutame vastuses juba oleva arvu arvuga ja saame .

5. Nüüd jälgige hoolikalt. Peame määrama paremal olevale numbrile ühe numbri ja korrutama selle numbriga, st sama määratud numbriga. Tulemus peaks olema sellele arvule võimalikult lähedane, kuid jällegi mitte suurem. Meie puhul on see number, kirjutame selle vastusesse kõrval, paremal. See on meie ruutjuure kümnendkoha järgmine number.

6. Korrutisest lahutada saame .

7. Järgmisena kordame tuttavaid tehteid: omistame paremale järgmise numbrirühma, korrutame saadud numbriga > omistame ühe numbri paremale, nii et sellega korrutades saame arvu, mis on väiksem kui , kuid lähim sellele – see on kümnendjuure tähistus järgmine number.

Arvutused kirjutatakse järgmiselt:

Ja nüüd lubatud selgitus. Algoritm põhineb valemil

Kommentaarid: 51

1. 2 Anton:

   Liiga kaootiline ja segane. Järjesta kõik punktide kaupa ja nummerda need. Pluss: selgitage, kus me igas toimingus nõutavad väärtused asendame. Ma pole kunagi varem juurjuurt arvutanud; mul oli raske seda välja mõelda.

2. 5 Julia:

3. 6 :

   Paremal on praegu kirjutatud Yulia, 23; need on vastuses juba saadud juure kaks esimest (vasakul) numbrit. Korrutage 2-ga vastavalt algoritmile. Kordame punktis 4 kirjeldatud samme.

4. 7 zzz:

   viga jaotises "6. 167-st lahutame korrutise 43 * 3 = 123 (129 nada), saame 38.
   Ma ei saa aru, kuidas pärast koma sai 08...

5. 9 Aleksander Fedotov:

   Ja isegi kalkulaatorieelsel ajal õpetati meile koolis mitte ainult ruutjuurt, vaid ka kuupjuurt veerus, kuid see oli tüütum ja vaevanõudvam töö. Lihtsam oli kasutada Bradise tabeleid või slaidireeglit, mida me juba keskkoolis õppisime.

6. 10 :

   Aleksander, sul on õigus, sa saad veergu eraldada suurte jõudude juured. Ma kirjutan just sellest, kuidas leida kuupjuurt.

7. 12 Sergei Valentinovitš:

   Kallis Elizaveta Aleksandrovna! 70ndate lõpus töötasin välja skeemi quadra automaatseks (st mitte valikuliseks) arvutamiseks. root Felixi lisamismasinas. Huvi korral võin kirjelduse saata.

8. 14 Vlad aus Engelsstadt:

   (((Veeru ruutjuure eraldamine)))
   Algoritm on lihtsustatud, kui kasutada 2. numbrisüsteemi, mida õpitakse informaatikas, kuid on kasulik ka matemaatikas. A.N. Kolmogorov tutvustas seda algoritmi populaarsetes kooliõpilaste loengutes. Tema artikli leiate Tšebõševi kogust (Mathematical Journal, otsige selle linki Internetist)
   Muide, ütle:
   G. Leibniz mängis omal ajal mõttega minna üle 10. numbrisüsteemilt kahendsüsteemile selle lihtsuse ja algajatele (algkoolilastele) juurdepääsetavuse tõttu. Kuid väljakujunenud traditsioonide rikkumine on nagu kindlusevärava lõhkumine laubaga: see on võimalik, kuid sellest pole kasu. Nii selgub, nagu vanasti enimtsiteeritud habemega filosoofi sõnul: kõigi surnud põlvkondade traditsioonid suruvad elavate teadvuse alla.

   Järgmise korrani.

9. 15 Vlad aus Engelsstadt:

   ))Sergei Valentinovitš, jah, olen huvitatud...((

   Vean kihla, et see on variatsioon „Felixi” Babüloonia meetodist, mille abil eraldati nelinurkne ratsu järjestikuste lähenduste meetodil. Seda algoritmi hõlmas Newtoni meetod (tangentmeetod)

   Huvitav, kas ma eksisin oma prognoosis?

10. 18 :

    2Vlad aus Engelsstadt

    Jah, kahendkoodi algoritm peaks olema lihtsam, see on üsna ilmne.

    Newtoni meetodi kohta. Võib-olla on see tõsi, kuid see on siiski huvitav

11. 20 Kirill:

    Tänud. Aga algoritmi ikka pole, keegi ei tea, kust see tuli, aga tulemus on õige. TÄNUD! Olen seda juba pikka aega otsinud)

12. 21 Aleksander:

    Kuidas eraldada juur arvust, kus teine ​​rühm vasakult paremale on väga väike? näiteks kõigi lemmiknumber on 4 398 046 511 104. Pärast esimest lahutamist ei ole võimalik kõike algoritmi järgi jätkata. Kas saate palun selgitada.

13. 22 Aleksei:

    Jah, ma tean seda meetodit. Mäletan, et lugesin seda mõne vana väljaande raamatust “Algebra”. Seejärel tegi ta ise analoogia põhjal järelduse, kuidas veerus kuupjuurt välja võtta. Kuid seal on see juba keerulisem: iga numbrit ei määra mitte üks (nagu ruudu puhul), vaid kaks lahutamist ja isegi seal peate iga kord pikki arve korrutama.

14. 23 Artem:

    Ruutjuure 56789.321 eraldamise näites on kirjavigu. Arvude rühm 32 omistatakse kahel korral numbritele 145 ja 243, arvus 2388025 tuleb teine ​​8 asendada 3-ga. Seejärel tuleb viimane lahutamine kirjutada järgmiselt: 2431000 – 2383025 = 47975.
    Lisaks saame jäägi jagamisel vastuse kahekordistunud väärtusega (ilma koma arvesse võtmata) täiendava arvu tähenduslikke numbreid (47975/(2*238305) = 0,100658819...), mis tuleks lisada vastus (√56789,321 = 238,305... = 238,305100659).

15. 24 Sergei:

    Ilmselt pärineb algoritm Isaac Newtoni raamatust "Üldine aritmeetika või raamat aritmeetilise sünteesi ja analüüsi kohta". Siin on väljavõte sellest:

    JUURTE VÄLJAVÕTMISEST

    Arvu ruutjuure eraldamiseks peate esmalt selle numbrite kohale asetama punkti, alustades numbritest. Seejärel tuleks jagatisesse või radikaali kirjutada arv, mille ruut on võrdne esimesele punktile eelnevate arvude või arvuga või neile kõige lähemal. Pärast selle ruudu lahutamist leitakse juure ülejäänud numbrid järjestikku, jagades jäägi kahekordse juba eraldatud juureosa väärtusega ja lahutades iga kord ruudu ülejäänud osast viimase leitud numbri ja selle kümnekordse korrutise nimetatud jagaja.

16. 25 Sergei:

    Parandage palun ka raamatu pealkiri “Üldne aritmeetika ehk raamat aritmeetilisest sünteesist ja analüüsist”

17. 26 Aleksander:

    Aitäh huvitava materjali eest. Kuid see meetod tundub mulle mõnevõrra keerulisem kui see, mida vajatakse näiteks koolilapse jaoks. Kasutan lihtsamat meetodit, mis põhineb ruutfunktsiooni laiendamisel kahe esimese tuletise abil. Selle valem on:
    sqrt(x)= A1+A2-A3, kus
    A1 on täisarv, mille ruut on x-le kõige lähemal;
    A2 on murd, lugeja on x-A1, nimetaja on 2*A1.
    Enamiku koolikursustel esinevate numbrite puhul piisab sellest, et saada tulemus sajandiku täpsusega.
    Kui vajate täpsemat tulemust, võtke
    A3 on murd, lugeja on A2 ruudus, nimetaja on 2*A1+1.
    Muidugi on selle kasutamiseks vaja täisarvude ruutude tabelit, kuid koolis pole see probleem. Selle valemi meeldejätmine on üsna lihtne.
    Mind ajab aga segadusse see, et sain A3 empiiriliselt arvutustabeliga tehtud katsete tulemusena ja ma ei saa päris hästi aru, miks sellel liikmel selline välimus on. Äkki oskate nõu anda?

18. 27 Aleksander:

    Jah, ma olen ka neid kaalutlusi kaalunud, kuid kurat peitub detailides. Sa kirjutad:
    "kuna a2 ja b erinevad üsna vähe." Küsimus on selles, kui vähe täpselt.
    See valem töötab hästi teise kümne numbriga ja palju halvemini (mitte kuni sajandikuteni, vaid kuni kümnendikuni) esimese kümne numbrite puhul. Miks see juhtub, on tuletisinstrumente kasutamata raske mõista.

19. 28 Aleksander:

    Selgitan, mida näen pakutud valemi eelisena. See ei nõua arvude mitte täiesti loomulikku jagamist numbripaarideks, mida, nagu kogemus näitab, tehakse sageli vigadega. Selle tähendus on ilmne, kuid analüüsiga kursis oleva inimese jaoks on see tühine. Töötab hästi numbritega 100 kuni 1000, mis on koolis kõige levinumad numbrid.

20. 29 Aleksander:

    Muide, uurisin veidi ja leidsin valemis A3 täpse väljendi:
    A3 = A22 /2 (A1 + A2)

21. 30 vasil stryzhak:

    Meie ajal, kui arvutitehnoloogia on laialdaselt kasutusel, ei ole ruutrüütli numbrist väljavõtmine praktilisest seisukohast seda väärt. Kuid matemaatikahuvilistele pakuvad selle probleemi lahendamiseks kahtlemata huvi mitmesugused võimalused. Kooli õppekavas peaks selle arvutuse meetod ilma lisaraha kasutamata toimuma samaväärselt korrutamise ja pika jagamisega. Arvutusalgoritm peab olema mitte ainult pähe õpitud, vaid ka arusaadav. Klassikaline meetod, mida selles materjalis käsitletakse koos olemuse avalikustamisega, vastab täielikult ülaltoodud kriteeriumidele.
    Aleksandri pakutud meetodi oluline puudus on täisarvude ruutude tabeli kasutamine. Autor vaikib enamiku koolikursustel ette tulnud numbrite kohta. Mis valemisse puutub, siis üldiselt meeldib see mulle suhteliselt suure arvutuse täpsuse tõttu.

22. 31 Aleksander:

    30 vasil stryzhak eest
    Ma ei vaikinud midagi. Ruudude tabel peaks olema kuni 1000. Minu kooliajal õpiti see lihtsalt pähe ja see oli kõigis matemaatikaõpikutes. Nimetasin selle intervalli selgesõnaliselt.
    Mis puutub arvutitehnoloogiasse, siis seda ei kasutata peamiselt matemaatikatundides, kui just kalkulaatori kasutamise teemat konkreetselt ei käsitleta. Kalkulaatorid on nüüd sisse ehitatud seadmetesse, mille kasutamine ühtse riigieksami ajal on keelatud.

23. 32 vasil stryzhak:

    Aleksander, tänan teid selgituse eest! Arvasin, et pakutud meetodi puhul on teoreetiliselt vaja meeles pidada või kasutada kõigi kahekohaliste arvude ruutude tabelit. Siis radikaalarvude puhul, mis ei sisaldu vahemikus 100 kuni 10 000, saate kasutada tehnikat, kuidas koma nihutades suurendada või vähendada neid vajaliku arvu suurusjärkude võrra.

24. 33 vasil stryzhak:

25. 39 Aleksander:

    MINU ESIMENE IAMB-KEELNE PROGRAMM NÕUKOGUDE MASINAS “ISKRA 555” OLI KIRJUTATUD ARVU RUUTJUURE VÄLJA VÄLJAVÕTMISEKS VEERU VÄLJAVÕTMISE ALGORITMI KASUTAMISEKS! ja nüüd ma unustasin, kuidas seda käsitsi ekstraktida!