Aplet
Rozważ następującą funkcję rekurencyjną, wyznaczającą n‑ty wyraz ciągu Fibonacciego, a następnie zapoznaj się z apletem prezentującym jej kolejne wywołania.
![](https://static.zpe.gov.pl/portal/f/res-minimized/RulZIWQ1WZZnA/1690812947/xtAhdbPieM4TJ2BGiEVZgLZR8LnQWUbW.png)
Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/DQkOVc10H
Symulacja przedstawia liczenie wybranego elementu z ciągu Fibonacciego.
Na górze ustawiono pole, w którym wpisuje się numer wybranego elementu do wyliczenia.
Pod nim dwa przyciski, wstecz oraz dalej.
Po środku ekranu znajduje się napis fib ( wybrana liczba ).
Od tego napisu poprowadzone zostaną rozgałęzienia, z czego każde zakończone będzie podobnym napisem, pierwsze rozgałęzienie będzie miało napis fib ( wybrana liczba - 1), zaś napis w drugiej gałęzi: napis fib (wybrana liczba - 2).
To zachowanie będzie się powtarzało przy każdym kliknięciu przycisku dalej, aż do momentu, w którym wybrana liczba – po stosownym odejmowaniu – osiągnie wartość 1 lub 0.
W przypadku osiągnięcia wartości 1 lub 0, wynik funkcji zostaje zwrócony jako 1 lub 0 odpowiednio, wtedy każdy wynik zostaje kolejno dodany i tym samym gałęzie zostają usunięte.
Po usunięciu gałęzi na jednym poziomie, schodzenie inną sąsiadującą gałęzią się powtarza.
Algorytm następnie polega na zsumowaniu wszystkich kolejnych wyników rozgałęzień i uzyskaniu wyniku dla początkowej wybranej liczby.
Zadanie 2
Bartek zapisał na kartce 1000 par liczb, każda para w osobnej linii. Pierwsza liczba oznacza klucz danej linii, druga natomiast jej wartość.
W pliku liczby.txt
znajduje się 1000 par liczb, każda w osobnej linii. Każdy klucz to liczba naturalna z przedziału <1, 2000>.
Napisz program, który dla pliku liczby.txt
wyznaczy linie, których klucze są wyrazami ciągu Fibonacciego, a następnie wypisze tylko parzyste wartości tych linii. Wyniki zapisz w pliku wynik.txt
. Pamiętaj, że linie numerujemy od 1.
Dla przykładowych danych:
Plik wynikowy powinien wyglądać następująco:
Do oceny oddajesz:
plik
wynik.txt
, zawierający odpowiedź do zadania (wartości – drugie liczby – linii z plikuliczby.txt
, które są parzyste oraz których klucze – pierwsze liczby z linii – są liczbami ciągu Fibonacciego),plik(i) z komputerową realizacją zadania (kodem programu)·
Odpowiedź do zadania
Twoim zadaniem jest opracowanie rozwiązania zadania w wybranym przez siebie języku programowania: C++, Java lub Python. Odpowiedź do zadania dla danych z pliku znajdziesz na dole strony.
Rozwiązanie
Rozwiązanie zadania przedstawimy w postaci pseudokodu, ponieważ na egzaminie maturalnym można korzystać z wybranego języka programowania: C++, Java lub Python.
Na początku wczytujemy dane z pliku do tablicy. Następnie chcemy obliczyć elementy ciągu Fibonacciego, które wynoszą maksymalnie 2000. Dzięki temu nie będziemy musieli wykonywać tego za każdym razem, gdy będziemy sprawdzać klucz. Zapisujemy je w tablicy. Gdy jest ona gotowa, tworzymy dwie pętle, które sprawdzają, czy klucz linii (pierwsza liczba) jest elementem ciągu Fibonacciego, oraz czy wartość linii (druga liczba) jest liczbą parzystą. Jeżeli tak jest, wpisujemy wartość linii do pliku wynikowego i przerywamy pętlę wewnętrzną.
Funkcja dodaj(x)
oznacza dodanie elementu x
na koniec zbioru danych (tablicy), na którym jest wywoływana, natomiast mod
oznacza operację modulo.
Odpowiedź do zadania
Odpowiedź do zadania znajduje się w pliku: