Skaitļu teorijas un algebras. Algoritm

1.

J. Raiņa Daugavpils 6.vidusskola
Skaitļu teorijas un algebras
algoritmi
Nataļja Mikuļina
Eiklīda algoritms
Divu veselu skaitļu lielākā kopīgā
dalītāja (LKD) vērtības noteikšana

2.

Algoritma darbības princips
Eiklīda algoritms skaitļu teorijā ir paņēmiens
divu veselu skaitļu lielākā kopīgā dalītāja (LKD)
atrašanai, vispirms nepilni izdalot lielāko skaitli ar
mazāko un tad katrā nākamajā solī iepriekšējās
darbības dalītāju savukārt dalot ar iegūto atlikumu.
LKD ir pēdējais iegūtais nenulles atlikums.
Ievērojami ir tas, ka algoritmam nav
nepieciešams sadalīt skaitļus pirmreizinātājos, kā arī
tas, ka šis ir viens no vecākajiem zināmajiem
algoritmiem.

3.

Darbības piemērs
LKD(336,287) = ?
1) 336 : 287 = 1 atl. 49
2) 287 : 49 = 5 atl. 42
3) 49 : 42 = 1 atl. 7
4) 42 : 7 = 6 atl. 0
LKD(336,287) = 7

4.

J. Raiņa Daugavpils 6.vidusskola
Skaitļu teorijas un algebras
algoritmi
Eratostēna siets
Pirmskaitļu meklēšanas algoritms
Nataļja Mikuļina

5.

Teorētiskais materiāls
Eratostēna siets (ES) matemātikā tiek lietots
pirmskaitļu noteikšanai. Metode balstās uz
principu, kad tiek uzrakstīta skaitļu virkne un
tiek svītroti tie elementi, kuri dalās ar iepriekš
virknē esošiem pirmskaitļiem. Lai iegūtu
precīzu pirmskaitļu virkni, pirmo pirmskaitli
izmanto ciparu “2”.
Apskatīsim piemēru ar virkni līdz skaitlim 20.

6.

Teorētiskais materiāls
Šajā virknē ir iespējamas tikai divas darbības:
1. Svītrojam skaitļus, kas dalās ar 2
2. Svītrojam skaitļus, kas dalās ar 3
Kā redzams piemērā ir iegūti visi pirmskaitļi.

7.

Ilustrācija Eratostena sieta algoritmam
skaitļiem, kas nepārsniedz 120
http://lv.wikipedia.org/wiki/Eratostena_siets

8.

J. Raiņa Daugavpils 6.vidusskola
Skaitļu teorijas un algebras
algoritmi
Nataļja Mikuļina
izliekta daudzstūra un līklīniju trapeces
laukuma aprēķināšanas algoritmi