Strona główna » Algorytmy » Teoria Liczb » Liczby Ekonomiczne
$
 

Liczby Ekonomiczne

https://mattomatti.com/a96

Wstęp

Liczby ekonomiczne są to takie liczby, które w rozkładzie na czynniki pierwsze wymagają mniej cyfr do zapisu. Podczas liczenia wymaganych cyfr należy pamiętać, że liczbę pierwszą można podnieść do dowolnej potęgi, ale cyfry potrzebne do zapisu potęgi też należy doliczyć. W przypadku, gdy liczba nie jest ekonomiczna to może zostać nazwana równocyfrową jeśli potrzebne jest tyle samo cyfr, albo wręcz marnotrawną jeśli potrzebne jest więcej cyfr niż w oryginalnym zapisie.

Przykład

Najmniejszą liczbą ekonomiczną jest 125, ponieważ 125 = 53 czyli potrzeba o jedną cyfrę mniej. Warto zauważyć, że wszystkie liczby pierwsze są na pewno liczba równocyfrowymi, ponieważ liczba pierwsza p rozkłada się tylko na p. Z kolei przykładem liczby marnotrawnej jest 6 = 2•3.

Implementacja

Szukanie rozkładu

Poszukiwania dzielników należy rozpocząć od 2. W przypadku napotkania dzielnika d jest on na pewno pierwszy. Jeśli dany dzielnik dzieli tylko raz to na zapis potrzebuje on log(d) pozycji. W przypadku, gdy występuje, więcej niż jeden raz to zawsze opłaca się zapisywać w postaci potęgowej, dlatego dla d występującego k razy potrzeba log(d) + log(k) cyfr.

Do liczenia długości liczby można napisać dodatkową funkcję dlLiczby(), która dla przekazanej liczby a zwróci z ilu cyfr się składa.

  1. int dlLiczby(int a) {
  2.   return int(log10(a)) + 1;
  3. }

Funkcja szukajRozkladu() przyjmuje jeden argument a - liczbę dla której zostanie wyliczone ile potrzebuje cyfr w zapisie rozkładu.

  1. int szukajRozkladu(int a) {
  2.   if (a < 2)
  3.     return 1;
  4.   int dzielnik = 2, licznik = 0, cyfr = 0;
  5.   while (a != 1) {
  6.     licznik = 0;
  7.     while (a % dzielnik == 0) {
  8.       a /= dzielnik;
  9.       licznik++;
  10.     }
  11.     if (licznik != 0) {
  12.       cyfr += dlLiczby(dzielnik);
  13.       cyfr += (licznik > 1 ? dlLiczby(licznik) : 0);
  14.     }
  15.     dzielnik++;
  16.   }
  17.   return cyfr;
  18. }

(2.) Jeśli liczba jest mniejsza od 2 to (3.) zwróć 1. (4.) Zadeklaruj kolejno zmienne całkowitoliczbowe: dzielnik - aktualnie sprawdzany dzielnik, licznik - liczby ile razy dzielnik podzielił oraz cyfr - ile już aktualnie cyfr ma zapis. (5.) Dopóki można rozłożyć liczbę to (6.) zresetuj licznik i (7.) sprawdź czy liczba a dzieli się przez dzielnik. Jeśli tak to (8.) podziel a i (9.) zwiększ licznik. (11.) Jeśli licznik jest różny od zera to (12.) zwiększ ile jest potrzebnych cyfr do zapisu o długość dzielnika oraz (13.) jeśli potęga jest różna od 1 to dolicz długość potęgi. (15.) Zwiększ dzielnik. (17.) Zwróć ile cyfr jest w rozkładzie.

Czy ekonomiczna?

W celu sprawdzenia czy liczba jest ekonomiczna zgodnie z definicją należy sprawdzić czy długość liczby jest mniejsza od ilości cyfr w zapisie przy użyciu liczb pierwszych.

  1. bool czyEkonomiczna(int a) {
  2.   return (dlLiczby(a) > szukajRozkladu(a));
  3. }

Podobne funkcję należałoby napisać dla liczb równocyfrowych oraz marnotrwanych, ale istnieje lepsze rozwiązanie tego problemu.

Podaj rodzaj liczby

W celu wypisania na konsolę rodzaju liczby wystarczy skorzystać z funkcji wypiszRodzaj(), która dla podanej liczby a wypisze na konsolę liczbę oraz jej rodzaj.

  1. void wypiszRodzaj(int a) {
  2.   int cyfrR = szukajRozkladu(a);
  3.   int cyfrL = dlLiczby(a);
  4.   cout << a << " ";
  5.   if (cyfrL > cyfrR) {
  6.     cout << "ekonomiczna";
  7.   } else if (cyfrL == cyfrR) {
  8.     cout << "rownocyfrowa";
  9.   } else {
  10.     cout << "marnotrawna";
  11.   }
  12.   cout << endl;
  13. }

Testowanie funkcji

Prezentowana poniżej funkcja main() wypisze najpierw wszystkie liczby ekonomiczne w zakresie [100, 200], a następnie rodzaje liczb w zakresie [125, 130].

  1. int main () {
  2.   cout << "Liczby ekonomiczne w zakresie [100, 200]\n";
  3.   for (int i = 100; i < 200; i++)
  4.     if (czyEkonomiczna(i))
  5.       cout << i << " ";
  6.   cout << "\n\nRodzaje liczb w zakresie [125, 130]\n";
  7.   for (int i = 125; i < 130; i++)
  8.     wypiszRodzaj(i);
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz funkcję pokazRozklad(), która będzie przyjmowała jedną liczbę a i dla tej liczby wyświetli jej rozkład na czynniki pierwsze.

Następnie zmodyfikuj funkcję wypiszRodzaj() tak, aby wyświetlała kolejno liczbę, rodzaj, a potem rozkład na czynniki pierwsze. Program po uruchomieniu powinien zapytać o zakres [a, b], a następnie wywołać wypiszRodzaj() dla każdej liczby z zakresu.

Przykładowo dla liczb 125 130 zostanie wypisane:

  1. Rodzaje liczb w zakresie [125, 130]
  2. 125     ekonomiczna     5^3
  3. 126     marnotrawna     2 * 3^2 * 7
  4. 127     równocyfrowa    127
  5. 128     ekonomiczna     2^7
  6. 129     równocyfrowa    3 * 43
  7. 130     marnotrawna     2 * 5 * 13