{"id":"informatyka-2016-maj-matura-rozszerzona/zad/1.2","paper_id":"informatyka-2016-maj-matura-rozszerzona","number":"1.2","points":4,"ptype":"open","subject":"informatyka","category":"matura","year":2016,"month":"maj","level":"rozszerzona","text":"Zadanie 1.2. (0-4)\nDana jest liczba całkowita a większa od 1. Ułóż i zapisz w wybranej przez siebie notacji\nalgorytm, który znajdzie i wypisze liczbę b skojarzoną z a lub komunikat „NIE”, jeśli taka\nliczba nie istnieje.\nW zapisie algorytmu możesz korzystać tylko z następujących operacji arytmetycznych:\ndodawania, odejmowania, mnożenia, dzielenia całkowitego i obliczania reszty z dzielenia.\nUwaga:\nPrzy ocenie algorytmu będzie brana pod uwagę liczba operacji arytmetycznych\nwykonywanych przez Twój algorytm.\nSpecyfikacja:\nDane:\nLiczba całkowita a > 1.\nWynik:\nLiczba całkowita b skojarzona z a lub komunikat „NIE”, jeśli taka liczba\nnie istnieje.\nAlgorytm:\nWypełnia\negzaminator\nNr zadania\n1.1.\n1.2.\nMaks. liczba pkt.\n1\n4\nUzyskana liczba pkt.\nMIN_1R","answer":null,"answer_text":"Zadanie 1.2. (0-4)\nIII. Rozwiązywanie problemów i\npodejmowanie decyzji […], z zastosowaniem\npodejścia algorytmicznego.\n5. Rozwiązywanie problemów i podejmowanie\ndecyzji […], stosowanie podejścia algorytmicznego.\nZdający:\n2) stosuje podejście algorytmiczne do rozwiązywania\nproblemu;\n4) dobiera efektywny algorytm do rozwiązania\nsytuacji problemowej i zapisuje go w wy branej\nnotacji;\n11) opisuje podstawowe algorytmy i stosuje:\na) algorytmy na liczbach całkowitych;\n18) oblicz liczbę operacji wykonywanych przez\nalgorytm.\nSchemat punktowania\n4 p. - za poprawny algorytm, w tym:\n- 3 p. - za poprawne obliczanie sumy dzielników zadanej liczby (lub potencjalnej liczby\nskojarzonej):\no 1 p. - za sumowanie kolejnych dzielników,\no 1 p. - za poprawną konstrukcję pętli,\no 1 p. - za algorytm o złożoności nie gorszej niż √݊ ;\n- 1 p. - za poprawne ustalenie liczby b oraz za sprawdzenie, czy liczby a i b są skojarzone;\n0 p. - za odpowiedź błędną albo brak odpowiedzi.\nPrzykładowa odpowiedź\nfunkcja sumadz(n) {\nsuma = 1\ni = 2\ndopóki (i*i <= n)\njeżeli (n mod i = 0)\nsuma = suma + i\njeżeli (n div i != i)\nsuma = suma + n/i\ni = i + 1\nzwróć suma\n}\nx = sumadz(a)\ny = sumadz(x-1)\njeżeli (y-1 = a)\nwypisz x-1\nw przeciwnym wypadku\nwypisz „NIE”","solution":"## Poprawna odpowiedź\n\n**Algorytm (pseudokod):**\n\nfunkcja sumadz(n):\nsuma ← 1\ni ← 2\ndopóki i*i ≤ n wykonuj:\njeżeli n mod i = 0:\nsuma ← suma + i\njeżeli n div i ≠ i:\nsuma ← suma + n div i\ni ← i + 1\nzwróć suma\n\nx ← sumadz(a) // x = suma dzielników właściwych a; szukamy b takiego, że b = x - 1\nb ← x - 1\njeżeli b > 1:\ny ← sumadz(b)\njeżeli y = a + 1:\nwypisz b\nw przeciwnym razie:\nwypisz \"NIE\"\nw przeciwnym razie:\nwypisz \"NIE\"\n\n## Sposób 1 - wykorzystanie symetrii definicji\n\n**Idea kluczowa:** definicja skojarzenia mówi `sumadz(a) = b + 1`, więc skoro znamy a, możemy **wyliczyć kandydata** `b = sumadz(a) - 1`. Potem wystarczy sprawdzić drugi warunek: czy `sumadz(b) = a + 1`.\n\n**Krok po kroku:**\n1. Oblicz `x = sumadz(a)`. To koszt O(√a).\n2. Kandydat: `b = x - 1`.\n3. Jeśli `b ≤ 1`, brak skojarzenia (b musi być > 1 z definicji).\n4. Oblicz `y = sumadz(b)`. To koszt O(√b).\n5. Jeśli `y = a + 1` - wypisz b. W przeciwnym razie wypisz „NIE”.\n\nTo daje algorytm O(√a + √b), czyli **O(√n)** ogólnie.\n\n## Sposób 2 - implementacja Python\n\n```python\ndef sumadz(n):\nif n < 2:\nreturn 0\nsuma = 1\ni = 2\nwhile i * i <= n:\nif n % i == 0:\nsuma += i\nif n // i != i:\nsuma += n // i\ni += 1\nreturn suma\n\ndef skojarzona(a):\nx = sumadz(a)\nb = x - 1\nif b <= 1:\nreturn \"NIE\"\nif sumadz(b) == a + 1:\nreturn b\nreturn \"NIE\"\n\nprint(skojarzona(75)) # 48\nprint(skojarzona(140)) # 195\nprint(skojarzona(20)) # NIE\n\n**C++:**\n```cpp\n#include \nusing namespace std;\n\nlong long sumadz(long long n) {\nif (n < 2) return 0;\nlong long s = 1;\nfor (long long i = 2; i * i <= n; i++) {\nif (n % i == 0) {\ns += i;\nif (n / i != i) s += n / i;\n}\n}\nreturn s;\n}\n\nint main() {\nlong long a; cin >> a;\nlong long x = sumadz(a);\nlong long b = x - 1;\nif (b > 1 && sumadz(b) == a + 1) cout << b;\nelse cout << \"NIE\";\nreturn 0;\n}\n\n**Pascal:**\n```pascal\nfunction Sumadz(n: LongInt): LongInt;\nvar s, i: LongInt;\nbegin\nif n < 2 then begin Sumadz := 0; Exit end;\ns := 1;\ni := 2;\nwhile i * i <= n do begin\nif n mod i = 0 then begin\ns := s + i;\nif n div i <> i then s := s + n div i;\nend;\ni := i + 1;\nend;\nSumadz := s;\nend;\n\nvar a, x, b: LongInt;\nbegin\nReadln(a);\nx := Sumadz(a);\nb := x - 1;\nif (b > 1) and (Sumadz(b) = a + 1) then Writeln(b)\nelse Writeln('NIE');\nend.\n\n## Reference informatyczny - suma dzielników w O(√n)\n\n> Reference - Wyznaczanie sumy dzielników:\n> - **Trywialne O(n)**: iteruj i od 1 do n-1, jeśli n mod i = 0 dodaj i. Za wolne dla dużych n.\n> - **O(√n)**: iteruj i od 2 do √n. Każdy dzielnik d < √n ma parę n/d > √n. Sprawdzamy `i*i ≤ n` (nie `i ≤ sqrt(n)` - żeby uniknąć błędów float).\n> - **Pułapka kwadratu doskonałego**: gdy `i = n/i` (np. n=36, i=6), nie dodawaj dwa razy.\n> - **1 jest zawsze dzielnikiem** liczby > 1, dlatego inicjujemy `suma = 1`.\n> - **Liczby doskonałe** (perfect numbers): liczby gdzie suma dzielników właściwych = sama liczba. Przykład: 6 = 1+2+3, 28 = 1+2+4+7+14.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 1.2, max 4 pkt):\n> - **3 pkt** za poprawne obliczanie sumy dzielników:\n> - 1 pkt - sumowanie dzielników\n> - 1 pkt - poprawna konstrukcja pętli\n> - 1 pkt - złożoność **nie gorsza niż O(√n)**\n> - **1 pkt** za poprawne ustalenie b oraz sprawdzenie warunku skojarzenia\n> - **0 pkt** za odpowiedź błędną\n\n**WAŻNE - warunek z treści zadania:** \"Przy ocenie będzie brana pod uwagę liczba operacji arytmetycznych\". Stąd O(√n), nie O(n).\n\n## Typowe pułapki\n\n- **Złożoność O(n)** zamiast O(√n) - utrata 1 pkt. Pętla `dla i = 1 do n-1` to klasyczna pułapka.\n- **Liczenie pary (i, n/i) dwa razy** dla kwadratu doskonałego - wynik zawyżony.\n- **Pomijanie 1** w sumie - wtedy suma zawsze o 1 mniejsza.\n- **Próba enumerowania wszystkich b** od 2 do M - nieoptymalne; lepiej skorzystać z `b = sumadz(a) - 1`.\n- **Pomylenie definicji** - w zadaniu jest `+1` po obu stronach, nie jak w klasycznych amicable numbers gdzie suma a = b a suma b = a.\n- **Pominięcie warunku `b > 1`** - z definicji a i b > 1.\n\n## Złożoność obliczeniowa\n\n- `sumadz(n)`: pętla i = 2 do √n → **O(√n)** operacji.\n- Cały algorytm: 2 wywołania sumadz → **O(√a + √b) = O(√n)**.\n- **Liczba operacji arytmetycznych**: rzędu 2√a (porównanie + mod + dodawanie w każdej iteracji).","image":"img/informatyka-2016-maj-matura-rozszerzona/zad-1.2.webp","solution_image":null,"topics":null,"page_from":3,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2016 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1.2. (0-4)
Dana jest liczba całkowita a większa od 1. Ułóż i zapisz w wybranej przez siebie notacji
algorytm, który znajdzie i wypisze liczbę b skojarzoną z a lub komunikat „NIE”, jeśli taka
liczba nie istnieje.
W zapisie algorytmu możesz korzystać tylko z następujących operacji arytmetycznych:
dodawania, odejmowania, mnożenia, dzielenia całkowitego i obliczania reszty z dzielenia.
Uwaga:
Przy ocenie algorytmu będzie brana pod uwagę liczba operacji arytmetycznych
wykonywanych przez Twój algorytm.
Specyfikacja:
Dane:
Liczba całkowita a > 1.
Wynik:
Liczba całkowita b skojarzona z a lub komunikat „NIE”, jeśli taka liczba
nie istnieje.
Algorytm:
Wypełnia
egzaminator
Nr zadania
1.1.
1.2.
Maks. liczba pkt.
1
4
Uzyskana liczba pkt.
MIN_1R

","answer_text_html":"

Zadanie 1.2. (0-4)
III. Rozwiązywanie problemów i
podejmowanie decyzji […], z zastosowaniem
podejścia algorytmicznego.

\n
  1. Rozwiązywanie problemów i podejmowanie
\n

decyzji […], stosowanie podejścia algorytmicznego.
Zdający:

\n
  1. stosuje podejście algorytmiczne do rozwiązywania
\n

problemu;

\n
  1. dobiera efektywny algorytm do rozwiązania
\n

sytuacji problemowej i zapisuje go w wy branej
notacji;

\n
  1. opisuje podstawowe algorytmy i stosuje:
\n

a) algorytmy na liczbach całkowitych;

\n
  1. oblicz liczbę operacji wykonywanych przez
\n

algorytm.
Schemat punktowania
4 p. - za poprawny algorytm, w tym:

\n\n

skojarzonej):
o 1 p. - za sumowanie kolejnych dzielników,
o 1 p. - za poprawną konstrukcję pętli,
o 1 p. - za algorytm o złożoności nie gorszej niż √݊ ;

\n\n

0 p. - za odpowiedź błędną albo brak odpowiedzi.
Przykładowa odpowiedź
funkcja sumadz(n) {
suma = 1
i = 2
dopóki (i*i <= n)
jeżeli (n mod i = 0)
suma = suma + i
jeżeli (n div i != i)
suma = suma + n/i
i = i + 1
zwróć suma
}
x = sumadz(a)
y = sumadz(x-1)
jeżeli (y-1 = a)
wypisz x-1
w przeciwnym wypadku
wypisz „NIE”

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

Poprawna odpowiedź

\n

Algorytm (pseudokod):

\n

funkcja sumadz(n):
suma ← 1
i ← 2
dopóki i*i ≤ n wykonuj:
jeżeli n mod i = 0:
suma ← suma + i
jeżeli n div i ≠ i:
suma ← suma + n div i
i ← i + 1
zwróć suma

\n

x ← sumadz(a) // x = suma dzielników właściwych a; szukamy b takiego, że b = x - 1
b ← x - 1
jeżeli b > 1:
y ← sumadz(b)
jeżeli y = a + 1:
wypisz b
w przeciwnym razie:
wypisz "NIE"
w przeciwnym razie:
wypisz "NIE"

\n

Sposób 1 - wykorzystanie symetrii definicji

\n

Idea kluczowa: definicja skojarzenia mówi sumadz(a) = b + 1, więc skoro znamy a, możemy wyliczyć kandydata b = sumadz(a) - 1. Potem wystarczy sprawdzić drugi warunek: czy sumadz(b) = a + 1.

\n

Krok po kroku:

\n
  1. Oblicz x = sumadz(a). To koszt O(√a).
  2. Kandydat: b = x - 1.
  3. Jeśli b ≤ 1, brak skojarzenia (b musi być > 1 z definicji).
  4. Oblicz y = sumadz(b). To koszt O(√b).
  5. Jeśli y = a + 1 - wypisz b. W przeciwnym razie wypisz „NIE”.
\n

To daje algorytm O(√a + √b), czyli O(√n) ogólnie.

\n

Sposób 2 - implementacja Python

\n

```python
def sumadz(n):
if n < 2:
return 0
suma = 1
i = 2
while i * i <= n:
if n % i == 0:
suma += i
if n // i != i:
suma += n // i
i += 1
return suma

\n

def skojarzona(a):
x = sumadz(a)
b = x - 1
if b <= 1:
return "NIE"
if sumadz(b) == a + 1:
return b
return "NIE"

\n

print(skojarzona(75)) # 48
print(skojarzona(140)) # 195
print(skojarzona(20)) # NIE

\n

C++:
```cpp
#include <iostream>
using namespace std;

\n

long long sumadz(long long n) {
if (n < 2) return 0;
long long s = 1;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
s += i;
if (n / i != i) s += n / i;
}
}
return s;
}

\n

int main() {
long long a; cin >> a;
long long x = sumadz(a);
long long b = x - 1;
if (b > 1 && sumadz(b) == a + 1) cout << b;
else cout << "NIE";
return 0;
}

\n

Pascal:
```pascal
function Sumadz(n: LongInt): LongInt;
var s, i: LongInt;
begin
if n < 2 then begin Sumadz := 0; Exit end;
s := 1;
i := 2;
while i * i <= n do begin
if n mod i = 0 then begin
s := s + i;
if n div i <> i then s := s + n div i;
end;
i := i + 1;
end;
Sumadz := s;
end;

\n

var a, x, b: LongInt;
begin
Readln(a);
x := Sumadz(a);
b := x - 1;
if (b > 1) and (Sumadz(b) = a + 1) then Writeln(b)
else Writeln('NIE');
end.

\n

Reference informatyczny - suma dzielników w O(√n)

\n
Reference - Wyznaczanie sumy dzielników:
- Trywialne O(n): iteruj i od 1 do n-1, jeśli n mod i = 0 dodaj i. Za wolne dla dużych n.
- O(√n): iteruj i od 2 do √n. Każdy dzielnik d < √n ma parę n/d > √n. Sprawdzamy i*i ≤ n (nie i ≤ sqrt(n) - żeby uniknąć błędów float).
- Pułapka kwadratu doskonałego: gdy i = n/i (np. n=36, i=6), nie dodawaj dwa razy.
- 1 jest zawsze dzielnikiem liczby > 1, dlatego inicjujemy suma = 1.
- Liczby doskonałe (perfect numbers): liczby gdzie suma dzielników właściwych = sama liczba. Przykład: 6 = 1+2+3, 28 = 1+2+4+7+14.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 1.2, max 4 pkt):
- 3 pkt za poprawne obliczanie sumy dzielników:
- 1 pkt - sumowanie dzielników
- 1 pkt - poprawna konstrukcja pętli
- 1 pkt - złożoność nie gorsza niż O(√n)
- 1 pkt za poprawne ustalenie b oraz sprawdzenie warunku skojarzenia
- 0 pkt za odpowiedź błędną
\n

WAŻNE - warunek z treści zadania: "Przy ocenie będzie brana pod uwagę liczba operacji arytmetycznych". Stąd O(√n), nie O(n).

\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}