Zbiory
Janusz Sobieraj - 28 LO

Zbiory liczbowe (bez powtórzeń))
Od struktury typu ZBIÓR będziemy żądali niewiele : utwórz_pusty, dodaj_element, sprawdż_czy_jest .
Ponadto zbiór to struktura "bez powtórzeń" tzn dodawanie kolejno np 3,2,3,3,2,3,2 utworzy zbiór {2,3}
Możemy oczywiście skorzystać z klasy HashSet → dokumentacja Javy, ale co oczywiste, "wykonamy" zbiór samodzielnie.
Oto on: 
package liceum28; 
import java.awt.*; 
public class Zbior_liczb
  { 
   class Wezel 
    { 
    int element; 
    Wezel nastepny; 

    public Wezel() 
    { 
      element = 0; 
      nastepny = null; 
    } 
  } 
//-------------------------------------------
  private int ile; 
  private Wezel pierwszy; 

  public Zbior_liczb() 
  { 
    pierwszy = null; 
    ile = 0; 
  } 
//-------------------------------------------  
  public void dodaj(int nowa) 
  { 
    if ( !nalezy(nowa)) 
    { 
      Wezel w_nowy = new Wezel(); 
      w_nowy.nastepny = pierwszy; 
      w_nowy.element = nowa; 
      pierwszy = w_nowy; 
      ile++; 
    } 
  } 
//-------------------------------------------
  public boolean nalezy(int liczba) 
  { 
    Wezel w_wezel; 
    w_wezel = pierwszy; 
    while(w_wezel != null) 
    { 
     if(w_wezel.element ==liczba)return true;
     w_wezel = w_wezel.nastepny; 
    } 
    return false; 
  }
//-------------------------------------------
  public int liczba()
  { 
   return ile; 
  } 
}

Posłużmy się bardzo prostym przykładem. 
void dowolne() 
{ int los; 
 for(int i=0;i<10;i++) 
   los=mat.losowa_c(10); 
}

Losujemy 10 liczb każda z przedziału <0,9>.
Procedura dowolne() organizuje takie losowanie.

Aplet poniżej, w części "losuj swobodnie" pokazuje problem. Praktycznie rzecz biorąc na 10 takich losowań, w każdym następuje sytuacja powtórzeń niektórych wyników (zaznaczono kolorem czerwonym).


[Twoja przeglądarka nie obsługuje apletów Javy] 
void kazda_inna() 
{Zbior_liczb notuj; 
  notuj=new Zbior_liczb( ); 
  for(int i=0;i<10;i++) 
  { 
  do 
    { 
     los=mat.losowa_c(10); 
    } 
  while(notuj.nalezy(los)); 
  notuj.dodaj(los); 
  } 
}



Problem oczywiście jest do rozwiązania, wystarczy wykorzystać nasz zbiór np tak jak pokazuję to w procedurze kazda_inna() .

Podobny problem (i rozwiązanie) napotkamy w zadaniach typu "błądzenie losowe" .