Strona główna

Największy wspólny dzielnik (algorytm Euklidesa)


Pobieranie 23.6 Kb.
Data18.06.2016
Rozmiar23.6 Kb.

Największy wspólny dzielnik (algorytm Euklidesa)


Obliczania największego wspólnego dzielnika wg algorytmu Euklidesa

Do obliczania największego wspólnego dzielnika (NWD) zastosujemy algorytm Euklidesa z tzw. odejmowaniem. Dane są dwie liczby nieujemne a i b. Liczba w jest największym wspólnym dzielnikiem, jeśli dzieli liczby a i b i jest największą liczbą o tej własności. Algorytm Euklidesa służy do wyznaczania tej liczby. Jest to jeden z najstarszych znanych algorytmów, odkrytych jeszcze w starożytności przez Euklidesa. Jest to jednocześnie jeden z najczęściej spotykanych algorytmów, ponieważ zawiera w sobie iterację i dlatego tak często przytaczany jest w książkach informatycznych i matematycznych.



schemat blokowy

.

Wyszukiwanie elementu minimalnego


Sprecyzujmy warunki algorytmu:

Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator mniejszy niż za pomocą którego będziemy porównywać elementy

Wynik: Indeks (numer) pierwszego najmniejszego elementu spośród n podanych elementów (czyli liczba 1 ... n)

Algorytm w postaci listy kroków


  1. Zmiennej pomocniczej k przypisujemy 1

  2. Dla zmiennej i od 2 do n wykonujemy:

    • Jeśli element x[i] jest mniejszy (w sensie użytego operatora) od elementu x[k], to zmiennej k przypisujemy wartość i

  3. Element minimalny to element o indeksie k. Jego wartość to x[k]. Kończymy algorytm.

Algorytm jest bardzo prosty. Oto idea algorytmu (różni się od realizacji): Zakładamy, że elementem najmniejszym jest pierwszy element. Następnie każdy następny element porównujemy z elementem pierwszym i jeśli element ten jest mniejszy od pierwszego elementu, to teraz wszystkie elementy będziemy porównywać z tym nowym elementem.

Liczba pierwsza-SITO ERATOSTENESA

Liczba pierwsza - liczba naturalna n>1, dla której istnieją tylko dwa dzielniki naturalne: 1 i n.

1 - nie jest liczbą pierwszą

Liczbami pierwszymi są liczby:



2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,....

Pojęcie liczb pierwszych oraz algorytm ich poszukiwań znany był w starożytności. Około roku 200 p.n.e. grecki matematyk Eratostenes podał algorytm na znajdowanie liczb pierwszych. Mimo zaproponowania bardzo prostego algorytmu do dnia dzisiejszego matematyka nie zna lepszego sposobu na uzyskanie liczb pierwszych. Prześledźmy ideę Eratostenesa na przykładzie. Przypuśćmy, że chcemy znaleźć wszystkie liczby pierwsze wśród liczb od 1 do 100.



1) Ustawiamy liczby w ciąg:

1 2 3 4 5 6 7 8 9 10


11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

2) 1 nie jest liczbą pierwszą, więc ją skreślamy.

2 3 4 5 6 7 8 9 10


11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

3) Listę rozpoczyna liczba 2. Jest to liczba pierwsza. Teraz wykreślamy wszystkie liczby większe od 2 i podzielne przez 2.

2 3 5 7 9


11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49
51 53 55 57 59
61 63 65 67 69
71 73 75 77 79
81 83 85 87 89
91 93 95 97 99

4) Najmniejszą liczbą jest teraz liczba 3 (jest to liczba pierwsza - gdyby nią nie była, to dzieliłaby się przez 2, ale wtedy byłaby wykreślona). Skreślamy teraz z listy wszystkie liczby większe od 3 i podzielne przez 3.

2 3 5 7
11 13 17 19


23 29
31 35 37
41 43 47 49
53 55 59
61 65 67
71 73 77 79
83 85 89
91 95 97

5) Najmniejszą liczbą na liście jest liczba 5. Jest to liczba pierwsza (argumentacja jak wyżej). Skreślamy teraz wszystkie liczby podzielne przez 5 i większe od 5.

2 3 5 7
11 13 17 19


23 29
31 37
41 43 47 49
53 59
61 67
71 73 77 79
83 89
91 97

6) Najmniejszą liczbą na liście jest liczba 7. Jest ona liczbą pierwszą. Wykreślamy wszystkie jej wielokrotności.

2 3 5 7
11 13 17 19


23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
97

Zwróćmy uwagę, że do znalezienia wszystkich liczb pierwszych wystarczy badać liczby pierwsze niewiększe od . Dzieje się tak dlatego, że biorąc pod uwagę liczbę pierwszą p, zaczynam skreślanie od liczby p2 - mniejsze wielokrotności p są już skreślone (dzielą się przez liczbę mniejszą od p). Najbliższą liczbą pierwszą jest 11. Zauważmy, że, więc znaleźliśmy wszystkie liczby pierwsze od 1 do 100.

Liczby te to: 2 3 5 7
11 13 17 19
23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
97

Obecnie za pomocą super szybkich komputerów można znaleźć gigantyczne liczby pierwsze. W Internecie odbywa się "Wielkie Internetowe Poszukiwanie Liczb Pierwszych Mersenne'a" (GIMPS). 

 

Ciekawostki: 

Liczba pierwsza 26972593-1(odkryta 1 czerwca 1999 roku) ma ponad 2 mln cyfr, dokładnie 2 098 960. Jest ona 38 z kolei tzw. liczbą Mersenne'a. 

Największą znalezioną dotąd liczbą pierwszą jest liczba: 213466917-1. Rekordzistkę odkryto 14 listopada 2001 roku. Liczba ta składa się z 4053946 cyfr! Co więcej, liczba ta należy do tzw. liczb Mersenne'a (jest to 39 liczba pierwsza Mersenne'a). Odkrycie zostało dokonane w ramach wspomnianego wyżej programu GIMPS, w którym obliczeń dokonują wspólnie pracujące w Internecie komputery ponad 130 tysięcy badaczy-ochotników, zaprzęgając do poszukiwań ponad 200 tysięcy komputerów PC.

Liczba 11111111111111111111111 złożona z 23 jedynek jest pierwsza.

Istnieją liczby pierwsze złożone z kolejnych cyfr np.: 23, 67, 4567, 23456789, 1234567891, 1234567891234567891234567891. W dwóch ostatnich liczbach cyfry występują w tak zwanym rosnącym porządku cyklicznym, tzn. po kolei, z tym że po 9 może być 0 lub 1. Trudniej trafić na liczby pierwsze z malejącym porządkiem cyklicznym: 43, 10987, 76543 i 1987.

liczba 31415926535897932384626433832795028841 zestawiona z początkowych 38 cyfr rozwinięcia dziesiętnego liczby π jest pierwsza.

Liczba 73939133 nie tylko jest pierwsza, ale liczby otrzymane z niej przez kolejne obcinanie cyfr od prawej też są pierwsze: 7393913, 739391, 73939, 7393, 739, 73, 7.












KŁADY RÓWNAŃ LINIOWYCH

Układ nazywamy układem równań liniowych

Rozwiązaniem układu jest każda para liczb ( x , y ), spełniająca każde z równań układu. Przy rozwiązywaniu układów równań korzystamy z twierdzeń o równaniach (układach) równoważnych.

Metody rozwiązywania układów równań:

I. Metoda graficzna
II. Metoda podstawiania
III. Metoda przeciwnych współczynników
IV. Metoda wyznacznikowa

W celu rozwiązania ukłau równań metodą wyznacznikową należy obliczyć:


wyznacznik główny
W== a1*b2 -a2*b1

wyznacznik Wx


Wx== c1*b2 - c2*b1

wyznacznik Wy

Wy== c2a1 - c1a2

1. Jeżeli W <>(czytaj różne) 0 , to układ ma jedno rozwiązanie postaci i nazywa się układem oznaczonym, czyli układem równań niezależnych.

2. Jeżeli W = Wx = Wy = 0 , to układ ma nieskończenie wiele rozwiązań i nazywa się układem nieoznaczonym lub układem równań niezależnych.

3. Jeżeli ( W = 0 i Wx <> 0 ) lub ( W = 0 i Wy <> 0 ), to układ nie ma rozwiązania i nazywa się układem sprzecznym .



schemat blokowy



















©snauka.pl 2016
wyślij wiadomość