Realizacja algorytmów rekurencyjnych - scenariusz zajęć z informatyki

Scenariusz
z zajęć informatyki
Temat: Realizacja algorytmów rekurencyjnych.
Klasa: III Liceum lub Technikum
Prowadzenie: Bartosz Chyś
Cele szczegółowe:
Uczeń:
- wymienia, czym zajmował się Leonardo Fibonacci;
- rozwiązuje zadania związane z algorytmem Fibonacciego;
- postępuje zgodnie z warunkami, aby wyznaczyć rozwiązanie przy pomocy algorytmu Fibonacciego;
- zna zapis rekurencyjny i iteracyjny algorytmu Fibonacciego w programie C++;
- wskazuje, do czego służą poszczególne elementy kodu algorytmu Fibonacciego w wersji iteracyjnej i rekurencyjnej;
- zna i potrafi zapisać wzór na algorytm Fibonacciego;
- współpracuje w grupie rozwiązania danego zadania;
- zachowuje się zgodnie z regulaminem pracowni informatycznej
Metody:
- podające: opis, wykład informacyjny
- eksponujące: pokaz
- praktyczne: ćwiczenia
Formy: indywidualna, zbiorowa
Środki:
- zadania( załącznik 1)
- tablica multimedialna
Czas realizacji: 45 minut


Przebieg lekcji:
Faza wstępna
1. Czynności organizacyjno-porządkowe
Nauczyciel-praktykant sprawdza obecność. Zapoznaje uczniów z tematem i celami zajęć.
Faza właściwa
1. Definicja ciągu Fibonacciego
Nauczyciel zwraca się do uczniów: Na wstępie dzisiejszych zajęć przedstawię Wam postać włoskiego matematyka Leonardo Fibonacciego. Otóż zajął się on problemem rozmnażania się królików. Chodziło mu o stworzenie pewnego modelu matematycznego. W modelu tym rozmnażanie rozpoczyna się od jednej pary zwierząt(nauczyciel omawia to na podstawie rysowanego przez siebie schematu- załącznik nr 1). W ich rozmnażaniu ważne są zasady:
- każda nowa para królików może mieć potomstwo po dokładnie jednym miesiącu życia;
- każda para królików, mogących być rodzicami, co miesiąc wydaje na świat potomstwo- kolejną parę królików;
- króliki nie starzeją się i nie chorują, co oznacza, że też nie umierają
Po omówieniu na schemacie pokazuje on uczniom definicję rekurencyjną ciągu Fibonacciego:

a1= a2=1
an=an-1+an-2 dla n>2

2. Zapis ciągu Fibonacciego w wersji iteracyjnej i w postaci rekurencji- porównanie
Nauczyciel odwołuje się do poprzednich zajęć. Prosi uczniów o przypomnienie czym jest algorytm iterencji i rekurencji oraz, jakie są pomiędzy nimi różnice. Następnie prezentuje uczniom na tablicy multimedialnej kod zapisu algorytmu Fibonacciego w wersji rekurencyjnej i iteracyjnej w programie C++(załącznik nr 1 do scenariusza).
3. Ciąg Fibonacciego- zadanie praktyczne
Nauczyciel rozdaje uczniom zadania dotyczące ciągu Fibonacciego, pochodzące z arkusza maturalnego z 2012 roku( załącznik nr 3 do scenariusza).

Faza końcowa
1. Podsumowanie zajęć
Nauczyciel systematyzuje wiedzę uczniów.
Uwagi:
Bibliografia
1) Informatyka europejczyka. Podręcznik dla szkół ponadgimnazjalnych-
zakres rozszerzony, wyd. PWN.

Załącznik nr 1
do scenariusza
Ciąg Fibonacciego

Numer miesiąca n Liczba par
królików
po n
miesiącach
1 MŁODE

2 RODZICE

3 RODZICE MŁODE

4 RODZICE MŁODE RODZICE

5 RODZICE MŁODE RODZICE RODZICE MŁODE

6 RODZICE MŁODE RODZICE RODZICE MŁODE RODZICE MŁODE RODZICE
Załącznik nr 2
do scenariusza

Ciąg Fibonacciego- wersja iteracyjna i rekurencyjna
A. Wersja iteracyjna
#include<cstdio>
int main(){

printf("ktory element ciagu obliczyc?
");
int n;
scanf("%d",&n);

if(n<=2) printf("%d elementem ciagu Fibonacciego jest 1
",n);
else{
int f1=1; //wartość pierwszego elementu
int f2=1; //wartość drugiego elementu
int temp; //zmienna pomocnicza
for(int i=3;i<=n;i++){
temp=f1+f2;
f1=f2;
f2=temp;
/*dwa przykładowe obiegi pętli:
temp=1+1=2;
f1=f2=1;
f2=temp=2;

temp=1+2=3;
f1=f2=2;
f2=temp=3 ;
*/
}
printf("%d elementem ciagu Fibonacciego jest %d
",n,f2);
}
return 0;
}

B. Wersja rekurencyjna
unsigned int fib(unsigned int n) {
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n-1)+fib(n-2);
}

Załącznik nr 3
do scenariusza

Zadanie z arkusza maturalnego 2012- poziom podstawowy- Fibonacci