Dana jest tablica liczb dodatnich, całkowitych. Należy ją osiągnąć tylko poprzez dwie operacje: zwiększenie wybranego elementu tablicy o jeden, albo pomnożenie wszystkich elementów przez 2. Ile trzeba takich operacji wykonać łącznie, aby uzyskać z tablicy samych zer tablicę docelową?
Weźmy przykładowo tablicę [1, 2, 3, 4, 5]. Można ją osiagnać kolejno poprzez:
| Tablica | Operacja | Łącznie |
|---|---|---|
| [0, 0, 0, 0, 0] | Dodaj 1 do dwóch ostatnich pozycji | 2 |
| [0, 0, 0, 1, 1] | Pomnóż wszystkie elementy razy dwa | 3 |
| [0, 0, 0, 2, 2] | Dodaj 1 do drugiego i trzeciego elementu | 5 |
| [0, 1, 1, 2, 2] | Pomnóż wszystkie elementy razy dwa | 6 |
| [0, 2, 2, 4, 4] | Dodaj na pozycji pierwszej, trzeciej i piątej 1 | 9 |
Łącznie potrzeba 9 operacji, aby z tablicy samych zer otrzymać tablicę [1, 2, 3, 4, 5].
Zadanie to warto rozważyć w drugą stronę tzn. jak z tablicy liczb otrzymać same zera? W takim przypadku dostępne są dwie operacje przeciwne czyli odjęcie 1 od wybranego elementu, albo podzielenie wszystkich elementów przez 2. Kiedy możliwe jest podzielenie wszystkich elementów przez 2? Wszystkie elementy tablicy muszą być podzielne przez 2, ponieważ inaczej nie uzyskamy na koniec samych zer. Jednak, aby wszystkie elementy spełniały to kryterium to wystarczy od liczb nieparzystych odjąć 1, aby otrzymać liczbę parzystą.
Na podstawie podanego opisu rowiążmy zadanie dla przykładowej tablicy [3, 2, 3]. Można z niej zrobić tablicę zer poprzez:
| Tablica | Operacja | Łącznie |
|---|---|---|
| [3, 2, 3] | Odejmij jeden z pierwszej i ostatniej pozycji | 2 |
| [2, 2, 2] | Podziel elementy przez 2 | 3 |
| [1, 1, 1] | Odejmij jeden od wszystkich elementów | 6 |
Łącznie potrzeba 6 operacji, aby z tablicy [3, 2, 3] otrzymać [0, 0, 0] przy pomocy dostępnych operacji.
Funkcja policzKroki() przyjmuje jako argument tablicę do wyzerowania. Wyszukuje ona rozwiązanie przy użyciu rekurencji.
(2.) Na początku deklarujemy dwie zmienne: ileZer - zlicza ile jest już zer w tablicy oraz krokow - ile do tej pory wykonano kroków. Następnie (3.) dla każdego elementu tablicy: (4.) sprawdź czy jest nieparzysta wartość. Jeśli tak to (5.) zmniejsz wartość i (6.) zwiększ liczbę kroków. Następnie (7.) podziel element przez 2 i (8.) sprawdź czy element jest zerowy. Jeśli tak to (9.) zwiększ ilość zer. W skrócie pętla wykonuje na każdym elemencie dwie operacje jednocześnie: odejmowanie jeśli istnieje potrzeba i dzielenie przez dwa. Następnie (10.) jeśli nie wszystkie elementy to zera: (11.) zwiększ liczbę kroków i (12.) dodaj ile kroków potrzeba, aby wyzerować zmodyfikowaną tablicę. Na koniec (13.) zwróć liczbę kroków.
W celu przetestowania kodu można skorzystać z poniższego fragmentu, aby wczytać od użytkownika dane, a następnie wypisać liczbę kroków na ekran.
Zauważmy, że na listę operacji końcowych wpływa liczba operacji odejmowania i dzielenia. Pierwsze z nich dotyczy każdej liczby oddzielnie, a druga wszystkich równocześnie. Możliwe jest wyznaczenie wszystkich operacji poprzez zliczenie ile jest bitów 1 w każdej z liczb (tyle trzeba wykonać na liczbie operacji odejmowania). Dodać należy największą liczbę bitów 0 wśród wszystkich liczb (dotyczy to dzielenie przez 2, im więcej bitów 0 tym więcej trzeba wykonać na liczbie operacji odejmowania).
Weźmy ponownie przykład tablicy [1, 2, 3, 4, 5] liczby te zapisane binarnie przedstawiają się następująco:
| Liczba | Binarnie | 0 | 1 |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 10 | 1 | 1 |
| 3 | 11 | 0 | 2 |
| 4 | 100 | 2 | 1 |
| 5 | 101 | 1 | 2 |
Zliczmy teraz wszystkie wartości z kolumny [1], a następnie największą wartość z kolumny [0]. Otrzymujemy (1 + 1 + 2 + 1 + 2) + 2 = 9 czyli wynik, który wcześniej uzyskany inną metodą.
Na podstawie powyższego wyjaśnienia napisz kod i przetestuj jego działanie.