Algorytmy i struktury danych

Ćwiczenie 4

Algorytmy rekurencyjne

1. F

UNKCJE 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

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;

}

float suma (float a, float b);

Algorytmy i struktury danych

Ćwiczenie 4

Algorytmy rekurencyjne

2. F

UNKCJE REKURENCYJNE

Funkcję nazywamy rekurencyjną, jeśli wywołuje ona sama siebie.

Z

ADANIE

Zaproponuj rekurencyjny algorytm obliczania silni dla dowolnej liczby całkowitej
dodatniej n.

Wskazówka:

n

n

n

n

n

1

dla

)!

1

(

0

dla

1

!

R

OZWIĄZANIE

//Program glowny:
int main(int argc, char *argv[])
{
int n;
cout<<"Podaj liczbe naturalna: ";
cin>>n;

co

ut<<"Silnia wynosi: "<<silnia(n)<<"\n";

return EXIT_SUCCESS;

}

#

include <iostream>

using namespace std;

//Funkcja rekurencyjna:
long silnia(int n)
{

long s;

if(n==0)

{

s=1;

}

else

{

s=n*silnia(n-1);

}

return s;

}

START

n==0

s=1

s= n *silnia(n-1)

zwracaj(s)

STOP

T

N

long s

long silnia( int n)

Rys. Schemat blokowy dla funkcji rekurencyjnej

silnia.

Algorytmy i struktury danych

Ćwiczenie 4

Algorytmy rekurencyjne

Z

ADANIA

Zadanie 1.
Dany jest ciąg o wyrazie ogólnym

)

(n

L

zdefiniowany rekurencyjnie:

.

0

dla

)

1

(

,

0

dla

1

)

(

n

n

n

L

n

n

L

Zaproponuj rekurencyjny algorytm obliczania n-tego wyrazu ciągu L(n).

Zadanie 2.
Zaproponuj rekurencyjny algorytm obliczania elementów ciągu Fibonacciego:

1

dla

)

2

(

)

1

(

1

dla

1

0

dla

0

)

(

n

n

fib

n

fib

n

n

n

fib

Narysuj drzewo wywołań funkcji rekurencyjnej

)

(n

fib

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

0

, n

m

).

Wskazówka: Korzystamy z definicji mnożenia:

n

n

m

m

n

m

n

m

1

dla

)]

1

(

[

1

dla

Zadanie 4.
Dany jest ciąg

)

(n

Q

zdefiniowany rekurencyjnie:

0

dla

)

1

(

0

dla

1

)

(

n

n

Q

n

n

n

Q

Napisz rekurencyjny algorytm obliczania n-tego wyrazu ciągu

)

(n

Q

. Narysuj drzewo

wywołań funkcji rekurencyjnej

)

(n

Q

dla

4

n

.

Zadanie 5.
Zaproponuj rekurencyjne rozwiązanie algorytmu Euklidesa obliczającego największy
wspólny dzielnik dwóch liczb naturalnych.