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

Liczby Irysowe

https://mattomatti.com/a0068

Definicja

Liczba Irysowa to taka liczba naturalna, której suma cyfr danej liczby jest równa iloczynowi cyfr tej liczby. Innymi słowy przyjmując, że cyfra składa się z n cyfr kolejno od najbardziej znaczęcej: c1, c2,.. , cn to wtedy spełnia warunek: c1 + c2 + .. + cn = c1c2..cn.

Przykład

Najmniejszą liczbą irysową jest 1. Innym przykładem jest liczba 123, gdzie 1+2+3 = 1·2·3. Warto zauważyć, że jeśli liczba n jest liczbą Irysową to wszystkie liczby powstałe z permutacji cyfr tej liczby też będą liczbami Irysowymi. Jest to cecha, która wynika z przemienności mnożenia oraz dodawania.

Ciąg

Kolejne liczby Irysowe można ustawić w następujący ciąg:
1, 2, 3, 4, 5, 6, 7, 8, 9, 22, 123, 132, 213, 231, 312, 321, 1124, 1142, ...

Implementacja

Sprawdzenie czy dana liczba jest liczbą Irysować sprowadza się do pobierania kolejnych cyfr z liczby, a następnie zwiększania sumy i przemnożenia iloczynu. Wynikiem działania funkcji jest porównanie obliczonej sumy oraz iloczynu.

C++
C#
  1. bool czyIrysowa(int a) {
  2.   int suma = 0;
  3.   int iloczyn = 1;
  4.   while (a > 0) {
  5.     int c = a % 10;
  6.     suma += c;
  7.     iloczyn *= c;
  8.     a /= 10;
  9.   }
  10.   return suma == iloczyn;
  11. }

Testowanie funkcji

W celu wypisania n pierwszych liczb Irysowych można skorzystać z poniższego fragmentu kodu:

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Ile liczb Irysowych wypisac?\n n = ";
  4.   cin >> n;
  5.   cout << "\nKolejne liczby Irysowe to:\n";
  6.   for (int i = 1; n > 0; i++) {
  7.     if (czyIrysowa(i)) {
  8.       cout << i << endl;
  9.       n--;
  10.     }
  11.   }
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz funkcję szukajUnikalnychIrysowych(), która wypisze n pierwszych liczb Irysowych, ale bez permutacji liczb już wypisanych. Oznacza to, że przykładowo liczba 123 wyklucz z wypisania jej permutacji: 132, 213, 231, 312 oraz 321. Zakładamy, że spośród wszystkich permutacji zawsze wypisujemy najmniejszą wartość. Przykładowo dla n = 15 program ma wypisać:

  1. 1, 2, 3, 4, 5, 6, 7, 8, 9, 22, 123, 1124, 11125, 11133, 11222