Utvikle et blokkdiagram for å finne den euklidiske algoritmen. Euklidisk algoritme

Euklids algoritme er en algoritme for å finne den største felles divisor (GCD) av et par heltall.

Største felles deler (GCD) er et tall som deler to tall uten en rest og selv er delelig uten en rest med en annen divisor av de gitte to tallene. Enkelt sagt er dette det største tallet som to tall som det søkes etter gcd for kan deles med uten en rest.

Algoritme for å finne GCD ved divisjon

1. Del det største tallet med det minste tallet.
2. Hvis det er delt uten en rest, er det minste tallet GCD (du bør avslutte syklusen).
3. Hvis det er en rest, erstatter du det største tallet med resten av divisjonen.
4. La oss gå videre til punkt 1.

Eksempel:
Finn gcd for 30 og 18.
30 / 18 = 1 (resten 12)
18 / 12 = 1 (resten 6)
12/6 = 2 (resten 0)
Slutt: GCD er en deler av 6.
GCD(30; 18) = 6

a = 50 b = 130 mens a != 0 og b != 0 : hvis a > b: a = a % b annet : b = b % a print (a + b)

I loopen skrives resten av divisjonen til variabelen a eller b. Sløyfen avsluttes når minst én av variablene er null. Dette betyr at den andre inneholder en gcd. Vi vet imidlertid ikke nøyaktig hvilken. Derfor finner vi summen av disse variablene for GCD. Siden en av variablene er null, har den ingen effekt på resultatet.

Algoritme for å finne GCD ved subtraksjon

1. Trekk det minste tallet fra det større tallet.
2. Hvis resultatet er 0, betyr det at tallene er like med hverandre og er GCD (du bør gå ut av loopen).
3. Hvis resultatet av subtraksjon ikke er lik 0, erstatter du det større tallet med resultatet av subtraksjonen.
4. La oss gå videre til punkt 1.

Eksempel:
Finn gcd for 30 og 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Slutt: GCD er en minuend eller subtrahend.
GCD(30; 18) = 6

a = 50 b = 130 mens a != b: hvis a > b: a = a - b annet : b = b - a utskrift (a)

Euklids algoritme

Største felles deler

Tenk på følgende problem: du må skrive et program for å bestemme den største felles divisor (GCD) av to naturlige tall.

La oss huske matematikk. Den største felles deleren av to naturlige tall er det største naturlige tallet som de er jevnt delbare med. For eksempel har tallene 12 og 18 felles faktorer: 2, 3, 6. Den største felles faktoren er tallet 6. Dette skrives slik:

GCD(12; 18) = 6.

La oss betegne de første dataene som M u N. Problemstillingen er som følger:
Gitt: M, N
Finne: GCD(M, N).

I dette tilfellet er det ikke nødvendig med ytterligere matematisk formalisering. Selve problemformuleringen er av formell matematisk karakter. Det er ingen formel for å beregne GCD(M, N) fra verdiene til M og N. Men for ganske lenge siden, lenge før fremkomsten av datamaskiner, var en algoritmisk metode for å løse dette problemet kjent. Det heter Euklidisk algoritme .

Ideen om den euklidiske algoritmen

Ideen til denne algoritmen er basert på egenskapen at hvis M>N, så

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

Med andre ord, gcd av to naturlige tall er lik gcd av deres positive forskjell (modulen til forskjellen deres) og det mindre tallet.

Det er lett å bevise denne egenskapen. La K være felles deler av M u N (M> N). Dette betyr at M = mK, N = nK, hvor m, n er naturlige tall, og m > n. Da er M - N = K(m - n), som betyr at K er en divisor av tallet M - N. Dette betyr at alle felles divisorer for tallene M og N er divisorer av deres forskjell M - N, inkludert den største felles deler.

Den andre åpenbare egenskapen:

GCD(M, M) = M.

For "manuell" telling ser den euklidiske algoritmen slik ut:

1) hvis tallene er like, ta noen av dem som svaret, ellers fortsett å utføre algoritmen;

2) erstatt det største tallet med forskjellen mellom det større og mindre tallet;

3) gå tilbake til trinn 1.

La oss vurdere denne algoritmen ved å bruke eksempelet M=32, N=24:

Strukturen til algoritmen er en while-løkke med nestet forgrening. Syklusen gjentas til verdiene til M og N er lik hverandre. Ved forgrening erstattes den største av de to verdiene med forskjellen deres.

Se nå på sporingstabellen til algoritmen for startverdiene M = 32, N = 24.

Skritt	Operasjon	M	N	Betingelse
1	input M	32
2	input N		24
3	M¹N			32 nr 24, ja
4	M>N			32>24, ja
5	M:=M-N	8
6	M¹N			8¹24, ja
7	M>N			8>24, nr
8	N:=N-M		16
9	M¹N			8¹16, ja
10	M>N			8>16, nr
11	N:=N-M		8
12	M¹N			8¹8, nei
13	pinne M	8
14	slutt

Til slutt ble resultatet riktig.

Program i AY og Pascal

La oss skrive algoritmen i AY og programmet i Pascal.

Spørsmål og oppgaver

1. Kjør Evklid-programmet på datamaskinen. Test den på verdiene M = 32, N = 24; M = 696, N = 234.

2. Skriv et program for å finne den største felles divisor av tre tall ved å bruke følgende formel:

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

3. Skriv et program for å finne det minste felles multiplum (LCM) av to tall ved å bruke formelen:

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

I forordet til sin første utgave «In the Kingdom of Genuity» (1908) skriver E. I. Ignatiev: «... intellektuelt initiativ, kvikkvittighet og «oppfinnsomhet» kan ikke «bores» inn i noens hode. Resultatene er pålitelige bare når introduksjonen til matematisk kunnskap gjøres på en enkel og behagelig måte, ved å bruke gjenstander og eksempler fra vanlige og hverdagslige situasjoner, valgt med passende vidd og underholdning.»

I forordet til 1911-utgaven "The Role of Memory in Mathematics" E.I. Ignatiev skriver "... i matematikk er det ikke formlene som skal huskes, men prosessen med å tenke."

For å trekke ut kvadratroten, er det tabeller med kvadrater for tosifrede tall, du kan faktorisere tallet til primfaktorer og trekke ut kvadratroten av produktet. En tabell med kvadrater er noen ganger ikke nok å trekke ut roten ved å faktorisere er en tidkrevende oppgave, som heller ikke alltid fører til ønsket resultat. Prøv å ta kvadratroten av 209764? Faktorering i primfaktorer gir produktet 2*2*52441. Ved prøving og feiling, utvalg - dette kan selvfølgelig gjøres hvis du er sikker på at dette er et heltall. Metoden jeg vil foreslå lar deg ta kvadratroten uansett.

En gang i tiden på instituttet (Perm State Pedagogical Institute) ble vi introdusert for denne metoden, som jeg nå vil snakke om. Jeg lurte aldri på om denne metoden hadde et bevis, så nå måtte jeg utlede noe av beviset selv.

Grunnlaget for denne metoden er sammensetningen av tallet =.

=&, dvs. & 2 =596334.

1. Del tallet (5963364) i par fra høyre til venstre (5`96`33`64)

2. Trekk ut kvadratroten av den første gruppen til venstre ( - nummer 2). Slik får vi det første sifferet i &.

3. Finn kvadratet til det første sifferet (2 2 =4).

4. Finn forskjellen mellom den første gruppen og kvadratet på det første sifferet (5-4=1).

5. Vi tar ned de to neste sifrene (vi får tallet 196).

6. Doble det første sifferet vi fant og skriv det til venstre bak linjen (2*2=4).

7. Nå må vi finne det andre sifferet i tallet &: dobbelt det første sifferet vi fant blir titallet i tallet, som når multiplisert med antall enere, må du få et tall mindre enn 196 (dette er tallet 4, 44*4=176). 4 er det andre sifferet i &.

8. Finn forskjellen (196-176=20).

9. Vi river neste gruppe (vi får tallet 2033).

10. Doble tallet 24, vi får 48.

Det er 11,48 tiere i et tall, når multiplisert med antall enere, bør vi få et tall mindre enn 2033 (484*4=1936). En-sifferet vi fant (4) er det tredje sifferet i tallet &.

Jeg har gitt bevis for følgende tilfeller:

1. Trekke ut kvadratroten av et tresifret tall;

2. Trekk ut kvadratroten av et firesifret tall.

Omtrentlig metoder for å trekke ut kvadratrøtter (uten å bruke kalkulator).

1. De gamle babylonerne brukte følgende metode for å finne den omtrentlige verdien av kvadratroten av tallet x. De representerte tallet x som summen a 2 + b, der a 2 er det nøyaktige kvadratet av det naturlige tallet a (a 2 ? x) nærmest tallet x, og brukte formelen . (1)

Ved å bruke formel (1), trekker vi ut kvadratroten, for eksempel fra tallet 28:

Resultatet av å trekke ut roten til 28 ved å bruke MK er 5.2915026.

Som du kan se, gir den babylonske metoden en god tilnærming til den nøyaktige verdien av roten.

2. Isaac Newton utviklet en metode for å trekke ut kvadratrøtter som dateres tilbake til Heron of Alexandria (ca. 100 e.Kr.). Denne metoden (kjent som Newtons metode) er som følger.

La en 1- den første tilnærmingen til et tall (som 1 kan du ta verdiene av kvadratroten av et naturlig tall - et eksakt kvadrat som ikke overstiger X).

Deretter mer nøyaktig tilnærming en 2 tall funnet av formelen .

Sirkelen viste hvordan du kan trekke ut kvadratrøtter i en kolonne. Du kan beregne roten med vilkårlig presisjon, finne et hvilket som helst antall sifre i dens desimalnotasjon, selv om det viser seg å være irrasjonelt. Algoritmen ble husket, men spørsmål gjensto. Det var ikke klart hvor metoden kom fra og hvorfor den ga riktig resultat. Det sto ikke i bøkene, eller kanskje jeg bare så i feil bøker. Til slutt, som mye av det jeg kan og kan i dag, kom jeg på det selv. Jeg deler min kunnskap her. Forresten, jeg vet fortsatt ikke hvor begrunnelsen for algoritmen er gitt)))

Så først forteller jeg deg "hvordan systemet fungerer" med et eksempel, og så forklarer jeg hvorfor det faktisk fungerer.

La oss ta et tall (nummeret ble tatt "ut av løse luften", det kom bare til tankene).

1. Vi deler tallene inn i par: de til venstre for desimaltegnet er gruppert to fra høyre til venstre, og de til høyre er gruppert to fra venstre til høyre. Vi får.

2. Vi trekker ut kvadratroten fra den første gruppen med tall til venstre - i vårt tilfelle er dette (det er klart at den nøyaktige roten kanskje ikke kan trekkes ut, vi tar et tall hvis kvadrat er så nært som mulig til tallet vårt dannet av første gruppe med tall, men overskrider den ikke). I vårt tilfelle vil dette være et tall. Vi skriver ned svaret - dette er det viktigste sifferet i roten.

3. Vi kvadrerer tallet som allerede er i svaret - dette - og trekker det fra den første tallgruppen til venstre - fra tallet. I vårt tilfelle gjenstår det.

4. Vi tildeler følgende gruppe med to tall til høyre: . Vi ganger tallet som allerede er i svaret med , og vi får .

5. Se nå nøye. Vi må tilordne ett siffer til tallet til høyre, og gange tallet med, det vil si med det samme tildelte sifferet. Resultatet skal være så nært som mulig, men igjen ikke mer enn dette tallet. I vårt tilfelle vil dette være nummeret, vi skriver det i svaret ved siden av, til høyre. Dette er det neste sifferet i desimalnotasjonen til kvadratroten vår.

6. Ved å trekke fra produktet får vi .

7. Deretter gjentar vi de kjente operasjonene: vi tildeler følgende gruppe sifre til høyre, multipliserer med , til det resulterende tallet > vi tildeler ett siffer til høyre, slik at når vi multipliserer med det, får vi et tall som er mindre enn , men nærmest til det - dette er neste siffer i desimalrotnotasjon.

Beregningene vil bli skrevet som følger:

Og nå den lovede forklaringen. Algoritmen er basert på formelen

Kommentarer: 51

1. 2 Anton:

   For kaotisk og forvirrende. Ordne alt punkt for punkt og nummer dem. Pluss: forklar hvor vi erstatter de nødvendige verdiene i hver handling. Jeg har aldri beregnet en rotrot før; jeg hadde vanskelig for å finne ut av det.

2. 5 Julia:

3. 6 :

   Yulia, 23 er for øyeblikket skrevet til høyre. Dette er de to første (til venstre) sifrene i roten som allerede er mottatt i svaret. Multipliser med 2 i henhold til algoritmen. Vi gjentar trinnene beskrevet i punkt 4.

4. 7 zzz:

   feil i "6. Fra 167 trekker vi produktet 43 * 3 = 123 (129 nada), vi får 38."
   Jeg forstår ikke hvordan det viste seg å være 08 etter desimaltegnet...

5. 9 Fedotov Alexander:

   Og selv i pre-kalkulator-tiden ble vi undervist på skolen ikke bare kvadratroten, men også terningroten i en kolonne, men dette var mer kjedelig og møysommelig arbeid. Det var lettere å bruke Bradis-bord eller en glideregel, som vi allerede studerte på videregående.

6. 10 :

   Alexander, du har rett, du kan trekke ut røttene til store krefter i en kolonne. Jeg skal bare skrive om hvordan du finner terningroten.

7. 12 Sergei Valentinovich:

   Kjære Elizaveta Alexandrovna! På slutten av 70-tallet utviklet jeg en ordning for automatisk (dvs. ikke ved valg) beregning av quadra. root på Felix-tilleggsmaskinen. Hvis du er interessert, kan jeg sende deg en beskrivelse.

8. 14 Vlad aus Engelsstadt:

   (((trekker ut kvadratroten av kolonnen)))
   Algoritmen forenkles hvis du bruker 2. tallsystemet, som studeres i informatikk, men også er nyttig i matematikk. A.N. Kolmogorov presenterte denne algoritmen i populære forelesninger for skolebarn. Artikkelen hans kan bli funnet i "Chebyshev Collection" (Mathematical Journal, se etter en lenke til den på Internett)
   Si forresten:
   G. Leibniz lekte en gang med ideen om å gå over fra det 10. tallsystemet til det binære på grunn av dets enkelhet og tilgjengelighet for nybegynnere (barneskolebarn). Men å bryte etablerte tradisjoner er som å bryte en festningsport med pannen: det er mulig, men det er ubrukelig. Slik viser det seg, som ifølge den mest siterte skjeggete filosofen i gamle dager: alle døde generasjoners tradisjoner undertrykker de levendes bevissthet.

   Til neste gang.

9. 15 Vlad aus Engelsstadt:

   ))Sergey Valentinovich, ja, jeg er interessert...((

   Jeg vedder på at dette er en variant av "Felix" av den babylonske metoden for å trekke ut den firkantede ridderen ved å bruke metoden for suksessive tilnærminger. Denne algoritmen ble dekket av Newtons metode (tangensmetode)

   Jeg lurer på om jeg tok feil i prognosen min?

10. 18 :

    2Vlad aus Engelsstadt

    Ja, algoritmen i binær burde være enklere, det er ganske åpenbart.

    Om Newtons metode. Kanskje det er sant, men det er likevel interessant

11. 20 Kirill:

    Tusen takk. Men det er fortsatt ingen algoritme, ingen vet hvor den kom fra, men resultatet er riktig. TUSEN TAKK! Jeg har lett etter dette lenge)

12. 21 Alexander:

    Hvordan vil du trekke ut roten fra et tall der den andre gruppen fra venstre til høyre er veldig liten? for eksempel er alles favorittnummer 4.398.046.511.104. Etter den første subtraksjonen er det ikke mulig å fortsette alt i henhold til algoritmen. Vennligst forklar.

13. 22 Alexey:

    Ja, jeg kjenner denne metoden. Jeg husker at jeg leste den i boken "Algebra" i en gammel utgave. Så, analogt, utledet han selv hvordan man trekker ut kuberoten i en kolonne. Men der er det allerede mer komplisert: hvert siffer bestemmes ikke av ett (som for et kvadrat), men av to subtraksjoner, og selv der må du multiplisere lange tall hver gang.

14. 23 Artem:

    Det er skrivefeil i eksemplet med å trekke ut kvadratroten av 56789.321. Gruppen med tall 32 er tilordnet to ganger til tallene 145 og 243, i tallet 2388025 må den andre 8 erstattes med 3. Da skal siste subtraksjon skrives slik: 2431000 – 2383025 = 47975.
    I tillegg, når vi deler resten med den doble verdien av svaret (uten å ta hensyn til kommaet), får vi et ekstra antall signifikante sifre (47975/(2*238305) = 0,100658819...), som bør legges til svaret (√56789.321 = 238.305... = 238.305100659).

15. 24 Sergey:

    Tilsynelatende kom algoritmen fra Isaac Newtons bok "General Arithmetic eller en bok om aritmetisk syntese og analyse." Her er et utdrag fra den:

    OM Å UTTREKKE RØTTER

    For å trekke ut kvadratroten av et tall, bør du først og fremst plassere en prikk over sifrene, og begynne med enheter. Deretter bør du skrive i kvotienten eller radikalet tallet hvis kvadrat er lik eller nærmest i ulempe til tallene eller tallet foran det første punktet. Etter å ha subtrahert denne kvadraten, vil de gjenværende sifrene i roten bli funnet sekvensielt ved å dividere resten med to ganger verdien av den allerede ekstraherte delen av roten og subtrahere hver gang fra resten av kvadratet det sist funnet sifferet og dets tidoblede produkt med den navngitte divisoren.

16. 25 Sergey:

    Rett også tittelen på boken "Generell aritmetikk eller en bok om aritmetisk syntese og analyse"

17. 26 Alexander:

    Takk for interessant materiale. Men denne metoden virker for meg noe mer komplisert enn hva for eksempel en skoleelev trenger. Jeg bruker en enklere metode basert på å utvide en kvadratisk funksjon ved å bruke de to første derivertene. Formelen er:
    sqrt(x)= A1+A2-A3, hvor
    A1 er heltallet hvis kvadrat er nærmest x;
    A2 er en brøk, telleren er x-A1, nevneren er 2*A1.
    For de fleste tall som er påtruffet i et skolekurs er dette nok til å få resultatet nøyaktig til hundredelen.
    Hvis du trenger et mer nøyaktig resultat, ta
    A3 er en brøk, telleren er A2 i annen, nevneren er 2*A1+1.
    For å bruke det trenger du selvfølgelig en tabell med kvadrater med heltall, men dette er ikke et problem på skolen. Det er ganske enkelt å huske denne formelen.
    Det forvirrer meg imidlertid at jeg fikk A3 empirisk som et resultat av eksperimenter med et regneark, og jeg forstår ikke helt hvorfor dette medlemmet har dette utseendet. Kanskje du kan gi meg noen råd?

18. 27 Alexander:

    Ja, jeg har også vurdert disse betraktningene, men djevelen sitter i detaljene. Du skriver:
    "siden a2 og b skiller seg ganske lite." Spørsmålet er nøyaktig hvor lite.
    Denne formelen fungerer bra på tall i de andre ti og mye verre (ikke opptil hundredeler, bare opptil tideler) på tall i de ti første. Hvorfor dette skjer er vanskelig å forstå uten bruk av derivater.

19. 28 Alexander:

    Jeg vil avklare hva jeg ser som fordelen med formelen jeg foreslår. Det krever ikke den ikke helt naturlige inndelingen av tall i sifferpar, som erfaringsmessig ofte utføres med feil. Betydningen er åpenbar, men for en person som er kjent med analyse, er den triviell. Fungerer bra på tall fra 100 til 1000, som er de vanligste tallene man møter på skolen.

20. 29 Alexander:

    Forresten, jeg gravde litt og fant det eksakte uttrykket for A3 i formelen min:
    A3= A22 /2(A1+A2)

21. 30 vasil stryzhak:

    I vår tid, med den utbredte bruken av datateknologi, er spørsmålet om å trekke ut den firkantede ridderen fra et tall ikke verdt det fra et praktisk synspunkt. Men for matematikkelskere vil ulike alternativer for å løse dette problemet utvilsomt være av interesse. I skolens læreplan bør metoden for denne beregningen uten bruk av tilleggsmidler skje på linje med multiplikasjon og langdivisjon. Beregningsalgoritmen må ikke bare huskes, men også forståelig. Den klassiske metoden, presentert i dette materialet for diskusjon med avsløring av essensen, samsvarer fullt ut med kriteriene ovenfor.
    En betydelig ulempe med metoden foreslått av Alexander er bruken av en tabell med kvadrater av heltall. Forfatteren er taus om flertallet av tallene som er påtruffet i skolekurset. Når det gjelder formelen, liker jeg den generelt på grunn av den relativt høye nøyaktigheten til beregningen.

22. 31 Alexander:

    for 30 vasil stryzhak
    Jeg holdt ingenting stille. Tabellen med ruter skal visstnok være opp til 1000. I min tid på skolen lærte de det rett og slett utenat og det sto i alle matematikkbøkene. Jeg kalte dette intervallet eksplisitt.
    Når det gjelder datateknologi, brukes den ikke hovedsakelig i matematikktimer, med mindre temaet bruk av kalkulator er spesifikt diskutert. Kalkulatorer er nå innebygd i enheter som er forbudt for bruk på Unified State-eksamenen.

23. 32 vasil stryzhak:

    Alexander, takk for avklaringen. Jeg tenkte at for den foreslåtte metoden er det teoretisk nødvendig å huske eller bruke en tabell med kvadrater av alle tosifrede tall. Så for radikale tall som ikke er inkludert i intervallet fra 100 til 10000 bruk teknikken for å øke eller redusere dem med det nødvendige antallet størrelsesordener ved å flytte desimaltegnet.

24. 33 vasil stryzhak:

25. 39 ALEXANDER:

    MITT FØRSTE PROGRAM PÅ IAMB-SPRÅK PÅ DEN SOVJETISKE MASKINEN “ISKRA 555″ BLEV SKREVET FOR Å UTTREKKE KVADRATROTEN TIL ET NUMMER VED Å BRUKE ALGORITIMEN FOR KOLONNEUTTREKKING! og nå har jeg glemt hvordan jeg trekker det ut manuelt!