Strona główna » Algorytmy » Artykuły » Czarno-Białe Kulki
 

Czarno-Białe Kulki

Zagadka

Krzyś bardzo lubi się bawić swoimi białymi i czarnymi kulkami. Wymyślił sobie zabawę, która polega na losowaniu dwóch kulek z pudełka. Jeśli wylosowane kulki są różnego koloru to wkładamy z powrotem czarną kulkę do pudełka. Jednak w przypadku, gdy są tego samego koloru to żadnej kulki nie wkładamy z powrotem. Chłopiec zastanawia się jaki będzie kolor ostatniej kulki w pudełku i od czego to będzie zależeć.

W zadaniu przyjmujemy, że łączna liczba kulek jest nieograniczona, ale co najmniej jedna kulka biała oraz czarna.

Przykład

Załóżmy, że Krzyś ma w pudełku 6 kulek z czego 2 są koloru czarnego, a białych są 4.

PudełkoLosowanieWynik
C, C, B, B, B, BC, BDokładamy kulkę Czarną do pudełka
C, C, B, B, BC, BDokładamy kulkę Czarną do pudełka
C, C, B, BC, BDokładamy kulkę Czarną do pudełka
C, C, BC, CNie dokładamy żadnej kuli
B-W pudełku została kulka Biała

Odpowiedź

W pudełku musi znajdować się nieparzysta liczba kulek czarnych, aby na koniec zawsze została kula czarna. W przeciwnym wypadku nie da rady określić jakiego koloru będzie ostatnia kula.

Wyjaśnienie

Zauważmy, że istnieją trzy różne wyniki losowania kulek: czarna i czarna, biała i biała oraz biała i czarna. W przypadku wylosowania kulek tego samego koloru nie są one zwracane, a w trzecim przypadku czarna kulka jest dorzucana do pudełka. Zauważmy, że jeśli danej kulki jest parzysta liczba to istnieje przypadek, że wszystkie zostaną one usunięte. W związku z tym wiadomo, że liczba kulek czarnych musi być nieparzysta, ponieważ z pudełku zawsze jest co najmniej jedna kulka każdego koloru.

Kontynuując rozważania każdy dowolny ciąg kulek można uprościć do jednego z trzech podanych przypadków. Jednak przy założeniu, że liczba kulek czarnych jest nieparzysta to po usunięciu wszystkich par o tym samym kolorze na koniec zostanie sama kula czarna i żadnej białej, albo kula czarna i biała co po wylosowaniu pozostawia kulę czarną w pudełku.

Kulka zwycięcza

Zauważmy, że jeśli w pudełku jest nieskończenie wiele kulek białych i chociaż tylko jedna czarna to wynikiem będzie kulka czarna, ponieważ losując dwie białe usuniemy je, a wybierając czarną i białą to dołożymy kolejną czarną.

Implementacja

Przypuśćmy, że chcemy napisać program, który rozwiąże przedstawiony w zadaniu problemy. Dane wejściowe dla niego to będzie ciąg znaków złożony z liter C oraz B. Program zliczy ilość wystąpień czarnych kul i na tej podstawie określi kolor ostatniej kuli. Zwrócona może być wartość C, która będzie oznaczać, że zwrócona zostanie czarna kulka, albo N - ostateczny kolor jest nie do określenia.

Zadanie to realizuje poniższa funkcja wynik(), która jako jedyny argument akceptuje słowo w - wspomniany ciąg liter C i B.

C++
C#
  1. char wynik(string w) {
  2.   int ilec = 0;
  3.   for (int i = 0; i < w.length(); i++)
  4.     if (w[i] == 'C')
  5.       ilec++;
  6.   if (ilec % 2 == 1)
  7.     return 'C';
  8.   return 'N';
  9. }

(2.) Przygotuj licznik i (3. - 5.) zlicz wystąpienia znaku C. Potem (6. - 8.) zinterpretuj otrzymaną wartość.

Testowanie funkcji

Napisaną funkcję można przetestować przy pomocy poniższego fragmentu kodu, która wczyta od użytkownika łańcuch znaków i wypisze kolor ostatniej kulki w pudełku.

C++
C#
  1. int main() {
  2.   string s;
  3.   cout << "Jakie kule znajduja sie w urnie?" << endl;
  4.   getline(cin, s);
  5.   char w = wynik(s);
  6.   switch (w) {
  7.   case 'C':
  8.     cout << "Ostatnia kula jest czarna";
  9.     break;
  10.   default:
  11.     cout << "Nie mozna okreslic koloru ostatniej kuli";
  12.     break;
  13.   }
  14.   system("pause");
  15.   return 0;
  16. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1