Strona główna » Algorytmy » Artykuły » Liczby Do Góry Nogami
49
 

Liczby Do Góry Nogami

Definicja

Liczbą do Góry Nogami nazywamy liczbę, której każda i-ta cyfra od lewej strony oraz i-ta od prawej strony dają w sumie liczbę 10.

Przykład

Najmniejszym reprezentatem definiowanej grupy liczb jest 5, ponieważ 5 + 5 = 10. Kolejnym przykładem jest 19, gdzie 1 + 9 = 10. Z bardziej złożonych przypadków 1379 też jest, ponieważ 1 + 9 = 10 oraz 3 + 7 = 10.

Ciąg liczb

Liczby można ustawić w następujący ciąg: 5, 19, 28, 37, 46, 55, 64, 73, 82, 91, 159, 258, ..

Analiza

Warunek liczb podany w definicji wymusza na liczbie pewne właściwości. Po pierwsze w liczbie Do Góry Nogami nie może występować 0. Jest to spowodowane faktem, że nie istnieje taka cyfra c, żeby 0 + c = 10. Dotyczy to również cyfry 0, gdzie warunek nigdy nie będzie spełniony.

Innym ciekawym spotrzeżeniem jest fakt, że jeśli liczba składa się z nieparzystej liczby cyfr to środkowa cyfra musi wynosić 5. Wynika to z faktu, że w takim przypadku środkowa cyfra c jest sumowana sama ze sobą i właśnie c = 5, jest jedynym poprawnym rozwiązaniem.

Implementacja

Przez Podział

Najprostszy sposób polega na podziale liczby na część lewą, środkową oraz prawą. Środkowa część istnieje jedynie dla liczb o nieparzystej liczbie cyfr i musi się równać 5. Dla części lewej i prawej jedną z nich zapisujemy wspak. Następnie wybieramy kolejne cyfry i sprawdzamy czy wszystkie takie pary sumują się do wartości 10. Jeśli żaden z wymienionych warunków nie jest spełniony to na pewno a nie jest liczbą do Góry Nogami.

Poniższa funkcja czyDoGoryNogami() sprawdza czy przekazana liczba a jest liczbą do Góry Nogami i zwraca wartość logiczną na ten temat.

  1. bool czyDoGoryNogami(int a) {
  2.   if (a <= 0)
  3.     return false;
  4.   int dl = log10(a) + 1;
  5.   int wybierz = pow(10, dl / 2);
  6.   int prawa = wspak(a % wybierz);
  7.   int lewa = a / wybierz;
  8.   if (dl % 2 == 1) {
  9.     if (lewa % 10 != 5)
  10.       return false;
  11.     lewa /= 10;
  12.   }
  13.   while (lewa > 0 && prawa > 0) {
  14.     if (lewa % 10 + prawa % 10 != 10)
  15.       return false;
  16.     lewa /= 10;
  17.     prawa /= 10;
  18.   }
  19.   return lewa == 0 && prawa == 0;
  20. }

Na początku funkcja odrzuca przypadki na którą odpowiedź jest oczywista. Następnie wyliiczamy długość liczby i dzielimy liczbę na dwie części. Lewa strona może zawierać część środkową, więc należy ją sprawdzić i usunąć. Następnie w pętli sumowane są kolejne cyfry dopóki obydwie części liczby są różne od 0. Na koniec należy sprawdzić, że obydwie części zostały wyzerowane.

Charakterystyczna Suma

Jeśli zostanie zsumowana liczba a oraz liczba a zapisana wspak to dla liczby do Góry Nogami zostanie otrzymana bardzo charakterystyczna suma, która będzie składała się z tylu jedynek na początku jaka jest ilość cyfr a i na końcu będzie 0. Wynika to z faktu, że sumy kolejnych cyfr wyniosą dokładnie 10. Przykładowo 19 + 91 = 110, albo 1379 + 9731 = 11110.

Oto kolejna przykładowa implementacja funkcji czyDoGoryNogami():

  1. bool czyDoGoryNogami(int a) {
  2.   if (a <= 0)
  3.     return false;
  4.   int dl = log10(a) + 1;
  5.   int wybierz = pow(10, dl / 2);
  6.   int prawa = wspak(a % wybierz);
  7.   int lewa = a / wybierz;
  8.   if (dl % 2 == 1) {
  9.     if (lewa % 10 != 5)
  10.       return false;
  11.     lewa /= 10;
  12.   }
  13.   while (lewa > 0 && prawa > 0) {
  14.     if (lewa % 10 + prawa % 10 != 10)
  15.       return false;
  16.     lewa /= 10;
  17.     prawa /= 10;
  18.   }
  19.   return lewa == 0 && prawa == 0;
  20. }

Na początku sumowana jest liczba a i jej wersja wspak. Następnie należy się upewnić, że ostatnia cyfra to 0 i ją usunąć. Potem wystarczy sprawdzić, że każda kolejna liczba to 1 i jeśli wszystkie warunki zostaną spełnione to zwrócić prawdę.

Testowanie funkcji

W celu przetestowania jak działa napisana funkcja można skorzystać z poniższego fragmentu kodu:

  1. int main () {
  2.   int a;
  3.   cout << "Podaj liczbe do sprawdzenia\n a = ";
  4.   cin >> a;
  5.   bool wynik = czyDoGoryNogami(a);
  6.   cout << "Liczba " << (wynik ? "" : "nie ");
  7.   cout << "jest liczba do gory nogami";
  8.   system("pause");
  9.   return 0;
  10. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1