2 XI 2016 - 6 lekcja, godz. 9.15, przypominamy rekurencję, piszemy własne programy

Uwaga, następne spotkanie ewentualnie 30 listopada.
Proszę do tego czasu przeczytać i przećwiczyć o:
Tablice,
Obiekty,
Programowanie obiektowe,
Stawanie się coraz lepszym programistą.
 
Dziś na rozgrzewkę:

1. Napiszmy program wypisujący wszystkie liczby trzycyfrowe podzielne przez liczbę n podaną przez użytkownika - przyjmijmy, że n jest liczbą z zakresu od 1 do 100. Tu główną trudnością jest rozmieszczenie wszystkich wyników np. dla n=1 lub n=2.
Oglądamy prezentację o algorytmach.


Porozmawiajmy o rekurencji. Rekurencja zwana rekursją, polega na wywołaniu przez funkcję samej siebie. Algorytmy rekurencyjne zastępują w pewnym sensie iteracje. Niekiedy problemy rozwiązywane tą techniką będą miały nieznacznie wolniejszy czas od iteracyjnego odpowiednika (wiąże się to z wywoływaniem funkcji), natomiast rozwiązanie niektórych problemów jest znacznie wygodniejsze.
Zawsze przy rekurencji wyodrębniamy warunek zakończenia się rekurencji oraz powtarzalność wywoływanej funkcji

2. Napiszmy program obliczający:
- silnię (silnia n jest to iloczyn wszystkich liczb naturalnych nie większych od n, np silnia pięciu - 5!=1*2*3*4*5=120). Warunek zakończenia to 1!=1 lub 0!=1.
Widać, że 5!=5*4!, zaś 4!=4*3! itd.

Przypomnijmy sobie ciąg Fibonacciego. Oglądamy przynajmniej 5 min z filmu.

 3. Napiszmy program liczący n tą liczbę Fibonacciego rekurencyjnie (gdy poznamy tabele obliczymy iteracyjnie). Warunkiem zakończenia jest liczba F1=1 i F2=1, zaś kolejne liczby są sumą dwóch poprzednich, np. Fn=F(n-1)+F(n-2). 1 1 2 3 5 8 13 21 34 55 89 .....