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

Film prezentuje implementację algorytmu rekurencyjnego oraz iteracyjnego obliczania n-tego wyrazu ciągu Fibonacciego.

dwa króliki @ Litvalifa/Shutterstock.com

Ć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; long int silnia(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji silnia(1) jest 1.
return silnia(1)==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(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; long int silnia2(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji silnia2(1) jest 1.
return silnia2(1)==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 argumentami są liczba a oraz liczba n, a wynikiem – 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; long int potega(int a, int n) { //zdefiniuj funkcję i sprawdź jej działanie
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; long int ciag(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji ciag(1) jest 1.
return ciag(1)==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; int suma_cyfr(int n) {
Wynikiem funkcji suma_cyfr(2) jest 2.
return suma_cyfr(2)==2;
2
suma_cyfr(2)
Wynikiem funkcji suma_cyfr(22) jest 4.
return suma_cyfr(22)==4;
4
suma_cyfr(22)
Wynikiem funkcji suma_cyfr(222222) jest 12.
return suma_cyfr(222222)==12;
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 – obliczona 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; long int fib(int n) { //zdefiniuj funkcję i sprawdź jej działanie
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 – obliczona 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; long int fib2(int n) { //zdefiniuj funkcję i sprawdź jej działanie
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

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.6666666666666667.

#include <iostream> using namespace std; long int fib(int n) { //uzupełnij kod
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; long int lucas(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji lucas(1) jest 2.
return lucas(1)==2;
2
lucas(1)
Wynikiem funkcji lucas(10) jest 76.
return lucas(10)==76;
76
lucas(10)
Wynikiem funkcji lucas(16) jest 1364.
return lucas(16)==1364;
1364
lucas(16)
Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 2

Dwie początkowe liczby ciągu Fibonacciego są równe 1. Każda kolejna liczba tego ciągu jest sumą dwóch poprzednich. Przyjmijmy taki model rozmnażania się królików:

  • w pierwszych dwóch miesiącach do stada dochodzi 1 królik;
  • każdy kolejny miesiąc kończy się liczbą królików będących sumą dwóch poprzednich wartości, np. w miesiącu trzecim liczba 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 królików zmniejsza się o wartość tego numeru.

Tabela poniżej przedstawia liczby 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 trzynastego miesiąca.

#include <iostream> using namespace std; long int stado(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji stado(1) jest 1.
return stado(1)==1;
1
stado(1)
Wynikiem funkcji stado(2) jest 1.
return stado(2)==1;
1
stado(2)
Wynikiem funkcji stado(12) jest 88.
return stado(12)==88;
88
stado(12)
Rozwiąż ćwiczenie
Ta strona wykorzystuje pliki cookies w celu zapewnienia wygody przy korzystaniu z pełnej funkcjonalności. Więcej informacji