Strona główna » Algorytmy » Artykuły » Brakująca Liczba
 

Brakująca Liczba

https://mattomatti.com/a0176

Zadanie

Jaś miał stos n kartek z zapisanymi liczbami od 1 i każda następna liczba była większa od poprzedniej o r. Niestety wiatr wyrwał Jasiowi kartki. Po zebraniu okazało się, że jednej brakuje, ale nie wiem jakiej. Pomóż Jasiowi znaleźć brakującą kartkę.

Przykład

Przyjmijmy, że Jaś miał 6 kartek ponumerowanych 1 .. 6. Po podniesieniu znalazł następująco: 5, 2, 6, 1, 4. W taki przypadku odpowiedź można znaleźć natychmiast, ale symulacja takiej sytuacji może się odbywać dla miliona rozrzuconych kartek. Jaś mógł nieść kartki z kolejnymi liczbami nieparzystymi czyli 1, 3, 5, 7, 9.. Wtedy należy wskazać, której liczby nieparzystej brakuje.

Implementacja

Proste Rozwiązanie

Najmniej optymalna metoda polega na wyszukiwaniu każdego kolejnego elementu czyli dla każdej z n liczb przeszukujemy n - 1 elementów. Złożoność takiego rozwiązania wynosi O(n2). Warto jednak nadmienić, że w takim przypadku złożoność pamięciowa wynosi O(1).

Rozwiązanie Liniowe

Rozwiązanie może działać w czasie liniowym poprzez utworzenie tymczasowej tablicy na której zostaną odznaczone kolejne elementy z tablicy. Następnie wystarczy przejrzeć tablicę, aby znaleźć jeden element, który nie został odnaleziony. Oznacza to, że algorytm działa w czasie liniowym O(n), ale jego złożoność pamięciowa też tyle wynosi tj. O(n).

Poniżej została przedstawiona implementacja takiego algorytmu. Funkcja szukajBrakujacejLiczby() wymaga podania: tab - liczb z kartek, które Jaś znalazł oraz r - różnica, która występuje pomiędzy kolejnymi liczbami (po posortowaniu).

  1. int szukajBrakujacejLiczby(int * tab, int n, int r = 1) {
  2.   bool * znalezione = new bool[n + 1];
  3.   for (int i = 0; i < n + 1; i++) {
  4.     znalezione[i] = false;
  5.   }
  6.   for (int i = 0; i < n; i++) {
  7.     znalezione[(tab[i] - 1) / r] = true;
  8.   }
  9.   for (int i = 0; i < n + 1; i++) {
  10.     if (!znalezione[i]) {
  11.       return i * r + 1;
  12.     }
  13.   }
  14.   return 0;
  15. }

Na początku algorytm tworzy tablicę dla n + 1, ponieważ w tablicy jest n znalezionych kartek i początkowo oznaczamy, że Jaś nie ma żadnej kartki. Następnie przechodzimy po każdym elemencie tablicy i ustawiamy odpowiedni element na prawdę. Na koniec należy znaleźć, który element nadal jest fałszywy i zwrócić jego wartość.

Rozwiązanie Optymalne

Znając pierwszy element, w tym zadaniu zawsze 1, ilość elementów oraz różnicę pomiędzy elementami możliwe jest, aby obliczyć wszystkie wyrazy jakie były zapisane na kartkach. Najbardziej potrzebny jest największy element, który został zapisany na kartkach, ponieważ pozwoli obliczyć jaka powinna być suma wszystkich elementów. Następnie należy odjąć każdy element z tablicy od sumy, aby na koniec została tylko szukana wartość.

Niewątpliwą zaletą takiego rozwiązania jest fakt, że działa w czasie liniowym O(n) oraz wymaga O(1) pamięci. Łączy, więc najlepsze cechy obu poprzednio wspomnianych algorytmów. Należy jednak zauważyć, że problem może dotyczyć sumy, ponieważ dla dużej tablicy, albo dużego r suma może szybko przewyższyć zakres typu w którym suma jest przechowywana.

Funkcja szukajBrakujacejLiczby() realizuje przedstawiony algorytm i tak jak poprzednia implementacja wymaga podania kolejno: tab - liczb z kartek, które Jaś znalazł oraz r - różnica, która występuje pomiędzy kolejnymi liczbami (po posortowaniu).

  1. int szukajBrakujacejLiczby(int * tab, int n, int r = 1) {
  2.   int ostatni = 1 + n*r;
  3.   int suma = (1 + ostatni) * (n + 1) / 2;
  4.   for (int i = 0; i < n; i++) {
  5.     suma -= tab[i];
  6.   }
  7.   return suma;
  8. }

Testowanie funkcji

W celu sprawdzenia poprawności działania funkcji można skorzystać z poniższego fragmentu kodu, aby wczytać dane, a następnie odczytać wynik.

  1. int main () {
  2.   int n, r;
  3.   cout << "Ile liczb ma lista?\n n = ";
  4.   cin >> n;
  5.   int * liczby = new int[n];
  6.   cout << "Podaj elementy:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> liczby[i];
  9.   cout << "Podaj roznice elementow\n r = ";
  10.   cin >> r;
  11.   int wynik = szukajBrakujacejLiczby(liczby, n, r);
  12.   cout << "Brakuje: " << wynik << endl;
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Do kodu źródłowego optymalnego rozwiązania dopisz fragment kodu, który sprawdzi czy dana lista elementów jest poprawna tj. czy wszystkie elementy są faktycznie z zakresu oraz czy różnica pomiędzy nimi wynosi k. Jeśli nie to zwróć 0.