Strona główna » Algorytmy » Artykuły » Pudełko Wadliwych Kuleczek
 

Pudełko Wadliwych Kuleczek

Zagadka

Jan jest pracownikiem magazynu. Dzisiaj otrzymał dziesięć pudełek wypełnionych po brzegi kuleczkami. Tuż po rozpakowaniu przyszła do niego wiadomość, że w najnowszej dostawie jedno pudełko jest wypełnione kuleczkami o nieprawidłowej wadze. Sprzedawane kuleczki ważą 10g każda, a wadliwe tylko 9g. Szef poprosił pracownika o przygotowanie pudełka do odesłania. Jan dysponuje elektroniczną wagą, więc chciał zważyć kulki z każdego pudełka w celu wykrycia wadliwych kulek. Jednak przed włączeniem wagi przypomniał sobie, że zapomniał w wadze wymienić baterii przez co nie jest pewien czy będzie mógł wykonać więcej niż jedno ważenie. Jan zastanawia się czy jest możliwe wykrycie wadliwego pudełka wykonując tylko jedno ważenie. Opracuj strategie dla Jana, która pozwoli mu przygotować odpowiednią paczkę.

Rozwiązanie

Przypuśćmy, że pudełka są ponumerowane od 1 do 10. Wtedy Jan powinien z pierwszego pudełka wyjąć jedną kulkę, z drugiego dwie, z trzeciego trzy, ... z ostatniego dziesięć. Łącznie weźmie 1 + 2 + 3 + .. + 10 = 55 kuleczek. Łącznie powinny one ważyć 550g. Jednak wadliwe kuleczki obniżą ten wynik o kilka gram. Przykładowo jeśli po zważeniu okaże się, że ważą tylko 545g. Wiemy, że różnica między wagą poprawną, a wadliwą wynosi 1g, więc dzieląc różnice pomiędzy wynikami 5g / 1g otrzymujemy pięć. Z tego wynika, że pięć kuleczek ma nieprawidłową wagę, a taką ilość pobraliśmy z pudełka numer 5.

Uogólnienie problemu

Oczywiście należy pamiętać, że jeśli różnica między prawidłową, a wadliwą kulką była większa to należałoby różnicę wagi zmierzonej oraz obliczonej nie uznawać od razu za numer pudełka, a dodatkowo podzielić poprzez różnicę tych wag.

Przykładowo ponownie dla dziesięciu pudełek wyjmujemy łącznie 55 kuleczek. Różnica polega jednak na tym, że wadliwa kulka waży teraz 8g, a prawidłowa 10g. Po zważeniu kulczeki ważą nie 550g, a 540g. Wydawać by się mogło, że w takim razie jest to pudełko 10. Jest to oczywiście nieprawda, ponieważ 10g to różnica x kuleczek, ale każda kulczeka pomniejsza wagę o 2g, więc 10g/2g = 5. Ponownie pudełkiem zawierającym wadliwe kuleczki okazało się pudełko numer 5.

Implementacja

Przypuśćmy, że dostawa składała się z n pudełek kuleczek i wiadomo, że jedno pudełko jest wypełnione wadliwymi kuleczkami. Zakładamy, że prawidłowe kuleczki ważą a, a wadliwe b. Program powinien wypisać na ekran w którym pudełku znajdują się wadliwe kuleczki zakładając, że po wybraniu kuleczek zgodnie ze schematem w rozwiązaniu zadania ich waga wynosi w.

C++
C#
  1. int ktorePudelko(int n, int a, int b, int w) {
  2.   int suma = 0;
  3.   for (int i = 1; i <= n; i++)
  4.     suma += i;
  5.   suma *= a;
  6.   return (suma - w) / (a - b);
  7. }

Testowanie funkcji

Napisaną funkcję można przetestować przy pomocy poniższego fragmentu kodu:

C++
C#
  1. int main () {
  2.   int a, b, n, w;
  3.   cout << "Ile pudelek bylo w dostawie?\n n = ";
  4.   cin >> n;
  5.   cout << "Waga poprawnej kuleczki to:\n a = ";
  6.   cin >> a;
  7.   cout << "Waga wadliwej kuleczki to:\n b = ";
  8.   cin >> b;
  9.   cout << "Waga kulek po zwazeniu to:\n w = ";
  10.   cin >> w;
  11.   cout << "\nWadliwe kuleczeki sa w pudelku ";
  12.   cout << ktorePudelko(n, a, b, w);
  13.   system("pause");
  14.   return 0;
  15. }