Od zera do celu

Cel

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ą?

Przykład

Weźmy przykładowo tablicę [1, 2, 3, 4, 5]. Można ją osiagnać kolejno poprzez:

Łącznie potrzeba 9 operacji, aby z tablicy samych zer otrzymać tablicę [1, 2, 3, 4, 5].

Analiza

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:

Łącznie potrzeba 6 operacji, aby z tablicy [3, 2, 3] otrzymać [0, 0, 0] przy pomocy dostępnych operacji.

Implementacja

Funkcja policzKroki() przyjmuje jako argument tablicę do wyzerowania. Wyszukuje ona rozwiązanie przy użyciu rekurencji.

1. int policzKroki(int* tab, int n) {
2.   int ileZer = 0, krokow = 0;
3.   for (int i = 0; i < n; i++) {
4.     if (tab[i] % 2 == 1) {
5.       tab[i]--;
6.       krokow++;
7.     }
8.     tab[i] /= 2;
9.     if (tab[i] == 0)
10.       ileZer++;
11.   }
12.   if (ileZer < n) {
13.     krokow++;
14.     krokow += policzKroki(tab, n);
15.   }
16.   return krokow;
17. }

(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 (8.) podziel element przez 2 i (9.) sprawdź czy element jest zerowy. Jeśli tak to (10.) 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 (11.) jeśli nie wszystkie elementy to zera: (12.) zwiększ liczbę kroków i (13.) dodaj ile kroków potrzeba, aby wyzerować zmodyfikowaną tablicę. Na koniec (15.) zwróć liczbę kroków.

Testowanie funkcji

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.

1. int main () {
2.   int n;
3.   cout << "Ile elementow ma lista?\n n = ";
4.   cin >> n;
5.   cout << "Podaj liste elementow:\n";
6.   int* tab = new int[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   cout << policzKroki(tab, n);
10.   system("pause");
11.   return 0;
12. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Wprowadzenie

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).

Przykład

Weźmy ponownie przykład tablicy [1, 2, 3, 4, 5] liczby te zapisane binarnie przedstawiają się następująco:

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ą.

Zadanie

Na podstawie powyższego wyjaśnienia napisz kod i przetestuj jego działanie.

• Kod źródłowy Zadanie 1