Euklids algoritme. Euklids algoritmepresentasjon for leksjonen informatikk og IKT (grad 9) om emnet Emne: Euklids algoritme for å finne GCD


Forklaring av problemet Tenk på følgende problem: det er nødvendig å 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 divisorer: 2, 3, 6. Den største felles divisoren er tallet 6. Dette skrives som følger: gcd(12,18) = 6. Betegn startdataene som M og N Problemsetningen er som følger: Gitt: M, N Finn: GCD(M, N).




N, så GCD(M,N) = GCD(M - N,N). Med andre ord, gcd av to naturlige tall er lik gcd av deres positive forskjell og det mindre tallet." title="(!LANG:Ideen til algoritmen Ideen til denne algoritmen er basert på egenskapen at hvis M>N, så er gcd(M,N) = gcd( M - N, N) Med andre ord, gcd av to naturlige tall er lik gcd av deres positive forskjell og det mindre tallet." class="link_thumb"> 4 !} Ideen til 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 og det minste tallet. N, så GCD(M,N) = GCD(M - N,N). Med andre ord, gcd av to naturlige tall er lik gcd av deres positive forskjell og et mindre tall. et mindre tall."> N, så er GCD(M, N) = GCD(M - N, N). Med andre ord, gcd av to naturlige tall er lik gcd av deres positive forskjell og det mindre tallet." title="(!LANG:Ideen til algoritmen Ideen til denne algoritmen er basert på egenskapen at hvis M>N, så er gcd(M,N) = gcd( M - N, N) Med andre ord, gcd av to naturlige tall er lik gcd av deres positive forskjell og det mindre tallet."> title="Ideen til 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 og det minste tallet."> !}


N). Dette betyr at M = mK, N = pK, hvor m, n er naturlige tall, og m>n. Da er M - N = K(m - n), hvorav det følger at K er en divisor av M - N. Derfor er alle felles divisorer av M og N divisorer" title="(!LANG:Proof La K være en felles divisor av M og. N (M > N). Dette betyr at M = mK, N = pK, hvor m, n er naturlige tall, og m> n. Da er M - N = K(m - n), hvorav det følger at K er en divisor av tallet M - N. Derfor er alle felles divisorer for tallene M og N divisorer" class="link_thumb"> 5 !} Bevis La K være en felles deler av M og. N (M>N). Dette betyr at M = mK, N = pK, hvor m, n er naturlige tall, og m>n. Da er M - N = K(m - n), hvorav det følger at K er en divisor av tallet M - N. Derfor er alle felles divisorer for tallene M og N divisorer av deres forskjell M - N, inkludert den største felles deler. Derfor: GCD(M,N) = GCD(M - N,N). Den andre åpenbare egenskapen: GCD(M,M) = M. N). Dette betyr at M = mK, N = pK, hvor m, n er naturlige tall, og m>n. Deretter M - N \u003d K (m - n), hvorav det følger at K er en divisor av tallet M - N. Derfor er alle vanlige divisorer for tallene M og N divisorer "\u003e N). Dette betyr at M \u003d mK, N \u003d pK , der m, n er naturlige tall, og m > n. Da er M - N = K(m - n), hvorav det følger at K er en divisor av tallet M - N. Derfor er alle felles divisorer for tallene M og N divisorer av deres forskjell M-N, inkludert den største felles divisor. Derfor: GCD(M, N) = GCD(M - N, N). Den andre åpenbare egenskapen: GCD(M) , M) = M."> N). Dette betyr at M = mK, N = pK, hvor m, n er naturlige tall, og m>n. Da er M - N = K(m - n), hvorav det følger at K er en divisor av M - N. Derfor er alle felles divisorer av M og N divisorer" title="(!LANG:Proof La K være en felles divisor av M og. N (M > N). Dette betyr at M = mK, N = pK, hvor m, n er naturlige tall, og m> n. Da er M - N = K(m - n), hvorav det følger at K er en divisor av tallet M - N. Derfor er alle felles divisorer for tallene M og N divisorer"> title="Bevis La K være en felles deler av M og. N (M>N). Dette betyr at M = mK, N = pK, hvor m, n er naturlige tall, og m>n. Deretter M - N \u003d K (m - n), som innebærer at K er en divisor av tallet M - N. Derfor er alle vanlige divisorer for tallene M og N divisorer"> !}








Program i Pascal Program Evklid; var M, N: heltall; begin writeln("Skriv inn M og N"); readln(M,N); mens MN begynner hvis M>N så M:=M-N ellers N:=N-M slutt; skriv("HOD=",M) slutt. N så M:=M-N ellers N:=N-M ende; skriv("HOD=",M) slutt."> N så M:=M-N annet N:=N-M slutt; skriv("HOD=",M) slutt."> N så M:=M-N annet N:=N-M slutt; write("HOD=",M) end." title="(!LANG:Pascal-programprogram Evklid; var M, N: heltall; start writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N så M:=M-N ellers N:=N-M ende; write("HOD=",M) end." title="(!LANG:Pascal-programprogram Evklid; var M, N: heltall; start writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}

lysbilde 1

lysbilde 2

EUCLIDS ALGORITME Euklids algoritme er en algoritme for å finne den største felles divisor (gcd) av to ikke-negative heltall. Euklid (365-300 f.Kr.) Gamle greske matematikere kalte denne algoritmen ἀνθυφαίρεσις eller ἀνταναίρεσις - "gjensidig subtraksjon".

lysbilde 3

Beregning GCD GCD = den største felles divisor av to naturlige tall er det største tallet som begge opprinnelige tallene er delbare med uten en rest. gcd(a, b)= gcd(a-b, b)= gcd(a, b-a) Erstatt det største av de to tallene med differansen mellom det større og det minste til de er like. Dette er NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27)=gcd(18, 9) ==gcd(9,9)=9 Eksempel:

lysbilde 4

TRINN Drift M N Tilstand 1 InngangM 48 2 InngangN 18 3 M N 48 18,ja 4 M>N 48>18,ja 5 M:=M-N 30 6 M N 30 18,ja 7 M>N 30>18,ja 8 M:= M-N 12 9 M N 12 18 ja 10 M>N 12>18 nei 11 N:=N-M 6 12 M N 12 6 ja 13 M>N 12>6 ja 14 M:=M-N 6 15 M N 6 6 nei 16 KonklusjonM

lysbilde 5

program Evklid; var m, n: heltall; begin writeln("vved 2 tall"); readln(m,n); mens mn begynner hvis m>n så m:=m-n ellers n:=n-m; slutt; skriv("nikk=",m); les slutt.

lysbilde 6

0.Kjør Evklid-programmet på datamaskinen. Test det med M=32, N=24; M=696, N=234. 1. Sjekk om to gitte tall er coprime. Merk. To tall kalles relativt primtall hvis deres største felles divisor er 1. 2. Finn det minste felles multiplum (LCM) av tallene n og m hvis LCM(n, m) = n * m / gcd(n, m). 3. Gitt naturlige tall m og n. Finn naturlige tall p og q uten felles divisorer slik at p / q = m / n. 4. Finn GCD for tre tall. Merk. gcd(a, b, c)= gcd(gcd(a, b), c) Oppgaver

Lysbilde 7

Euklid , gammel gresk matematiker. Jobbet i Alexandria på 300-tallet. f.Kr e. Hovedverket "Begynnelser" (15 bøker), som inneholder grunnlaget for eldgammel matematikk, elementær geometri, tallteori, generell teori om relasjoner og metoden for å bestemme områder og volumer, som inkluderte elementer fra teorien om grenser. Han hadde stor innflytelse på utviklingen av matematikken. Arbeider med astronomi, optikk, musikkteori.

Klasse: 6

Leksjonens mål:

  • fikse algoritmen for å finne den største felles divisor ved hjelp av faktorisering;
  • gjenta relaterte definisjoner og begreper;
  • introdusere elevene til Euklid-algoritmen;
  • å danne ferdighetene til matematisk kultur

Utstyr: datamaskin, projektor, lerret.

I løpet av timene

1. Organiseringsmoment (kontrollere elevenes beredskap for timen, markering fraværende) (1 min)

2. Muntlig arbeid: (6 min)

1. Erstatt produktet med en grad:

    d) a * a * a * a * a

  1. Regn ut: 2 3 ; 52; 3 3; 10 4 .
  2. Finn verdien av uttrykket: (3?3?5?11): (3?11). Hvilken konklusjon kan man trekke?
  3. Utfør deling en på b hvis a=170, b=35. Skriv ned likheten, hva som er lik a.

    4. Skriv denne likheten i generell form: a vil være delelig, og b vil være en divisor. La kvotienten være q og resten r, så: a = bq + r , og q kan enten være et naturlig tall eller null. Kan r være et hvilket som helst tall? [ r er et naturlig tall, og 0 < r < b .] Hva kan sies om tallene a og b hvis r = 0? Heltallsdivisjon er et spesielt tilfelle av divisjon med en rest.

  4. Finn ut og forklar om tallet a er delelig med tallet b uten en rest hvis:

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

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

b = 2 7 * 3 * 5 4

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

b = 2 * 3 3 * 5 * 11.

3. Oppdatering av grunnleggende kunnskap(10 min)

1) Spørsmål:

Hva er en talldeler en ?

Hva er et primtall?

Hva betyr det å faktorisere et tall i primfaktorer?

Formuler tegn på delbarhet med 2, 3, 5, 9,10;

Gi et eksempel på et enkeltsifret sammensatt tall;

Er det sant at tallet 77 er et primtall?

Hvorfor, hvis ett tall kan dekomponeres i 2 primfaktorer, og det andre i 3 primfaktorer, så er ikke disse tallene like?

Hvilket tall, primtall eller sammensatt, er produktet av to primtall?

Hva er den største felles divisor av to eller flere tall?

Hvilke tall kalles coprime?

Gjenta måter å finne GCD: Det finnes forskjellige algoritmer for å finne GCD for naturlige tall.

1 vei: Hvis to tall er gitt og de er relativt små, er den beste algoritmen brute-force-søk. Men for store tall, finn gcd(a;b) ved å liste opp alle divisorene til tallene en og b Prosessen er arbeidskrevende og upålitelig.

Det er nyttig å huske at gcd for et hvilket som helst antall tall ikke overskrider det minste av dem.

2-veis: ved å faktorisere tall (mest vanlig) (vedlegg, lysbilde1)

2) Regn ut GCD for tallene 24 og 16.

3) Faktoriser tallene: 875 og 8000 og beregn GCD for disse tallene.

(Bruk tallet 8000 som eksempel, gjenta en enklere metode for å faktorisere tall som slutter på null: siden 10=2 *5, deretter 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 *5 3)

4) Kan GCD av tre tall være lik 15 hvis produktet deres er lik 3000? [ Nei, fordi

15 \u003d 3 * 5, noe som betyr at tallet 3 må inkluderes i utvidelsen av hvert av de tre tallene. Men, 3000 = 2 3 * 3 * 5 3 .]

5) R spise oppgaven«Lærebøker ble tatt med til klassen: 24 i matematikk, 36 i historie og 48 i geografi.Hva er det største antallet sett som kan lages av disse bøkene slik at hver inneholder like mange bøker i matematikk, historie og geografi? Hvor mange bøker vil det være i hvert sett?"

4. Verifikasjonsarbeid (vedlegg, lysbilde 2) (6 min)

5. Lære nytt materiale (10 min)

Lærer: Den studerte metoden for å finne GCD(a, b) er enkel, forståelig og praktisk, men den har en betydelig ulempe: hvis de gitte tallene er store, og til og med ikke veldig lett å faktorisere, er oppgaven med å finne GCD(a, b) blir ganske vanskelig. I tillegg kan det vise seg at etter å ha jobbet hardt, vil vi sørge for at GCD(a, b) = 1 og det ser ut til at alt arbeidet er gjort forgjeves.

Euclid fant en fantastisk måte å finne gcd(a, b) uten noen forbehandling av tallene. (Vedlegg, lysbilde 3 og 4) Deretter ble denne algoritmen kjent som Euklids algoritme)

La oss bli kjent med Euclid-algoritmen. La det kreves å finne gcd(102;84). Del ett tall med et annet og finn resten.

La oss nå gjøre den samme operasjonen for tallene 84 og 18:

Neste trinn er for 18 og 12:

Nå - for 12 og 6:

0-rest. Prosessen er avsluttet.

Denne prosessen kan ikke være uendelig, fordi restene avtar, blir igjen ikke-negative heltall, hvis sett, som kjent, er avgrenset nedenfra:

84 >18 > 12> 6 >0

Hvis du ser nøye på de skriftlige likhetene, kan du fastslå at GCD for alle tallpar er lik hverandre (inviter elevene til å tenke - hvorfor?),

dvs. gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. Men tallet 6 er den siste ikke-0-resten .

Faktisk, hvis c er en vilkårlig felles divisor av tallene a og b, så er r = a - bq delelig med c; og omvendt, hvis c er en vilkårlig felles deler av b og r, så er a delelig med c. Det vil si at alle felles divisorer av parene (a; b) og (b; r) faller sammen, og dermed er deres største felles divisorer også sammenfallende.

Bekvemmeligheten med Euklids algoritme blir spesielt merkbar hvis vi bruker formen til notasjonen i form av en tabell:

I dette nettbrettet blir de opprinnelige tallene først skrevet ned, delt inn i tankene, resten skrives til høyre og private nederst, til prosessen avsluttes. Den siste divisoren er GCD.

Dermed er den største felles divisor av to tall den siste, ikke lik 0, resten når man deler et større tall med et mindre, dvs. hvis a = b*q + r, deretter gcd(a; b) = gcd(b; r)

Denne sekvensen av operasjoner kalles Euklids algoritme. Denne algoritmen lar deg finne GCD for tall uten å faktorisere dem (vedlegg, lysbilde 5)

6. Øvelser (10 min)

1. Det er tilrådelig å vurdere et eksempel. La det være nødvendig å finne GCD for tallene 323 og 437. Det er ikke lett å gjøre dette ved å velge eller dekomponering i primfaktorer, siden ingen av disse tallene er et multiplum av 2, 3, 5, 7, 11. Vi fortsetter følgende (

For å bruke forhåndsvisningen av presentasjoner, opprett en konto for deg selv ( regnskap) Google og logg på: https://accounts.google.com


Bildetekster:

Euklids algoritme Euklid , gammel gresk matematiker. Jobbet i Alexandria på 300-tallet. f.Kr e. Hovedverket "Begynnelser" (15 bøker), som inneholder grunnlaget for eldgammel matematikk, elementær geometri, tallteori, generell teori om relasjoner og metoden for å bestemme områder og volumer, som inkluderte elementer fra teorien om grenser. Han hadde stor innflytelse på utviklingen av matematikken. Arbeider med astronomi, optikk, musikkteori. Euklid (365–300 f.Kr.)

EUCLIDS ALGORITME Euklids algoritme er en algoritme for å finne den største felles divisor (gcd) av to ikke-negative heltall. Euklid (365-300 f.Kr.) Gamle greske matematikere kalte denne algoritmen ἀνθυφαίρεσις eller ἀνταναίρεσις - "gjensidig subtraksjon".

Beregning GCD GCD = den største felles divisor av to naturlige tall er det største tallet som begge opprinnelige tallene er delbare med uten en rest. gcd(a, b)= gcd(a-b, b)= gcd(a, b-a) Bytt ut det største av de to tallene med differansen mellom det større og det minste til de er like. Dette er NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Eksempel:

TRINN Drift M N Tilstand 1 Inngang M 48 2 Inngang N 18 3 M  N 48 18, ja 4 M>N 48>18, ja 5 M:=M-N 30 6 M  N 30  18, ja 30 M>N >18, ja 8 M:=M-N 12 9 M  N 12 18, ja 10 M>N 12 >18, nei 11 N:=N-M 6 12 M  N 12  6, ja 13 M>N 12 > , ja 14 M:=M-N 6 15 M  N 6  6, nei 16 Utgang M

program Evklid ; var m, n: heltall; begin writeln("vved 2 chisla"); readln(m,n); mens mn begynner hvis m>n så m:=m-n ellers n:= n-m ; slutt; skriv("nikk=",m); les slutt.

0.Kjør Evklid-programmet på datamaskinen. Test det med M=32, N=24; M=696, N=234. en . Sjekk om to gitte tall er coprime. Merk. To tall sies å være coprime hvis deres største felles divisor er 1. 2 . Finn det minste felles multiplum (LCM) av tallene n og m hvis LCM(n, m) = n * m / gcd(n, m). 3. Naturlige tall m og n er gitt. Finn naturlige tall p og q som ikke har felles deler slik at p / q = m / n . 4. Finn GCD for tre tall. Merk. GCD(a , b , c)= GCD(gcd(a , b), c) Oppgaver

Forhåndsvisning:

Emne: "Euklids algoritme"

Leksjonens mål:

  1. Pedagogisk:
  1. lær hvordan du bruker Euclid-algoritmen for å finne gcd-en til to og tre tall
  2. konsolidere ferdigheter i å bruke de algoritmiske strukturene "Branching" og "Cycle"
  3. få erfaring med å skrive og feilsøke programmer i programmeringsspråket Pascal
  1. Pedagogisk:
  1. dannelse av uavhengighet og ansvar i studiet av nytt materiale
  1. Utvikler:
  1. utvikling av oppmerksomhet og analytisk tenkning

Timeplan:

  1. Organisering av tid
  2. Kunnskapsoppdatering
  3. Forklaring av det nye temaet
  4. Praktisk del
  5. Oppsummering av leksjonen
  6. Hjemmelekser.

Organisering av tid

Hilsener. Hvem er fraværende. Antall. Leksjonens tema. Spørsmål om lekser.

Kunnskapsoppdatering.

Spørsmål:

Hvilke typer algoritmiske strukturer kjenner du til?

Hva er en lineær struktur? (Bl-sh)

Hva er en forgreningsstruktur? (Bl-sh)

Hva er en syklisk struktur? (Bl-sh)

Hvilke typer sykluser kjenner du til?

Hvordan implementeres en loop med et kjent antall repetisjoner i programmeringsspråket Pascal?

Hvordan implementeres en loop med et ukjent antall repetisjoner i programmeringsspråket Pascal?

Forklaring av et nytt emne (presentasjon)

Om Euklid;

Ideen om Euklids algoritme

Ideen til denne algoritmen er basert på:

1. 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.

Bevis: la K være en felles deler av M og N (M > N). Dette betyr at M \u003d mK, N \u003d nK, hvor m, n er naturlige tall, og m > n. Deretter M - N \u003d K (m - n), som innebærer at K er en divisor av tallet M - N. Derfor er alle felles divisorer for tallene M og N divisorer av deres forskjell M - N, inkludert den største felles deler.

2. Andre åpenbare egenskap:

GCD(M, M) = M.

For "manuell" telling ser Euclids algoritme slik ut:

1) hvis tallene er like, ta noen av dem som et svar, ellers fortsett algoritmen;

2) erstatt det største tallet med forskjellen mellom det største og minste av tallene;

3) gå tilbake til gjennomføringen av paragraf 1.

Blokkdiagram av Euclid-algoritmen

Program i JS Pascal

program Evklid;

var m, n: heltall;

begynne

writeln("vved 2 tall");

readln(m,n);

Mens mn gjør

Begynne

Hvis m>n

Deretter m:=m-n

Ellers n:=n-m;

slutt;

Skriv("nikk=",m);

lesln

slutt.

Praktisk del

Spørsmål og oppgaver:

  1. Kjør Evklid-programmet på datamaskinen din. Test den på M=32, N=24; M = 696, N = 234.
  2. Sjekk om to gitte tall er coprime. Merk. To tall sies å være coprime hvis deres største felles divisor er 1.

Oppsummering av leksjonen

I dag i leksjonen ble vi kjent med Euclid-algoritmen, som lar oss finne GCD for to ikke-negative heltall, vi skrev et program i Pascal-programmeringsspråket som implementerer denne algoritmen. Hjemme vil du motta en oppgave der du bruker denne algoritmen for å finne GCD for tre tall og LCM for to tall.

Hjemmelekser.

1. 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)

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

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

 

Det kan være nyttig å lese: