Szkoły ETE im. Alberta Schweitzera

  • Increase font size
  • Default font size
  • Decrease font size
Start Liceum Przedmioty Informatyka Algorytmika i programowanie
C++

Rzutowanie

Email Drukuj PDF

Przekształcenia typów w języku C++. 

W języku C rzutowanie wyglądało w następujący sposób:

int zmienna_calkowita = (int)zmienna_rzeczywista;

W C++ nadal można używać takiego rzutowania, jest ono nazywane "rzutowaniem w stylu C". Oprócz tego C++ oferuje "rzutowanie w stylu funkcyjnym":

int zmienna_calkowita =int(zmienna_rzeczywista);

które działa dokładnie tak samo.

Poprawiony: poniedziałek, 16 grudnia 2019 22:59
 

Sito Eratostenesa

Email Drukuj PDF

Metoda Sito Eratostenesa pozwala na znalezienie wszystkich liczb pierwszych w zakresie  od 2 do n

#include <iostream>
using namespace std;
int main()
{
int n;
cout<<"podaj zakres "<<endl;
cin>>n;
int tab[n]={0};
int a=2;
for(int j=2;j<n;j++)
 {
   if(tab[j]==0) a=j;
   for(int i=a+1;i<n;i++)
     {
        if(i%a==0)tab[i]=1;
     }
  }
for(int j=2;j<n;j++)
if(tab[j]==0)cout << j << endl;
return 0;
}

 

szyfr polialfabetyczny ze słowem kluczowym

Email Drukuj PDF

 

 
#include <iostream>
 
using namespace std;
 
int main()
{
    string klucz;
    string jawny, zakod;
    cout<<"podaj klucz"<<endl;
    cin>>klucz;
    cout<<"podajtekst do zakodowania"<<endl;
    cin>>jawny;
    int dlklucza;
    dlklucza=klucz.length();
    char tab[dlklucza+1][26];
    int kod, a, z;
    for(int i=0; i<26; i++)
    {
        tab[0][i]=(char)i+65;
        cout<<tab[0][i];
    }
    cout<<endl;
    for(int i=1; i<dlklucza+1; i++)
    {
       tab[i][0]=klucz[i-1];
       kod=(int) klucz[i-1];
       cout<<endl<<tab[i][0];
        for(int j=1; j<26; j++)
        {
           kod++;
           if(kod>90) kod-=26;
            tab[i][j]=(char) kod;
           cout<<tab[i][j];
        }
    }
    for(int i=0;i<jawny.length();i++)
    {
        a=i%dlklucza+1;
        z=(int)jawny[i]-65;
        zakod=zakod+tab[a][z];
    }
cout<<endl<<"takst zaszyfrowany   "<<zakod;
    return 0;
}

 

Poprawiony: poniedziałek, 16 grudnia 2019 22:56
 

SZYFR NONOALFABETYCZNY ZE SŁOWEM KLUCZOWYM

Email Drukuj PDF

SZYFR MONOALFABETYCZNY ZE SŁOWEM KLUCZOWYM

słowo kluczowe – KLUCZ

0

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

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

K

L

U

C

Z

A

B

D

E

F

G

H

I

J

M

N

O

P

Q

R

S

T

V

W

X

Y

I

N

F

O

R

M

A

T

Y

K

A

E

J

A

M

P

I

K

R

X

G

K

TABLICA   ASCII

0

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

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

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

 

#include <iostream>

using namespace std;
bool czy_byla(char a, string k)
  {
     int dl=k.length();
     for(int i=0; i<dl; i++)
       {
          if(a==k[i])  return 0;

        }
    return 1;
  }

int main()
{
string klucz;
string jawny, zakod;
cout<<"podaj klucz"<<endl;
cin>>klucz;
cout<<"podaj tekst do zakodowania"<<endl;
cin>>jawny;
int dlklucza=klucz.length();
string alfszyfrowy;
char znak,z;

alfszyfrowy=klucz;

char ost=klucz[dlklucza-1];
int kod=(int) ost;
for(int i =0; i<26; i++)
 {
   kod++;
   if(kod>90) kod-=26;
   z=(char)kod;
   if(czy_byla(z,klucz)==1) alfszyfrowy+= z;
 }
cout<<alfszyfrowy<<endl;
for(int i=0;i<jawny.length();i++)
  {
   z=(int)jawny[i]-65;
   zakod=zakod+alfszyfrowy[z];
   }
cout<<endl<<"tekst zaszyfrowany "<<zakod;

return 0;
}

Poprawiony: poniedziałek, 16 grudnia 2019 22:54
 

Quick sort implementacja

Email Drukuj PDF

#include<iostream>
using namespace std;


void quick_sort(int *tab, int lewy, int prawy)
{
if(prawy <= lewy) return;

int i = lewy - 1, j = prawy + 1,
pivot = tab[(lewy+prawy)/2]; //wybieramy punkt odniesienia

while(1)
{
//szukam elementu wiekszego lub rownego piwot stojacego
//po prawej stronie wartosci pivot
while(pivot>tab[++i]);

//szukam elementu mniejszego lub rownego pivot stojacego
//po lewej stronie wartosci pivot
while(pivot<tab[--j]);

//jesli liczniki sie nie minely to zamień elementy ze soba
//stojace po niewlasciwej stronie elementu pivot
if( i <= j)
//funkcja swap zamienia wartosciami tab[i] z tab[j]
swap(tab[i],tab[j]);
else
break;
}

if(j > lewy)
quick_sort(tab, lewy, j);
if(i < prawy)
quick_sort(tab, i, prawy);
}
int main()
{
int *tab, n;

cout<<"Ile liczb chcesz posortowac? ";
cin>>n;
tab = new int [n]; //przydzielenie pamięci na elementy tablicy
//wczytanie liczb
for(int i=0;i<n;i++)
cin>>tab[i];

quick_sort(tab,0, n-1);

//wypisanie posortowanych elementów
for(int i=0;i<n;i++)
cout<<tab[i]<<" ";


return 0;
}

Poprawiony: poniedziałek, 16 grudnia 2019 23:01
 

Quick sort - sortowanie szybkie

Email Drukuj PDF

Quick sort - sortowanie szybkie

Omawiany algorytm należy do jednego z najszybszych algorytmów sortujących dane wynaleziony w 1960 roku przez Sir Charles Antony Richard Hoare. Jest on chętnie implementowany i wdrażany do systemów informatycznych ze względu na szerokie spektrum zalet:

  • złożoność czasowa jest rzędu O(nlogn)
  • algorytm nie potrzebuje dodatkowej tablicy do posortowania jak to jest w przypadku sortowania przez scalanie
  • jest łatwy w implementacji
  • dobrze współpracuje z różnymi typami danych

Algorytm posiada także wady:

  • w sytuacji pesymistycznej złożoność może wynosić O(n2)
  • jest niestabilny
  • jest wrażliwy na błędy w implementacji

Działanie algorytmu

Algorytm wykorzystuje technikę "dziel i zwyciężaj". Według ustalonego schematu wybierany jest jeden element w sortowanej tablicy, który będziemy nazywać pivot. Pivot może być elementem środkowym, pierwszym, ostatnim, losowym lub wybranym według jakiegoś innego schematu dostosowanego do zbioru danych. Następnie ustawiamy elementy nie większe na lewo tej wartości, natomiast nie mniejsze na prawo. W ten sposób powstaną nam dwie części tablicy (niekoniecznie równe), gdzie w pierwszej części znajdują się elementy nie większe od drugiej. Następnie każdą z tych podtablic sortujemy osobno według tego samego schematu. 

Przykład

Do posortowania posłużymy się przykładem ciągu liczb:

2 5 1 3 4 0 6 2 5

W naszym algorytmie element pivot będzie środkowym elementem sortowanej tablicy

 

lewa część tablicy

pivot

prawa część tablicy

2

5

1

3

4

0

6

2

5

                 

Następnie ustawiamy liczniki i na pierwszy element tablicy, natomiast j na ostatni element tablicy:

lewa część tablicy

pivot

prawa część tablicy

2

5

1

3

4

0

6

2

5

i

             

j

W kolejnym kroku szukamy pierwszej liczby z lewej strony tablicy poruszając się licznikiem i ku wartości pivot, która jest nie mniejsza niż pivot oraz pierwszej liczby z prawej strony, która jest nie większa niż pivot. Stan liczników po wyszukaniu odpowiednich liczb:

lewa część tablicy

pivot

prawa część tablicy

2

5

1

3

4

0

6

2

5

 

i

         

j

 

 Teraz wykonujemy zamianę liczb, które stoją po niewłaściwej stronie:

lewa część tablicy

pivot

prawa część tablicy

2

2

1

3

4

0

6

5

5

 

i

         

j

 

 Czynności powtarzamy do momentu minięcia się liczników:

lewa część tablicy

pivot

prawa część tablicy

2

2

1

3

4

0

6

5

5

       

 i

j

     

Zamiana pivota z zerem

lewa część tablicy

pivot

prawa część tablicy

2

2

1

3

0

4

6

5

5

       

 i

 j

 

 

 

 i minięcie się liczników

lewa część tablicy

pivot

prawa część tablicy

2

2

1

3

0

4

6

5

5

lewy 

     

 j

 i

 

 

 prawy

W kolejnym kroku wykonujemy sortowanie dwóch tablic osobno, zawierających się w przedziałach:

pierwsza tablica:[lewy..j]:2 2 1 3 0

druga tablica:[i..prawy] :4 6 5 5.

Zauważmy, że w pierwszej tablicy znajdują się elementy nie większe od drugiej.

Lewa część tablicy

   

pivot

   

2

2

1

3

0

i

     

j

0

2

1

3

2

 

i

j

   
 

pivot

     

0

1

2

3

2

 

j

i

   

Po lewej stronie pivota jest tylko jeden element, więc stoi on już na odpowiedniej pozycji. Prawą część tej podtablicy dzielimy ponownie na dwie części:

 

pivot

 

2

3

2

i

 

j

2

3

2

 

i

j

   

pivot

2

2

3

 

j

i

Algorytm dla tej części podtablicy musi się wykonać jeszcze dla dwóch dwójek, ponieważ sortowanie kończy się, gdy podtablica składa się z co najwyżej jednego elementu. W tym przypadku liczby są już posortowane, więc dalsza wizualizacja jest zbędna.

Prawa część tablicy

 

pivot

   

4

6

5

5

 i

   

 j

4

 

 i

 

 j

     

 pivot

4

5

5

6

   

i=j

 

4

5

5

6

 

j

 

 i

Po tym minięciu się liczników, tablica zostanie jeszcze podzielona na dwie części, ale są one już posortowane, więc na tym kroku zakończymy.

Gdy popatrzymy globalnie na całą tablice, to zauważymy, że wszystkie jej elementy są poukładane w odpowiedniej kolejności.

Poprawiony: poniedziałek, 16 grudnia 2019 23:01