Informatyka

Przykładowy program realizujący algorytm wyszukiwania binarnego. W programie losowanych jest 100 liczb z zakresu 1-1000. Następnie dane są sortowane rosnąco. Dla posortowanych danych program sprawdza, czy wystąpiła liczba 100.

Na wyjściu otrzymujemy posortowane dane, wartości "x" i "y" dla kolejnych przebiegów pętli oraz wartość elementu środkowego. Jeżeli element środkowy jest poszukiwaną liczbą pętla kończy pracę, w przeciwnym wypadku sprawdzamy, w którą stronę przesunąć przeszukiwany zakres (zminiejszamy go poprzez przesunięcie "x" lub "y")

 

 

  1. #include<iostream>
  2. #include<ctime>
  3. #include<cstdlib>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int T[100];
  9.  
  10. main()
  11. {
  12.   srand(time(NULL));
  13.  
  14.   //generujemy liczby <1-1000>
  15.   for (int i=0 ; i<100 ; i++)
  16.       T[i]= rand()%1000+1;    
  17.  
  18.   //sortujemy dane
  19.   sort(T,T+100);
  20.  
  21.   //wypisujemy posortowana tablice
  22.   for (int i=0 ; i<100 ; i++)
  23.       cout<<T[i]<<", ";
  24.  
  25.   //zmienna istnieje ustawiamy na FALSZ
  26.   bool istnieje=false;
  27.  
  28.   //ustawiamy indexy x i y na poczatek i koniec przeszukiwanego zbioru
  29.   int x=0,y=99;          
  30.  
  31.   //ustalamy wyszukiwana wartosc s=100
  32.   int s=100;
  33.  
  34.   //sprawdzamy czy wyszukiwana wartosc jest na poczatku lub na koncu zakresu
  35.   if (T[x]==s || T[y]==s) istnieje=true;
  36.  
  37.   //jezeli nie, to wyszukujemy binarnie
  38.   while (y-x>1 && !istnieje)
  39.   {
  40.      //linia pomocnicza - wyswietlenie biezacych danych
  41.      cout << "\nx=" << x << "\ty="<< y << "\tT[(y+x)/2]=" << T[(y+x)/2];
  42.  
  43.      //jezeli na srodku zakresu jest wyszukiwana liczba istnieje=true
  44.      if (T[(y+x)/2]==s)
  45.            istnieje=true;
  46.      else
  47.           //w przeciwnym razie modyfikujemy x lub y w zaleznosci od "za duzo lub za malo"
  48.           if (T[(y+x)/2]>s)
  49.               y=(y+x)/2;
  50.           else
  51.               x=(y+x)/2;
  52.   }
  53.  
  54. //wypisujemy wynik
  55. if (istnieje) cout<<"\n\nTAK"; else cout<<"\n\nNIE";;
  56.  
  57. }

Poniższy link prowadzi do zbiorów zadań opublikowanegych przez Centralną Komisję Egzaminacyjną. ► zobacz zbiór CKE

 

Informacje o egzaminie maturalnym

Informacje o przebiegu i terminach egzaminu maturalnego ► CKE

 

certyfikat zadowolony konsument

Kontakt

I Liceum Ogólnokształcące im.S.Żeromskiego w Lęborku

84-300 Lębork; ul.Dygasińskiego 14

tel.: (59) 862 12 93

sekretariat(at)lo1.lebork.pl

d  dziennik
p  poczta
f  fanpage