Strona główna » Algorytmy » Artykuły » Liczba Wspak
 

Liczba Wspak

https://mattomatti.com/a0199

Cel

Podczas rozwiązywania różnych zadań informatycznych może pojawić się potrzeba zapisania liczby wspak. W tym artykule zostało omówione kilka sposobów realizacji tego zadania w zależności od treści zadania. Ponadto zostały dodane opisy, które podpowiadają zaletę lub wadę danej metody.

Implementacja

Wspak Arytmetycznie

Jest to najpopularniejsza metoda, która polega na usuwaniu kolejnych cyfr z końca i dopisywania ich do zmiennej wynikowej z prawej strony. Taki kod składa się z jednej pętli i wymaga zastosowania dwóch zmiennych. Oto przykładowy kod, który realizuje funkcję wspak():

  1. int wspak(int a) {
  2.   int wynik = 0;
  3.   while (a > 0) {
  4.     wynik *= 10;
  5.     wynik += a % 10;
  6.     a /= 10;
  7.   }
  8.   return wynik;
  9. }

Funkcja składa się z jednej pętli, gdzie kolejno liczby są przesuwane w lewo o jedną pozycję poprzez mnożenie przez 10, a następnie dodawana jest kolejna cyfra, która później musi być usunięta z liczby wejściowej. Po usunięciu wszystkich cyfr zostanie tylko 0, a więc pętla jest skończona.

Wykorzystując stos

Do zapisywania liczby wspak można też skorzystać z stosu, który w swojej naturze wszystko co zostanie położone, a następnie zdjęte jest w kolejności odwrotnej. Można to wykorzystać kładąc na stosie kolejn odczytane cyfry z liczby, a następnie odczytaniu ich i ustawieniu w liczbie wynikowej. Oto kod realizujący podany algorytm:

  1. int wspak(int a) {
  2.   stack<int> stos;
  3.   while (a > 0) {
  4.     stos.push(a % 10);
  5.     a /= 10;
  6.   }
  7.   int wynik = 0;
  8.   int mn = 1;
  9.   while (!stos.empty()) {
  10.     wynik += mn * stos.top();
  11.     stos.pop();
  12.     mn *= 10;
  13.   }
  14.   return wynik;
  15. }

Tym razem potrzebne są dwie pętle. Pierwsza z nich wrzuca wszystko na stos, a druga zdejmuje te cyfry do stosu i dodaje do wyniku. W tym przypadku należy pamiętać, że dodawą liczbę należy pomnożyć przez kolejne potęgi liczby 10, aby cyfra znalazła się na właściwym miejscu.

Zamiana na Tekst

Innym sposobem na odwrócenie liczby wspak jest konwersja jej na tekst, który można odwrócić (zazwyczaj języki programowania mają gotowe do tego funkcje jak również konwersji liczby na tekst i odwrotnie). W tym jednak kryje się problem wydajności. Konwersja liczby na tekst i odwrotnie wymaga bardzo dużo obliczeń. Także tego algorytmu najlepiej nie używać, aby oparty o niego program nie działał bardzo wolno. Należy jednak przyznać, że kod wygląda bardzo "elegancko":

  1. int wspak(int a) {
  2.   string s = to_string(a);
  3.   reverse(s.begin(), s.end());
  4.   return stoi(s);
  5. }

Wniosek płynie taki, że jedno polecenie można rozwiązać wieloma różnymi algorytmami, ale zawsze należy się zastanowić czy wybrany algorytm jest odpowiedni do pisanego programu.

Testowanie funkcji

Wszystkie powyższe algorytmy tworzące liczbę wspak można przetestować przy pomocy poniższego kodu:

  1. int main () {
  2.   int a;
  3.   cout << "Podaj liczbe:\n a = ";
  4.   cin >> a;
  5.   int wynik = wspak(a);
  6.   cout << "a zapisane wspak to " << wynik;
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Przedstawione algorytmy działają poprawnie tylko dla liczb naturalnych. Napisz wersję funkcji wspak(), która będzie potrafiła zamieniać również liczby ujemne. Przykładowo dla -123 wynikiem powinno być -321.