Algorytmy i struktury danych
Ćwiczenie 4
Algorytmy rekurencyjne
1. FUNKCJE W J
ZYKU C++
W języku C++ istnieje możliwość posługiwania się podprogramami, które możemy
traktować jako małe programy w programie głównym. W języku C++ wszystkie
podprogramy nazywane są funkcjami. Funkcję wywołuje się poprzez podanie jej nazwy
oraz argumentów, które umieszczamy w nawiasach. Każda funkcja ma swoją nazwę,
która ją identyfikuje. Tak samo jak nazwy zmiennych, wszelkie nazwy  przed pierwszym
odwołaniem się do nich  muszą zostać zadeklarowane.
A) Deklaracja funkcji
float suma (float a, float b);
B) Wywołanie funkcji w programowe głównym
int main(int argc, char *argv[])
{
float Wynik;
Wynik = suma(1.0, 13.23);
cout <<  suma wynosi: << Wynik << endl;
return EXIT_SUCCESS;
}
C) Definicja funkcji
float suma(float a, float b)
{
float s;
s = a+b;
return s;
}
Algorytmy i struktury danych
Ćwiczenie 4
Algorytmy rekurencyjne
2. FUNKCJE REKURENCYJNE
Funkcję nazywamy rekurencyjną, jeśli wywołuje ona sama siebie.
ZADANIE
Zaproponuj rekurencyjny algorytm obliczania silni dla dowolnej liczby całkowitej
dodatniej n.
Wskazówka:
1 dla n 0
n!
n(n 1)! dla n 1
ROZWI
ZANIE
START
#include
long silnia( int n)
using namespace std;
long s
//Funkcja rekurencyjna:
T N
long silnia(int n)
n==0
{
s=1 s= n *silnia(n-1)
long s;
if(n==0)
zwracaj(s)
{
s=1;
STOP
}
else
{
s=n*silnia(n-1);
}
return s;
}
Rys. Schemat blokowy dla funkcji rekurencyjnej
silnia.
//Program glowny:
int main(int argc, char *argv[])
{
int n;
cout<<"Podaj liczbe naturalna: ";
cin>>n;
cout<<"Silnia wynosi: "< return EXIT_SUCCESS;
}
Algorytmy i struktury danych
Ćwiczenie 4
Algorytmy rekurencyjne
ZADANIA
Zadanie 1.
Dany jest ciąg o wyrazie ogólnym L(n) zdefiniowany rekurencyjnie:
1 dla n 0,
L(n)
L(n 1) n dla n 0.
Zaproponuj rekurencyjny algorytm obliczania n-tego wyrazu ciągu L(n).
Zadanie 2.
Zaproponuj rekurencyjny algorytm obliczania elementów ciągu Fibonacciego:
0 dla n 0
fib(n) 1 dla n 1
fib(n 1) fib(n 2) dla n 1
Narysuj drzewo wywołań funkcji rekurencyjnej fib(n) dla n=5.
Co można powiedzieć o efektywności rekurencyjnego rozwiązania powyższego problemu?
Zadanie 3.
Napisz rekurencyjny algorytm mnożenia dwóch liczb naturalnych m i n (gdzie m,n 0 ).
Wskazówka: Korzystamy z definicji mnożenia:
m dla n 1
m n
m [m (n 1)] dla n 1
Zadanie 4.
Dany jest ciąg Q(n) zdefiniowany rekurencyjnie:
1 dla n 0
Q(n)
n
dla n 0
Q(n 1)
Napisz rekurencyjny algorytm obliczania n-tego wyrazu ciągu Q(n) . Narysuj drzewo
wywołań funkcji rekurencyjnej Q(n) dla n 4 .
Zadanie 5.
Zaproponuj rekurencyjne rozwiązanie algorytmu Euklidesa obliczającego największy
wspólny dzielnik dwóch liczb naturalnych.