{"id":"informatyka-2019-maj-matura-rozszerzona/zad/4.2","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"4.2","points":4,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 4.1.\n\nSilnią liczby naturalnej k większej od 0 nazywamy wartość iloczynu 1·2 k i oznaczamy przez k!. Przyjmujemy, że 0!=1. Zatem mamy:\n- 0! = 1\n- 1! = 1\n- 2! = 1·2 = 2\n- 3! = 1·2·3 = 6\n- 4! = 1·2·3·4 = 24 itd.\n\nDowolną liczbę naturalną możemy rozbić na cyfry, a następnie policzyć sumę silni jej cyfr. Na przykład dla liczby 343 mamy 3! + 4! + 3! = 6 + 24 + 6 = 36.\n\nW pliku przyklad.txt znajduje się jedna taka liczba: 145 (1!+4!+5! =1+24+120 =145).\n\nPodaj, w kolejności ich występowania w pliku liczby.txt, wszystkie liczby, które są równe sumie silni swoich cyfr.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**Liczby z pliku liczby.txt równe sumie silni swoich cyfr (w kolejności występowania):**\n\n2\n145\n1\n40585\n\n**Te liczby to tzw. \"factorions\" - w dziesiętnym wszystkich jest dokładnie 4: 1, 2, 145, 40585.**\n\n## Sposób 1 - implementacja Python\n\n```python\n# Precomputed silnie 0! 9!\nsilnie = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]\n\ndef suma_silni_cyfr(n):\ns = 0\nif n == 0:\nreturn 1 # 0! = 1\nwhile n > 0:\ns += silnie[n % 10]\nn //= 10\nreturn s\n\nwyniki = []\nwith open('liczby.txt', encoding='utf-8') as f:\nfor linia in f:\nn = int(linia.strip())\nif suma_silni_cyfr(n) == n:\nwyniki.append(n)\n\nfor w in wyniki:\nprint(w)\n# 2\n# 145\n# 1\n# 40585\n\n**Weryfikacja:**\n- 1: 1! = 1 ✓\n- 2: 2! = 2 ✓\n- 145: 1! + 4! + 5! = 1 + 24 + 120 = **145** ✓\n- 40585: 4! + 0! + 5! + 8! + 5! = 24 + 1 + 120 + 40320 + 120 = **40585** ✓\n\n## Sposób 2 - implementacja Pascal\n\n```pascal\nprogram SumaSilniCyfr;\nvar\nf: TextFile;\nn, m, suma, cyfra, i: LongInt;\nsilnie: array[0 9] of LongInt;\nbegin\nsilnie[0] := 1;\nfor i := 1 to 9 do silnie[i] := silnie[i-1] * i;\nAssignFile(f, 'liczby.txt');\nReset(f);\nwhile not Eof(f) do\nbegin\nReadLn(f, n);\nm := n; suma := 0;\nif m = 0 then suma := 1\nelse while m > 0 do\nbegin\ncyfra := m mod 10;\nsuma := suma + silnie[cyfra];\nm := m div 10;\nend;\nif suma = n then WriteLn(n);\nend;\nCloseFile(f);\nend.\n\n## Sposób 3 - implementacja C++\n\n```cpp\n#include \n#include \nusing namespace std;\n\nint silnie[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};\n\nlong long sumaSilniCyfr(long long n) {\nif (n == 0) return 1;\nlong long s = 0;\nwhile (n > 0) {\ns += silnie[n % 10];\nn /= 10;\n}\nreturn s;\n}\n\nint main() {\nifstream plik(\"liczby.txt\");\nlong long n;\nwhile (plik >> n) {\nif (sumaSilniCyfr(n) == n) cout << n << endl;\n}\nreturn 0;\n}\n\n## Reference informatyczny - wydobywanie cyfr liczby\n\n> Reference - Algorytm na rozkład liczby na cyfry:\n> ```\n> dopóki n > 0\n> cyfra ← n mod 10\n> n ← n div 10\n> ```\n> Złożoność: O(log₁₀(n)) - liczba cyfr.\n>\n> Reference - Silnia:\n> - 0! = 1, n! = n · (n-1)! dla n > 0.\n> - Rosnie szybko: 10! = 3 628 800, 12! przekracza 32-bit int.\n> - Pre-kompute: tablica silni[0 9] = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880].\n>\n> Reference - Factoriony:\n> - W dziesiętnym SĄ TYLKO 4 factoriony: 1, 2, 145, 40585. Udowodniono, że więcej nie istnieje.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 4.2, max 4 pkt):\n> - **4 pkt** - wszystkie 4 liczby (2, 145, 1, 40585) w prawidłowej kolejności\n> - **1 pkt** za każdą poprawną liczbę w wyniku\n> - **0 pkt** - błędna albo brak\n\n## Typowe pułapki\n\n- **Pominięcie 0! = 1** - bez tego dla liczby 40585 wynik byłby 23+1+120+40320+120 = 40584 (lub mocno błędny).\n- **Kolejność w wyniku** - musi być w kolejności pojawiania się w pliku liczby.txt (nie alfabetycznie/numerycznie).\n- **Złe wpisanie tablicy silni** - najczęstszy błąd: pomylenie 5! = 120 z 6! = 720.\n- **Overflow w Pascal/C++** - 9! = 362880 mieści się w 32-bit int, ale uważać dla wielocyfrowych liczb.\n- **Brak warunku zatrzymania pętli** - gdy n=0 (liczba 0 nie pojawi się w danych, bo zakres 1-100000).\n\n## Złożoność obliczeniowa\n\n- Wczytanie pliku: O(n) - 500 wierszy.\n- Obliczenie sumy silni cyfr: O(log n) ≈ 6 operacji (max 6 cyfr).\n- Łącznie: **O(n · log(max))** ≈ 3000 operacji - błyskawicznie.\n- Pamięć: O(1) (tablica silni stała).","image":null,"solution_image":null,"topics":null,"page_from":null,"source":"maturazai","answer_source":null,"answer_text_source":null,"solution_source":"maturazai","text_source":"maturazai","source_label":"Informatyka · Matura · maj 2019 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 4.1.

\n

Silnią liczby naturalnej k większej od 0 nazywamy wartość iloczynu 1·2 k i oznaczamy przez k!. Przyjmujemy, że 0!=1. Zatem mamy:

\n\n

Dowolną liczbę naturalną możemy rozbić na cyfry, a następnie policzyć sumę silni jej cyfr. Na przykład dla liczby 343 mamy 3! + 4! + 3! = 6 + 24 + 6 = 36.

\n

W pliku przyklad.txt znajduje się jedna taka liczba: 145 (1!+4!+5! =1+24+120 =145).

\n

Podaj, w kolejności ich występowania w pliku liczby.txt, wszystkie liczby, które są równe sumie silni swoich cyfr.

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

Liczby z pliku liczby.txt równe sumie silni swoich cyfr (w kolejności występowania):

\n

2
145
1
40585

\n

Te liczby to tzw. "factorions" - w dziesiętnym wszystkich jest dokładnie 4: 1, 2, 145, 40585.

\n

Sposób 1 - implementacja Python

\n

```python

\n

Precomputed silnie 0! 9!

\n

silnie = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

\n

def suma_silni_cyfr(n):
s = 0
if n == 0:
return 1 # 0! = 1
while n > 0:
s += silnie[n % 10]
n //= 10
return s

\n

wyniki = []
with open('liczby.txt', encoding='utf-8') as f:
for linia in f:
n = int(linia.strip())
if suma_silni_cyfr(n) == n:
wyniki.append(n)

\n

for w in wyniki:
print(w)

\n

2

\n

145

\n

1

\n

40585

\n

Weryfikacja:

\n\n

Sposób 2 - implementacja Pascal

\n

```pascal
program SumaSilniCyfr;
var
f: TextFile;
n, m, suma, cyfra, i: LongInt;
silnie: array[0 9] of LongInt;
begin
silnie[0] := 1;
for i := 1 to 9 do silnie[i] := silnie[i-1] * i;
AssignFile(f, 'liczby.txt');
Reset(f);
while not Eof(f) do
begin
ReadLn(f, n);
m := n; suma := 0;
if m = 0 then suma := 1
else while m > 0 do
begin
cyfra := m mod 10;
suma := suma + silnie[cyfra];
m := m div 10;
end;
if suma = n then WriteLn(n);
end;
CloseFile(f);
end.

\n

Sposób 3 - implementacja C++

\n

```cpp
#include <iostream>
#include <fstream>
using namespace std;

\n

int silnie[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

\n

long long sumaSilniCyfr(long long n) {
if (n == 0) return 1;
long long s = 0;
while (n > 0) {
s += silnie[n % 10];
n /= 10;
}
return s;
}

\n

int main() {
ifstream plik("liczby.txt");
long long n;
while (plik >> n) {
if (sumaSilniCyfr(n) == n) cout << n << endl;
}
return 0;
}

\n

Reference informatyczny - wydobywanie cyfr liczby

\n
Reference - Algorytm na rozkład liczby na cyfry:
```
dopóki n > 0
cyfra ← n mod 10
n ← n div 10
```
Złożoność: O(log₁₀(n)) - liczba cyfr.

Reference - Silnia:
- 0! = 1, n! = n · (n-1)! dla n > 0.
- Rosnie szybko: 10! = 3 628 800, 12! przekracza 32-bit int.
- Pre-kompute: tablica silni[0 9] = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880].

Reference - Factoriony:
- W dziesiętnym SĄ TYLKO 4 factoriony: 1, 2, 145, 40585. Udowodniono, że więcej nie istnieje.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 4.2, max 4 pkt):
- 4 pkt - wszystkie 4 liczby (2, 145, 1, 40585) w prawidłowej kolejności
- 1 pkt za każdą poprawną liczbę w wyniku
- 0 pkt - błędna albo brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}