Strona główna » Algorytmy » Artykuły » Jedno Rozwiązanie?
 

Jedno Rozwiązanie?

https://mattomatti.com/a0233

Zadanie

Dane jest równanie a = b AND c oraz dwie wartości całkowite a i b. Zakładając, że c jest mniejsze niż 2b to ile jest możliwych rozwiązań? Napisz program, który wypisze je wszystkie w dowolnej kolejności. Jeśli nie jest możliwe wyznaczenie c to program powinien wypisać odpowiedni komunikat.

Przykład

Przykładowo mamy dane a = 4 = 1002 oraz b = 5 = 1012. Wiadomo, że c to liczba należąca do przedziału [0, 10), ale tylko dwie spełniają równanie. Są to 4 oraz 6. Wystarczy sprawdzić, że 100 = 101 AND 100 oraz 100 = 101 AND 110.

Implementacja

Rozwiązanie Siłowe

Rozwiązanie siłowe polega na napisaniu funkcji, która w pętli sprawdzi wszystkie możliwe rozwiązania. Złożoność takiego algorytmu jest liniowa O(n). Warto jednak zauważyć, że rozwiązania stanowią niewielki procent wszystkich możliwych. Oto przykładowy kod funkcji:

  1. vector<int> SzukajRozwiazan(int a, int b) {
  2.   vector<int> wynik;
  3.   for (int c = 0; c < 2 * b; c++) {
  4.     if (a == (b & c)) {
  5.       wynik.push_back(c);
  6.     }
  7.   }
  8.   return wynik;
  9. }

Na początku deklarowana jest pusta lista do zapisu danych, a następnie definiowany jest odpowiedni zakres w pętli i jeśli aktualny indeks po wykonaniu operacji binarnej da odpowiedni wynik to wartość indeksu zostaje dopisana na listę. Na koniec zwracana jest lista wynikowa.

Rozwiązanie Optymalne

Opis

Złożoność algorytmu można poprawić wyznaczając miejsca, gdzie trzeba postawić konkretną wartość, a kiedy dowolną. Oto możliwe pary (a, b) oraz akcja jaką należy podjąć:

abc
00dowolna wartość, 0 lub 1
01tylko 0
10niemożliwe, cokolwiek i 0 daje zawsze 0
11tylko 1

Jak można zauważyć jeśli w parze (a, b) wystąpi para wartości (1, 0) to zadanie jest niemożliwe do rozwiązania. Jedynym przypadkiem, gdy można postawić dowolną wartość jest (0, 0), ponieważ cokolwiek i 0 zawsze da 0.

Algorytm można usprawnić następująco: na początku znajdujemy wszystkie bity o dowolnej wartości i zapisujemy ich pozycje na liście [p1, p2, .., pk]. Podczas przeglądania wartości możemy zakończyć działanie funkcji jeśli znajdziemy parę (1, 0). Na podstawie listy określamy, że jest 2k możliwych rozwiązań i je wyznaczamy. n-te rozwiązanie polega na zastąpieniu bitu pi poprzez i-ty bit n.

Przykład

Dane jest a = 1002 oraz b = 1012. Wiadomo, że dowolny może być bit środkowy, a więc o indeksie 1. Istnieję tylko dwa możliwe rozwiązania. Podstawą do generowanie kolejnych rozwiązań jest 1x0. Najpierw x to 0, a potem 1. W ten sposób zostają uzyskane obydwa możliwe rozwiązania.

Kod

Poniższy kod implementuje powyższe wyjaśnienie algorytmu i zwraca listę wszystkich możliwych rozwiązań:

  1. vector<int> SzukajRozwiazan(int a, int b) {
  2.   vector<int> wynik, dowolne;
  3.   int maska = 0;
  4.   int dl = log2(max(a, b)) + 1;
  5.   for (int i = 0; i < dl; i++) {
  6.     if (((a >> i) & 1) == 0) {
  7.       if (((b >> i) & 1) == 0) {
  8.         dowolne.push_back(i);
  9.       }
  10.     } else {
  11.       if (((b >> i) & 1) == 0) {
  12.         return wynik;
  13.       } else {
  14.         UstawBit(maska, i, 1);
  15.       }
  16.     }
  17.   }
  18.   dl = 1 << dowolne.size();
  19.   for (int i = 0; i < dl; i++) {
  20.     for (int j = 0; j < dowolne.size(); j++) {
  21.       UstawBit(maska, dowolne[j], (i >> j) & 1);
  22.     }
  23.     wynik.push_back(maska);
  24.   }
  25.   return wynik;
  26. }

Dla k wierszy inicjujemy licznik na zero oraz kopiujemy aktualny numer wiersza. Nastepnie w petli przechodzimy po kolejnych bitach tak dlugo, az wyzerujemy wartosc. Za kazdym razem dodajemy najstarszy bit liczby. Na koniec obliczamy 2ile i wypisujemy wynik.

Pierwsza część polega na wyznaczeniu maski rozwiązań, która będzie potem wykorzystana do generowania rozwiązań (zmieniane będę później tylko odpowiednie bity). W zależności od wartości i-tego bitu modyfikujemy maskę. Następnie przechodzimy do generowania rozwiązań odpowiednio modyfikując bity maski i zapisując dane do wyniku. Złożoność algorytmu to O(nk), gdzie n - ilość rozwiązań, a k - ilość bitów dowolnych. Zaletą takiego rozwiązania jest to, że w każdej iteracji znajduje rozwiązanie i potrafi wyjść z funkcji poprzez wykrycie niemożliwego stanu.

W kodzie została wykorzystana metoda UstawBit(), która w podanej zmiennej ustawia i-ty bit na wartosc.

  1. void UstawBit(int &zmienna, int i, int wartosc) {
  2.   zmienna &= ~(1 << i);
  3.   zmienna |= (wartosc << i);
  4. }

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programau:

  1. int main() {
  2.   int a, b;
  3.   cout << "Podaj liczbe wynikowa\n a = ";
  4.   cin >> a;
  5.   cout << "Podaj pierwszy skladnik\n b = ";
  6.   cin >> b;
  7.   vector<int> wynik = SzukajRozwiazan(a, b);
  8.   if (wynik.size() == 0) {
  9.     cout << "Nie ma rozwiazan";
  10.   }
  11.   else {
  12.     cout << "Oto rozwiazania:" << endl;
  13.     for each (int x in wynik) {
  14.       cout << x << " ";
  15.     }
  16.   }
  18.   system("pause");
  19.   return 0;
  20. }