Przetwarzanie Liczby

Cel

Dana jest pewna liczba początkowa x i końcowa y. Napisz algorytm, który przy użyciu podanych operacji arytmetycznych zwróci ile najmniej trzeba wykonać kroków, aby z x uzyskać y.

Zakładamy, że liczby 0 ≤ x, y ≤ 100 000. Operacja jest zdefiniowana przez parę (znak, liczba). Przykładowo para (+, 2) oznacza, że x' = x + 2. Zakładamy, że poprawne operacje to dodawanie, odejmowanie, mnożenia oraz dzielenie (pod warunkiem, że wynikiem operacji jest liczba całkowita).

Analiza Zadania

Program musi przeszukać wszystkie możliwe rozwiązania. Należy jednak zauważyć, że takie obliczenia należy odpowiednio ograniczyć. Otóż mogą zostać zdefiniowane dwie przeciwne operacj. Wtedy program może błąkać się pomiędzy dwoma wartościami. Przykładowo jeśli mamy operacje +1, -1 to program będzie przechodził przykładowo pomiędzy 1 i 2.

Podobny problem pojawia się podczas przeszukiwania BFS grafu. Zabezpieczenie algorytmu przed wpadnięciem w nieskończoną pętle polega na przechowywaniu / odznaczaniu elementów już odwiedzonych. Dzięki temu algorytm w momencie napotkania tego samego wierzchołka już drugi raz nie wykonuje dla niego określonych operacji.

Zauważmy, że przekształcenia liczby x na y możnaby przedstawić w postaci grafu. Program jednak nie będzie generował grafu dla wszystkich możliwych wyników, ponieważ nie ma to większego sensu - wszystkie gałęzie można na bieżąco określić. Ważne jest, aby po odwiedzeniu kolejnej liczby sprawdzić czy nie była już przeglądana. Jeśli tak to algorytm kończy przeglądanie, a jeśli nie to kontynuuje. Możliwy zakres liczb również pozwala ograniczyć ilość potrzebnych operacji.

Implementacja

Struktury

W programie zostaną wykorzystane dwie struktury. Pierwsza z nich przypomina krok wykonywany w agorytmie BFS. W tym przypadku będzie przetrzymywana obliczona kolejna wartość przekształcenia oraz poziom czyli ile do tej pory wykonano operacji.

1. struct operacja {
2.   char znak;
3.   int wartosc;
4. };

Z kolei druga struktura dotyczy przechowywania informacji o możliwej operacji arytmetycznej.

1. struct krok {
2.   int liczba;
3.   int poziom;
4. };

Ile kroków

Funkcja ileOperacji() przyjmuje następujące argumenty: x i y tj. początkowa i końcowa wartość, operacje - możliwe przekształcenia oraz min i max zakres poszukiwań. Jako wynik zostaje zwrócona liczba, która określa ile potrzeba przekształceń, aby z x otrzymać y, albo -1 jeśli jest to niemożliwe.

1. int ileOperacji(int x, int y, vector<operacja> operacje, int min = 0, int max = 100000) {
2.   vector<int> poprz;
3.   queue<krok> kolejka;
4.   krok teraz = { x, 0 };
5.   kolejka.push(teraz);
6.   while (!kolejka.empty()) {
7.     teraz = kolejka.front();
8.     kolejka.pop();
9.     if (teraz.liczba == y) {
10.       return teraz.poziom;
11.     }
12.     for (int i = 0; i < operacje.size(); i++) {
13.       int nowa = wykonajOperacje(teraz.liczba, operacje[i]);
14.       bool dodaj = find(poprz.begin(), poprz.end(), nowa) == poprz.end();
15.       if (dodaj && nowa >= min && min <= max) {
16.         poprz.push_back(nowa);
17.         krok kolejny = { nowa, teraz.poziom + 1 };
18.         kolejka.push(kolejny);
19.       }
20.     }
21.   }
22.   return -1;
23. }

Na początku deklarowana jest pusta lista oraz kolejka. Do kolejki dodawany jest pierwsze "węzeł" tj. wartość początkowa o poziomie 0 (czyli, że żadna operacja nie została wykonana). Dopóki kolejka nie jest pusta to pobierany jest element z początku kolejki. Następnie należy sprawdzić czy jest on elementem szukanym. Jeśli tak to należy go zwrócić. W przeciwnym wypadku do kolejki należy dodać wszystkie możliwe przekształcenia na wartości, które do tej pory nie były przeglądane i które mieszczą się w zakresie.

Wykonanie operacji

Funkcję do wykonania operacji jest najwygodniej zaimplementować poprzez instrukcję switch. W przypadku, gdy dana liczba nie może zostać podzielona to wystarczy zwrócić aktualną wartość. Ze względu na to, że znajduje się ona już na liście to drugi raz nie będzie rozpatrywana.

1. int wykonajOperacje(int liczba, operacja op) {
2.   switch (op.znak) {
3.   case '+':
4.     return liczba + op.wartosc;
5.   case '-':
6.     return liczba - op.wartosc;
7.   case '*':
8.     return liczba * op.wartosc;
9.   case '/':
10.     if (liczba % op.wartosc == 0)
11.       return liczba / op.wartosc;
12.     break;
13.   }
14.   return liczba;
15. }

Testowanie funkcji

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

1. int main() {
2.   int x, y, n, t;
3.   char c;
4.   cout << "Podaj poczatkowa wartosc\n x = ";
5.   cin >> x;
6.   cout << "Podaj wartosc do uzyskania\n y = ";
7.   cin >> y;
8.   cout << "Ile jest mozliwych operacji?\n n = ";
9.   cin >> n;
10.   cout << "Podaj je (operacja liczba):\n";
11.   vector<operacja> operacje;
12.   while (n > 0) {
13.     cin >> c >> t;
14.     operacja op = {c, t};
15.     operacje.push_back(op);
16.     n--;
17.   }
18.   int wynik = ileOperacji(x, y, operacje);
19.   if (wynik == -1) {
20.     cout << "Nie mozna uzyskac " << y;
21.   } else {
22.     cout << "Potrzebnych operacji: " << wynik;
23.   }
24.   system("pause");
25.   return 0;
26. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Zmodyfikuj program tak, aby na koniec wyświetlił informację jakie operacje należy wykonać, aby liczbę x przekształcić w y. Postaraj się wypisać jak najmniej nawiasów. Przykładowo po podaniu następujących danych:

1. x = 11
2. y = 14
3. operacje: *2, -2, /3

program powinien zwrócić:

1. (11-2-2)*2

• Kod źródłowy Zadanie 1