5A. Rekurencja i ciąg Fibonacciego

Ćwiczenie 0

Przeanalizuj tabelę oraz kod, a następnie uzupełnij funkcję bank(float kwota) pozwalającą obliczyć procent składany, w którym odsetki doliczane są do kwoty lokaty.

#include <iostream>
using namespace std;

float bank(float kwota) {
	float procent = 0.1;
    	//po pierwszym roku oszczędzania
   	 kwota += kwota * procent;
		//po drugim roku oszczędzania
    	//uzupełnij
    	//po trzecim roku oszczędzania
    	//uzupełnij
   	 return kwota;
}

int main() {
	cout << bank(1000) << endl;
	return 0;
}

Wynikiem funkcji bank(1000) jest 1331.

return (int)bank(1000)==1331;

1331

(int)bank(1000)

Rozwiąż ćwiczenie

Ćwiczenie 1Silnia rekurencyjnie

Zdefiniuj funkcję rekurencyjną silnia(int n), której argumentem jest liczba nieujemna n, a wynikiem – obliczona silnia podanej liczby n. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji silnia(3) jest 6.
Wynikiem funkcji silnia(9) jest 362880.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int silnia(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji silnia(1) jest 1.

return silnia(1)==1;

silnia(1)

Wynikiem funkcji silnia(7) jest 5040.

return silnia(7)==5040;

5040

silnia(7)

Wynikiem funkcji silnia(12) jest 479 001 600.

return silnia(12)==479001600;

479001600

silnia(12)

Rozwiąż ćwiczenie

Ćwiczenie 2Silnia iteracyjnie

Zdefiniuj funkcję iteracyjną silnia2(int n), której argumentem jest liczba nieujemna n, a wynikiem – obliczona silnia podanej liczby n. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji silnia2(3) jest 6.
Wynikiem funkcji silnia2(9) jest 362880.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int silnia2(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji silnia2(1) jest 1.

return silnia2(1)==1;

silnia2(1)

Wynikiem funkcji silnia2(7) jest 5040.

return silnia2(7)==5040;

5040

silnia2(7)

Wynikiem funkcji silnia2(12) jest 479 001 600.

return silnia2(12)==479001600;

479001600

silnia2(12)

Rozwiąż ćwiczenie

Ćwiczenie 3Potęga rekurencyjnie

Zdefiniuj funkcję rekurencyjną potega(int a, int n), której parametrami są liczba a oraz liczba n, a wynikiem jest obliczona n-ta potęga podanej liczby a. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji potega(2, 3) jest 8.
Wynikiem funkcji potega(9, 5) jest 59049.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int potega(int a, int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji potega(10, 7) jest 10000000.

return potega(10, 7)==10000000;

10000000

potega(10, 7)

Wynikiem funkcji potega(12, 3) jest 1728.

return potega(12, 3)==1728;

1728

potega(12, 3)

Wynikiem funkcji potega(2, 13) jest 8192.

return potega(2, 13)==8192;

8192

potega(2, 13)

Rozwiąż ćwiczenie

Ćwiczenie 4Rekurencyjny ciąg liczb

Pewien ciąg liczb został zdefiniowany rekurencyjnie, tak jak poniżej:

Zdefiniuj funkcję rekurencyjną ciag(int n) obliczania n-tego wyrazu tego ciągu. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji ciag(5) jest -56.
Wynikiem funkcji ciag(8) jest 19012.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int ciag(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji ciag(1) jest 1.

return ciag(1)==1;

ciag(1)

Wynikiem funkcji ciag(7) jest -2376.

return ciag(7)==-2376;

-2376

ciag(7)

Wynikiem funkcji ciag(10) jest 1711044.

return ciag(10)==1711044;

1711044

ciag(10)

Rozwiąż ćwiczenie

Ćwiczenie 5Suma cyfr

Zdefiniuj funkcję rekurencyjną suma_cyfr(int n), która wyznaczy sumę cyfr liczby podanej jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji suma_cyfr(136) jest 10.
Wynikiem funkcji suma_cyfr(19918) jest 28.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
int suma_cyfr(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji suma_cyfr(2) jest 2.

return suma_cyfr(2)==2;

suma_cyfr(2)

Wynikiem funkcji suma_cyfr(22) jest 4.

return suma_cyfr(22)==4;

suma_cyfr(22)

Wynikiem funkcji suma_cyfr(222222) jest 12.

return suma_cyfr(222222)==12;

suma_cyfr(222222)

Rozwiąż ćwiczenie

Ćwiczenie 7Ciąg Fibonacciego rekurencyjnie

Zdefiniuj funkcję rekurencyjną fib(int n), której argumentem jest liczba n, a wynikiem – n-ta liczba ciągu Fibonacciego. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji fib(4) jest 3.
Wynikiem funkcji fib(11) jest 89.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int fib(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji fib(32) jest 2178309.

return fib(32)==2178309;

2178309

fib(32)

Wynikiem funkcji fib(37) jest 24157817.

return fib(37)==24157817;

24157817

fib(37)

Wynikiem funkcji fib(40) jest 102334155.

return fib(40)==102334155;

102334155

fib(40)

Rozwiąż ćwiczenie

Ćwiczenie 8Ciąg Fibonacciego iteracyjnie

Zdefiniuj funkcję iteracyjną fib2(int n), której argumentem jest liczba n, a wynikiem – n-ta liczba ciągu Fibonacciego. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji fib2(4) jest 3.
Wynikiem funkcji fib2(11) jest 89.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int fib2(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji fib2(32) jest 2178309.

return fib2(32)==2178309;

2178309

fib2(32)

Wynikiem funkcji fib2(37) jest 24157817.

return fib2(37)==24157817;

24157817

fib2(37)

Wynikiem funkcji fib2(40) jest 102334155.

return fib2(40)==102334155;

102334155

fib2(40)

Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 1

Kolejne liczby ciągu Lucasa oblicza się w taki sam sposób jak liczby Fibonacciego, z tym że początkowe liczby są równe 2 i 1. Każda kolejna liczba Lucasa jest sumą dwóch poprzednich, a zatem początkowe wartości ciągu Lucasa to: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, …

Zdefiniuj rekurencyjną funkcję lucas(int n), której wynikiem będzie n-ta liczba Lucasa i przetestuj dla wartości trzeciej i jedenastej z kolei.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int lucas(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji lucas(1) jest 2.

return lucas(1)==2;

lucas(1)

Wynikiem funkcji lucas(10) jest 76.

return lucas(10)==76;

lucas(10)

Wynikiem funkcji lucas(16) jest 1364.

return lucas(16)==1364;

1364

lucas(16)

Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 2

Fibonacci przedstawił zależność znaną obecnie jako ciąg Fibonacciego na przykładzie analizy liczby par królików w stadzie, w którym każda dojrzała para co miesiąc wydaje na świat parę młodych. Króliki osiągają dojrzałość dopiero po miesiącu. Na początku w stadzie żyje jedna para królików. Na koniec każdego miesiąca w stadzie żyje więc tyle par królików, ile w sumie żyło pod koniec dwóch poprzednich miesięcy, np. w miesiącu trzecim liczba par królików wynosi 2, czwartym – 3, w piątym – 5 itd.

Ponieważ króliki umierają, w każdym miesiącu, którego numer jest podzielny przez 7, liczba par królików zmniejsza się o wartość tego numeru. Przyjmij, że umierają króliki najstarsze.

Poniższa tabela przedstawia liczbę par królików w kolejnych miesiącach.

Zdefiniuj funkcję stado(int n) obliczania liczby królików w poszczególnych miesiącach i przetestuj dla trzeciego, siódmego i czternastego miesiąca.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int stado(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Wynikiem funkcji stado(1) jest 1.

return stado(1)==1;

stado(1)

Wynikiem funkcji stado(2) jest 1.

return stado(2)==1;

stado(2)

Wynikiem funkcji stado(12) jest 88.

return stado(12)==88;

stado(12)

Rozwiąż ćwiczenie

Zadanie 2Złota proporcja

Wypisz kolejne ilorazy wartości F(n) i F(n – 1) ciągu Fibonacciego dla przedziału od 2 do 20. Jaką widać prawidłowość?

Wskazówka: pierwsze cztery ilorazy to: 1.0, 2.0, 1.5, 1.66667.

#include <iostream>
using namespace std;

// zdefiniuj funkcję
long int fib(int n) {
}
int main() {
    // sprawdź działanie funkcji
    return 0;
}

Rozwiąż ćwiczenie

Informatyka 3

Treści usunięte z lekcji zgodnie z podstawą programową
z 2024 r. sprawdź w e-booku podręcznika na eduranga.pl.

InfografikaŚwiat rekurencji

FilmProgramowanie w C++. Rekurencja i ciąg Fibonacciego

Ćwiczenie 0

Ćwiczenie 1Silnia rekurencyjnie

Ćwiczenie 2Silnia iteracyjnie

Ćwiczenie 3Potęga rekurencyjnie

Ćwiczenie 4Rekurencyjny ciąg liczb

Ćwiczenie 5Suma cyfr

Ćwiczenie 7Ciąg Fibonacciego rekurencyjnie

Ćwiczenie 8Ciąg Fibonacciego iteracyjnie

Ćwiczenie dodatkowe 1

Ćwiczenie dodatkowe 2

Zadanie 2Złota proporcja

Pytania quizoweRekurencja i ciąg Fibonacciego