{"id":"informatyka-2018-czerwiec-matura-rozszerzona/zad/2.3","paper_id":"informatyka-2018-czerwiec-matura-rozszerzona","number":"2.3","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2018,"month":"czerwiec","level":"rozszerzona","text":"Zadanie 2.3. (0-2)\nAby przyśpieszyć rekurencyjne obliczanie wartości n-tego wyrazu ciągu Fibonacciego, można\nskorzystać z następujących wzorów, prawdziwych dla dowolnego całkowitego k ≥ 2:\nF2k=(Fk+1)2 -(Fk-1)2\nF2k-1=(Fk)2 +(Fk-1)2\nZapisz w wybranej przez siebie notacji (w postaci listy kroków, w języku programowania lub\nw pseudokodzie) algorytm rekurencyjny, który służy do obliczania wartości liczby Fn dla\ndowolnego n ≥ 1 i korzysta z tych wzorów.\nAlgorytm.\nMIN_1R","answer":null,"answer_text":"Zadanie 2.3. (0-2)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […]\nz zastosowaniem podejścia\nalgorytmicznego.\n5. Rozwiązywanie problemów\ni podejmowanie decyzji […], stosowanie\npodejścia algorytmicznego.\nZdający:\n1) analizuje, modeluje i rozwiązuje sytuacje\nproblemowe z różnych dziedzin;\n2) stosuje podejście algorytmiczne do\nrozwiązywania problemu;\n4) dobiera efektywny algorytm do\nrozwiązania sytuacji problemowej\ni zapisuje go w wybranej notacji;\n5) posługuje się podstawowymi\ntechnikami algorytmicznymi;\n11) opisuje podstawowe algorytmy\ni stosuje:\na) algorytmy na liczbach całkowitych\n18) oblicza liczbę operacji wykonywanych\nprzez algorytm;\n19) szacuje wielkość pamięci potrzebnej do\nkomputerowej realizacji algorytmu;\n20) bada efektywność komputerowych\nrozwiązań problemów;\nSchemat punktowania\n2 p. - za poprawną odpowiedź, w tym:.\n1 p. - za prawidłowe zdefiniowanie warunków,\n1 p. - za prawidłowe wywołania rekurencyjne.\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPrzykładowe rozwiązanie\nkw(long int n)\n{\nreturn n*n;\n}\nlong int f(long int n)\n{\nint i,k;\nif(n==1||n==2) return 1;\nelse if (n%2==0)\n{\ni=n/2+1;\nk=n/2-1;\nreturn kw(f(i))-kw(f(k));\n}\nelse {\ni=(n+1)/2;\nk=(n+1)/2-1;\nreturn kw(f(i))+kw(f(k));\n}\n}\nint main()\n{\nint n;\ncin>>n;\ncout << f(n)<< endl; return 0;\n}\nUwaga:\nDopuszczamy zastosowanie przez zdającego funkcji potęgowania wbudowanej w język\nprogramowania","solution":null,"image":"img/informatyka-2018-czerwiec-matura-rozszerzona/zad-2.3.webp","solution_image":null,"topics":null,"page_from":6,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":null,"text_source":"ocr","source_label":"Informatyka · Matura · czerwiec 2018 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.3. (0-2)
Aby przyśpieszyć rekurencyjne obliczanie wartości n-tego wyrazu ciągu Fibonacciego, można
skorzystać z następujących wzorów, prawdziwych dla dowolnego całkowitego k ≥ 2:
F2k=(Fk+1)2 -(Fk-1)2
F2k-1=(Fk)2 +(Fk-1)2
Zapisz w wybranej przez siebie notacji (w postaci listy kroków, w języku programowania lub
w pseudokodzie) algorytm rekurencyjny, który służy do obliczania wartości liczby Fn dla
dowolnego n ≥ 1 i korzysta z tych wzorów.
Algorytm.
MIN_1R

","answer_text_html":"

Zadanie 2.3. (0-2)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji […]
z zastosowaniem podejścia
algorytmicznego.

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

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

\n
  1. analizuje, modeluje i rozwiązuje sytuacje
\n

problemowe z różnych dziedzin;

\n
  1. stosuje podejście algorytmiczne do
\n

rozwiązywania problemu;

\n
  1. dobiera efektywny algorytm do
\n

rozwiązania sytuacji problemowej
i zapisuje go w wybranej notacji;

\n
  1. posługuje się podstawowymi
\n

technikami algorytmicznymi;

\n
  1. opisuje podstawowe algorytmy
\n

i stosuje:
a) algorytmy na liczbach całkowitych

\n
  1. oblicza liczbę operacji wykonywanych
\n

przez algorytm;

\n
  1. szacuje wielkość pamięci potrzebnej do
\n

komputerowej realizacji algorytmu;

\n
  1. bada efektywność komputerowych
\n

rozwiązań problemów;
Schemat punktowania
2 p. - za poprawną odpowiedź, w tym:.
1 p. - za prawidłowe zdefiniowanie warunków,
1 p. - za prawidłowe wywołania rekurencyjne.
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Przykładowe rozwiązanie
kw(long int n)
{
return n*n;
}
long int f(long int n)
{
int i,k;
if(n==1||n==2) return 1;
else if (n%2==0)
{
i=n/2+1;
k=n/2-1;
return kw(f(i))-kw(f(k));
}
else {
i=(n+1)/2;
k=(n+1)/2-1;
return kw(f(i))+kw(f(k));
}
}
int main()
{
int n;
cin>>n;
cout << f(n)<< endl; return 0;
}
Uwaga:
Dopuszczamy zastosowanie przez zdającego funkcji potęgowania wbudowanej w język
programowania

","solutions":[]}