program lab2_1JP3.pdf

Laboratorium 1: Algorytmy z p ħ tlami

1. Algorytm Euklidesa

1.1. Wyznacz najwi ħ kszy wspólny podzielnik dwóch liczb naturalnych za pomoc Ģ algorytmu Euklidesa

1.2. Algorytm:

Podaj liczb ħ a

Podaj liczb ħ b

Wybierz liczb ħ wi ħ ksz Ģ z liczb a i b

Przypisz liczb ħ niemniejsz Ģ do x1 oraz pozostał Ģ liczb ħ do x2

Ustaw i:=0

Wyznacz reszt ħ dzielenia x3:=x1 mod x2

Je Ļ li x3>0 , wykonuj kolejne kroki, w przeciwnym wypadku przejd Ņ do kroku 8

7.1) Powi ħ ksz i:=i+1

7.2) Umie Ļę x3 w tablicy w wierszu i oraz kolumnie 0

7.3) Wyznacz: x1:=x2 x2:=x3 x3:=x1 mod x2 i przejd Ņ do kroku 7

x2 jest najwi ħ kszym wspólnym podzielnikiem – wy Ļ wietl go na ekranie

wy Ļ wietl zawarto Ļę tablicy na ekranie

9.1) ustaw j:=1

9.2) dopóki j<=i wykonuj kolejne kroki, w przeciwnym wypadku zako ı cz program

9.3) pobierz do zmiennej a element tablicy z wiersza j i kolumny 0

9.4) wy Ļ wietl a na ekranie

9.5) zwi ħ ksz j:=j+1 i przejd Ņ do kroku 9.2

2.Algorytm wyszukania liczb pierwszych metod Ģ sita Eratostenesa

2.1.Nale Ň y wyznaczy ę wszystkie liczby pierwsze w podzbiorze liczb naturalnych {1..N} za pomoc Ģ algorytmu

sita Eratostenesa

2.2.Algorytm:

Podaj N z klawiatury

1.2)

Je Ļ li N<2, powtórz krok 1.1

1.3)

Ustaw i:=2

1.4)

Dopóki i<=N wykonuj kolejne kroki, w przeciwnym wypadku przejd Ņ do kroku 2

1.4.1) wstaw 0 do elementu tablicy o indeksie i

1.4.2) zwi ħ ksz i:=i+1 i przejd Ņ do kroku 1.4.

Utworzy ę tablic ħ zawieraj Ģ c Ģ N elementów i wstawi ę do ka Ň dego elementu warto Ļę 0

1.1)

Zakłada si ħ , Ň e pewne indeksy elementów s Ģ szukanymi liczbami pierwszymi i po zako ı czeniu algorytmu

elementy tablicy o tych indeksach b ħ d Ģ zawiera ę warto Ļę 0, natomiast pozostałe elementy maja warto Ļę 1,

poniewa Ň nie s Ģ liczbami pierwszymi. St Ģ d nale Ň y wstawi ę na pocz Ģ tku warto Ļę 1 do elementu o indeksie

równym 1, poniewa Ň 1 nie jest liczb Ģ pierwsz Ģ

Ustawi ę ost_Liczp:=1;

Na podstawie faktu, Ň e ka Ň da liczba zło Ň ona nie wi ħ ksza ni Ň N ma dzielnik nie wi ħ kszy ni Ň sqrt(N)

wykonuj kolejne kroki, gdy ost_Liczp*ost_Liczp <=N, w przeciwnym wypadku przejd Ņ do kroku 4.6:

4.1) Nale Ň y zwi ħ kszy ę ost_Liczp o 1 : ost_Liczi:=ost_Liczp+1

4.2) Wykonuj kolejne kroki , je Ļ li jest prawdziwy warunek (ost_Liczp<=N) and (tab[ost_Liczp]=1 ), w

przeciwnym wypadku przejd Ņ do kroku 4.3.

4.2.1) zwi ħ kszaj ost_Liczp o 1 : ost_Liczi:=ost_Liczp+1 (poszukiwanie kolejnej liczby pierwszej, czyli

elementu tablicy o indeksie ost_Liczp nie zawieraj Ģ cej warto Ļ ci 1)

4.4.2) przejd Ņ do kroku 4.2

4.3) Nale Ň y podwoi ę ost_Liczp ost : i:= ost_Liczp*2 (rozpocz ħ cie kolejnego etapu wykre Ļ lania liczb, które

nie s Ģ liczbami pierwszymi)

4.4) Dopóki i<=N, wykonaj w kolejnych krokach eliminacj ħ liczb, które nie s Ģ liczbami pierwszymi,

poniewa Ň s Ģ ich wielokrotno Ļ ciami, w przeciwnym wypadku przejd Ņ do kroku 4 .

4.4.1) wstaw warto Ļę 1 to elementu tablicy o wierszu równym i

4.4.2) dodaj warto Ļę ost_Liczp do i: i:=i+ost_Liczp , nast ħ pnie przejd Ņ do kroku 4.4

4.6) Wy Ļ wietl zawarto Ļę tablicy na ekranie:

4.6.1) wstaw i:=1

4.6.2) dopóki i<=N wykonuj kolejne kroki, w przeciwnym wypadku zako ı cz algorytm

4.6.2.1) je Ļ li tab[i]=0 , wy Ļ wietl indeks elementu jako warto Ļę kolejnej liczby pierwszej

4.6.2.2) wyznacz kolejny indeks i:=i+1 i przejd Ņ do kroku 4.6.2.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: