Strona główna » Algorytmy » Teoria Liczb » Liczby Narcystyczne
 

Liczby Narcystyczne

https://mattomatti.com/a57

Definicja

Liczby narcystyczne są to liczby o długości n, które są sumą swoich cyfr. Każda z cyfr przed dodaniem zostaje podniesione do n-tej potęgi.

Przykłady

Przykładowo liczbą narcystyczną jest liczba 371. W celu udowodnienia należy obliczyć, że 33 + 73 + 13 = 27 + 343 + 1 = 371. Warto zauważyć, że wszystkie cyfry są liczbami narcystycznymi zgodnie z prawem potęgowania a1 = a.

Oto pierwsze liczby narcystyczne: 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, ..

Implementacja

Funkcja pomocnicza

Przed napisaniem funkcji sprawdzającej czy dana liczba jest narcystyczna warto napisać funkcję, która będzie podawać jak długa jest podana liczba. W tym celu napiszemy funkcję intLength(), która będzie rekurencyjnie wyliczać długość liczby. Ponadto będzie przyjmować tylko jeden argument a - liczbę, której długość chcemy wyliczyć.

  1. int intLength(int a, int dl = 1){
  2.   return (a > 9) ? intLength(a / 10, dl + 1) : dl;
  3. }

Czy narcystyczna?

Teraz przy użyciu tej funkcji łatwo wyznaczyć do której potęgi musimy podnosić każdą z cyfr. Funkcja isNarcissistic() pozwala sprawdzić dowolną liczbę pod kątem narcystyczności:

  1. bool isNarcissistic(int a){
  2.   int suma = 0, dl = intLength(a);
  3.   for(int i = 0; i < dl; i++){
  4.     suma += pow((int)(a / pow(10, i)) % 10, dl);
  5.   }
  6.   return suma == a;
  7. }

(1.) Funkcja przyjmuje argument a - liczbę do sprawdzenia. Jako wynik zostaje zwrócona wartość logiczna mówiąca czy podana liczba a jest liczba narcystyczna. (2.) Deklarujemy dwie zmienne: suma - tu będziemy wrzucać wyliczoną n-tą potęgę cyfry. Zmienna dl - to długość podanej liczby. (3.) Dla każdej cyfry w liczbie: (4.) pobieramy i-tą cyfrę i podnosimy ją do potęgi dl. Na koniec (6.) zwracamy wynik porównania suma razem z podaną liczbą a.

k liczb Narcystycznych

Najprostszym sposobem na wypisanie k liczb Narcystycznych będzie zastosowanie for:

  1. void kNarcissisticSimple(int a){
  2.   for(int i = 0; i < 1000; i++){
  3.     if(isNarcissistic(i)){
  4.       cout << i << " ";
  5.     }
  6.   }
  7. }

Jednak tego typu metoda choć okazuje się wystarczająca może zostać usprawniona. Jednym ze sposobów jest przetrzymywanie suma n-tych potęg. Przykładowo dla liczb w których zmienia się tylko cyfra jedności można przechowywać sumę n-tych potęg wszystkich cyfr prócz jedności. Sumę będzie trzeba zaktualizować dopiero, gdy będzie zmienimy inną cyfrę niż jedności. Oto kod funkcji, który pozwala na szybsze sprawdzanie czy liczby z przedziału [..]0, [..]9 są narcystyczne:

  1. void isNarcissistic10(int a){
  2.   int temp = 0, dl = intLength(a);
  3.   for(int i = 1; i < dl; i++){
  4.     temp += pow((int)(a / pow(10, i)) % 10, dl);
  5.   }
  6.   for(int i = 0; i < 10; i++){
  7.     if(temp + pow(i, dl) == a + i){
  8.       cout << (temp + pow(i, dl)) << " ";
  9.     }
  10.   }
  11. }

(1.) Funkcja niczego nie zwraca. Wyniki będą wyświetlane bezpośrednio na konsoli. Przyjmowany argument a - to liczba od której program rozpoczyna poszukiwania liczby. Bardzo ważne, żeby liczb a miała na końcu zero. (2.) Deklarujemy dwie zmienne: temp będzie przechowywać sumę n-tych potęg prócz ostatniej. (3. - 5.) Wyliczamy sumę cyfr prócz jedności. (6.) Zmienna tymczasowa przechowuje wynik tylko dla kolejnych dziesięciu liczb po a, dla kolejnych 10 liczb: (7.) sprawdzamy warunek i jeśli jest spełniony to (8.) wypisujemy wynik.

Analiza algorytmu

Tego typu metoda nie jest perfekcyjna, ale pozwala na znaczne zmniejszenie zużycia mocy komputera. W przypadku pętli for i funkcji isNarcissistic() dla jednej dziesiątki liczb wykonamy 10 wywołań funkcji, gdzie zostanie wykonane n operacji potęgowanie i n - 1 operacji dodawania. Łącznie zostanie wykonanych 10(2n - 1) operacji arytmetycznych. W przypadku drugiej implementacji liczba potrzebnych operacji jest znacznie mniejsza. Na początku wyliczamy zmienną temp czyli wykonamy n - 1 operacji potęgowania i n - 2 dodawania. Następnie dla każdej liczby wykonamy dokładnie jedną operację potęgowania i dwie dodawania. Ostatecznie otrzymujemy, że wykonamy 2n + 27 operacji arytmetycznych. Już podczas przeglądania przynajmniej 20 liczb pod względem czy są narcystyczne można zauważyć szybsze znajdowanie. Przy użyciu matematyki łatwo wyliczyć, że im więcej liczb będziemy przeglądać tym efektywniejsze staje się przeszukiwania: aż do 10 razy szybciej.

Testowanie funkcji

Przykładowe zastosowanie napisanych funkcji:

  1. int main () {
  2.   int a;
  3.   cout << "Podaj liczbe: ";
  4.   cin >> a;
  5.   cout << "podana liczba " << a;
  6.   cout << (isNarcissistic(a) ? "":"nie ");
  7.   cout << "jest narcystyczna\n\n";
  8.   cout << "Liczby narcystyczne miedzy 0, a 1000:\n";
  9.   for(int i = 0; i < 1000; i+=10){
  10.     isNarcissistic10(i);
  11.   }
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz program, który dla każdej potęgi 10 wyznaczy najmniejszą liczbę narcystyczną. Przyjmujemy, że pierwsza potęga to 0, a ostatnia 5. Podana funkcja powinna wypisać:

  1. 0, , 153, 1634, 54748, 588834,