Algorytmy i struktury danych

laboratorium – część 1

1. Algorytmy z rozgałęzieniami, algorytmy cykliczne

Zad. 1.1.
Narysuj schemat blokowy algorytmu rozwiązywania równania kwadratowego o postaci

0

2







c

bx

ax

, gdzie a, b i c są stałymi podawanymi przez użytkownika, ale przyjmij, że stała a

będzie zawsze różna od zera. Zapisz algorytm jako program w języku C/C++.

Zad. 1.2.
Rozszerz algorytm utworzony w zad. 1 o przypadek kiedy stała a jest równa 0.

Zad. 1.3.
Napisz algorytm obliczania podatku dochodowego przy danej podstawie obliczenia podatku.

Podstawa obliczenia podatku

w złotych

Podatek wynosi

ponad

do

85528

18% podstawy obliczenia minus kwota 556 zł 2 gr

85528

14839 zł 2 gr + 32% nadwyżki ponad 85528 zł

Zad. 1.4.
Napisz algorytm wyznaczania wartości funkcji signum dla argumentu rzeczywistego podawanego
przez użytkownika. Funkcja signum określona jest wzorem:























0

1

0

0

0

1

sgn

)

(

x

dla

x

dla

x

dla

x

x

f

Zad. 1.5.
Określ jaką wartość będzie mieć zmienna m po wykonaniu następującego algorytmu:

2. Algorytmy iteracyjne, operacje na tablicach

Zad. 2.1.
Napisz algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych
m i n metodą Euklidesa.

Zad. 2.2.
Napisz iteracyjny algorytm obliczania wartości wyrażenia

n

2 dla podanej liczby naturalnej n.

Zad. 2.3.
Napisz algorytm wczytywania i wyświetlania elementów tablicy 10-elementowej.

Zad. 2.4.
Napisz algorytm wyszukiwania w dziesięcioelementowej tablicy liczb całkowitych liczby
największej oraz określania jej pozycji.

Zad. 2.5.
Napisz algorytm określania ilości liczb podzielnych przez 3, lecz niepodzielnych przez 2 w danej
tablicy liczb naturalnych.

3. Algorytmy rekurencyjne

Zad. 3.1.
Napisz rekurencyjny algorytm obliczania silni danej liczby naturalnej n.
Wskazówka:
Korzystamy z definicji silni:















n

n

n

n

n

1

dla

)!

1

(

0

dla

1

!

Zad. 3.2.
Zaproponuj rekurencyjny algorytm odwracania kolejności elementów w tablicy.

Zad. 3.3.
Napisz rekurencyjny algorytm mnożenia dwóch liczb naturalnych m i n (gdzie

0

,



n

m

). Narysuj

drzewo wywołań rekurencyjnych dla

5

,

5





n

m

.

Wskazówka:
Korzystamy z definicji mnożenia:





















n

n

m

m

n

m

n

m

1

dla

)]

1

(

[

1

dla

Zad. 3.4.
Podaj rekurencyjny opis następujących ciągów:

a) ciągu arytmetycznego o pierwszym wyrazie równym 1 i różnicy równej 2,
b) ciągu geometrycznego o pierwszym wyrazie równym 5 i ilorazie równym 2.

Napisz rekurencyjne algorytmy obliczania n-tych wyrazów tych ciągów. Narysuj drzewa wywołań
rekurencyjnych dla tych algorytmów przy

6



n

.

4. Złożoność obliczeniowa algorytmów

Zad. 4.1.
Uporządkuj w kierunku rosnącym następujące złożoności obliczeniowe algorytmów:

)

2

(

),

!

(

),

(log

),

(

n

O

n

O

n

O

n

O

.

Zad. 4.2.
Dana jest tablica n-elementowa. Oszacuj złożoność czasową algorytmu sortowania bąbelkowego tej
tablicy:

for(int i=1; i<n; i++)
{

for(int j=n-1; j>=i; j--)

{

if(tab[j-1]>tab[j])

{

t=tab[j-1]; tab[j-1]=tab[j]; tab[j]=t;

}

}

}

Zad. 4.3.
Dana jest tablica n-elementowa. Oszacuj złożoność czasową algorytmu sortowania przez selekcję
tej tablicy:

for(int i=0; i<n-1; i++)
{

min=i;
for(int j=i+1; j<n; j++)

{

if(tab[j]<tab[min]) min=j;

}

t=tab[min]; tab[min]=tab[i]; tab[i]=t;

}

Zad. 4.4.
Oszacuj złożoność czasową algorytmu mnożenia dwóch macierzy kwadratowych o rozmiarze

n

n



. Dla dwóch macierzy

n

n

ij

a

A





]

[

oraz

n

n

ij

b

B





]

[

elementy macierzy

B

A

C





wyznaczane są

ze wzoru:









n

k

kj

ik

ij

b

a

c

1

dla

n

i

,...,

2

,

1



,

n

j

,...,

2

,

1



.

Zad. 4.5.
Rozwiąż równania rekurencyjne:

a)

















1

1

1

)

1

(

)

(

n

dla

n

dla

n

n

T

n

T

b)





























1

1

1

1

2

)

(

n

dla

n

dla

n

T

n

T