Paradygmaty 

Paradygmaty 

programowania

programowania

Lab. 2

Lab. 2

Napisa

Napisa

ć

ć

program wyznaczaj

program wyznaczaj

ą

ą

cy warto

cy warto

ść

ść

Symbolu Newtona, gdzie

Symbolu Newtona, gdzie

Symbol Newtona (czytamy: 

Symbol Newtona (czytamy: 

n nad k

n nad k

, 

, 

n po k

n po k

lub

lub

k z n

k z n

) jest funkcj

) jest funkcj

ą

ą

dw

dw

ó

ó

ch 

ch 

argument

argument

ó

ó

w ca

w ca

ł

ł

kowitych nieujemnych, zdefiniowan

kowitych nieujemnych, zdefiniowan

ą

ą

jako:

jako:

)!

(

!

!

k

n

k

n

k

n

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

dla danego dodatniego n oraz 0 <= k <= n

dla danego dodatniego n oraz 0 <= k <= n

)!

(

!

!

k

n

k

n

k

n

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

A teraz napiszmy program wyznaczaj

A teraz napiszmy program wyznaczaj

ą

ą

cy warto

cy warto

ść

ść

Symbolu Newtona 

Symbolu Newtona 

wyra

wyra

ż

ż

onego wzorem rekurencyjnym postaci:

onego wzorem rekurencyjnym postaci:

⎪

⎩

⎪

⎨

⎧

=

=

<

<

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

−

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

n

k

k

gdy

n

k

gdy

k

n

k

n

k

n

lub

0

1

0

1

1

1

dla danego dodatniego   

dla danego dodatniego   

n   

n   

oraz

oraz

0 <= k <= n

0 <= k <= n

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

6

49

Czy obydwoma programami mo

Czy obydwoma programami mo

ż

ż

na policzy

na policzy

ć

ć

liczb

liczb

ę

ę

kombinacji w totka czyli

kombinacji w totka czyli

1

1

1

1

1

1

1

1

1

0

1

1

1

0

1

1

1

1

0

1

1

2

2

1

2

1

2

0

2

1

2

0

2

1

2

3

1

3

1

3

0

3

2

4

1

4

10

!

3

!*

2

!

5

)!

2

5

!*(

2

!

5

2

5

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

=

=

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

)!

(

!

!

k

n

k

n

k

n

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

⎪

⎩

⎪

⎨

⎧

=

=

<

<

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

−

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

n

k

k

gdy

n

k

gdy

k

n

k

n

k

n

lub

0

1

0

1

1

1

⎪

⎩

⎪

⎨

⎧

=

=

<

<

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

−

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

n

k

k

gdy

n

k

gdy

k

n

k

n

k

n

lub

0

1

0

1

1

1

#

#

include

include

<

<

iostream

iostream

>

>

using

using

namespace

namespace

std

std

;

;

long

long

n_po_k

n_po_k

(int

(int

n,

n,

int

int

k)

k)

{

{

if

if

( (k>0) && (

( (k>0) && (

k<n

k<n

) )

) )

return

return

n_po_k(n

n_po_k(n

-

-

1, k

1, k

-

-

1) + n_po_k(n

1) + n_po_k(n

-

-

1, k);

1, k);

else

else

return

return

1

1

; }

; }

int

int

main

main

()

()

{

{

int

int

n, k, y;

n, k, y;

A:

A:

cout

cout

<< "

<< "

\

\

nWczytaj

nWczytaj

n= ";

n= ";

cin

cin

>> n;

>> n;

if

if

(n<1) {

(n<1) {

cout

cout

<< "

<< "

\

\

nBledne

nBledne

n";

n";

goto

goto

A

A

;}

;}

B:

B:

cout

cout

<< "

<< "

\

\

nWczytaj

nWczytaj

k= ";

k= ";

cin

cin

>> k;

>> k;

if

if

((k<1) || (

((k<1) || (

k>n

k>n

)) {

)) {

cout

cout

<< "

<< "

\

\

nBledne

nBledne

k";

k";

goto

goto

B

B

;}

;}

y =

y =

n_po_k(n

n_po_k(n

, k);

, k);

cout

cout

<< "

<< "

\

\

n

n

\

\

n

n

Met. rekurencyjna {n po k} = " << y << "

Met. rekurencyjna {n po k} = " << y << "

\

\

n

n

\

\

n

n

";

";

return 0;

return 0;

}

int, long: -2 147 483 648; 2 147 483 647

}

⎪

⎩

⎪

⎨

⎧

=

=

<

<

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

−

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

n

k

k

gdy

n

k

gdy

k

n

k

n

k

n

lub

0

1

0

1

1

1

A teraz zmodyfikujmy program, wykorzystuj

A teraz zmodyfikujmy program, wykorzystuj

ą

ą

c poprzednio 

c poprzednio 

zdefiniowane funkcje: dane, silnia, prezentacja

zdefiniowane funkcje: dane, silnia, prezentacja

tak aby unikn

tak aby unikn

ąć

ąć

instrukcji postaci:

instrukcji postaci:

goto

goto

Etykieta

Etykieta

⎪

⎩

⎪

⎨

⎧

=

=

<

<

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −

+

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

−

−

=

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

n

k

k

gdy

n

k

gdy

k

n

k

n

k

n

lub

0

1

0

1

1

1

Napisa

Napisa

ć

ć

program wyznaczaj

program wyznaczaj

ą

ą

cy kolejne wyrazy 

cy kolejne wyrazy 

ci

ci

ą

ą

gu, kt

gu, kt

ó

ó

re tworzymy korzystaj

re tworzymy korzystaj

ą

ą

c z 

c z 

rekurencyjnego wzoru postaci jak ni

rekurencyjnego wzoru postaci jak ni

ż

ż

ej dla 

ej dla 

danych   a

danych   a

0

0

, a

, a

1

1

oraz n

oraz n

⎪

⎩

⎪

⎨

⎧

>

−

+

−

=

=

=

1

)

2

(

)

1

(

1

0

)

(

1

0

n

dla

n

F

n

F

n

dla

a

n

dla

a

n

F

⎪

⎩

⎪

⎨

⎧

>

−

+

−

=

=

=

1

)

2

(

)

1

(

1

0

)

(

1

0

n

dla

n

F

n

F

n

dla

a

n

dla

a

n

F

#

#

include <

include <

iostream.h

iostream.h

>

>

using

using

namespace

namespace

std

std

;

;

void

void

fibonacci

fibonacci

(

(

int

int

&,

&,

int

int

& );

& );

main(

main(

)

)

{

{

int

int

n,

n,

k, w1, w2;

k, w1, w2;

cout

cout

<< "Program na obliczanie kolejnego"

<< "Program na obliczanie kolejnego"

<< " wyrazu

<< " wyrazu

ciagu

ciagu

Fibonacci'ego

Fibonacci'ego

\

\

n

n

\

\

n

n

";

";

cout << "

cout << "

Pierwszy wyraz

Pierwszy wyraz

ciagu

ciagu

=

=

";

";

cin

cin

>> w1;

>> w1;

cout << "

cout << "

Drugi wyraz

Drugi wyraz

ciagu

ciagu

=

=

";

";

cin

cin

>> w2;

>> w2;

cout

cout

<<

<<

„

„

Liczba

Liczba

wyrazow

wyrazow

ciagu

ciagu

= ";

= ";

cin >> n;

cin >> n;

cout

cout

<< "

<< "

\

\

n";

n";

for ( k=3;

for ( k=3;

k<=n

k<=n

; k++ )

; k++ )

{ fibonacci(w1, w2);

{ fibonacci(w1, w2);

cout

cout

<< " " << k << "

<< " " << k << "

\

\

t" << "wyraz

t" << "wyraz

ciagu

ciagu

= "

= "

<< "

<< "

\

\

t" << w2 <<

t" << w2 <<

endl

endl

; };

; };

return 0;

return 0;

}

}

void

void

f

f

i

i

bonacci

bonacci

(

(

int

int

&a,

&a,

int

int

&b

&b

)

)

{

{

int

int

pom

pom

;

;

pom

pom

= a + b; a = b; b =

= a + b; a = b; b =

pom

pom

;

;

}

}

zad. 4.1

zad. 4.1

Mamy zadan

Mamy zadan

ą

ą

tablic

tablic

ę

ę

A o rozmiarach 3 x 4 zawieraj

A o rozmiarach 3 x 4 zawieraj

ą

ą

c

c

ą

ą

liczby typu 

liczby typu 

ca

ca

ł

ł

kowitego (wprowadzone (4a) lub wygenerowane przy u

kowitego (wprowadzone (4a) lub wygenerowane przy u

ż

ż

yciu generatora 

yciu generatora 

liczb losowych (4b)). 

liczb losowych (4b)). 

Program ma wyszuka

Program ma wyszuka

ć

ć

elementy 

elementy 

o

o

warto

warto

ś

ś

ci

ci

najmniejszej oraz najwi

najmniejszej oraz najwi

ę

ę

kszej, 

kszej, 

poda

poda

ć

ć

te warto

te warto

ś

ś

ci oraz ich wsp

ci oraz ich wsp

ó

ó

ł

ł

rz

rz

ę

ę

dne, a nast

dne, a nast

ę

ę

pnie zamieni

pnie zamieni

ć

ć

je miejscami. 

je miejscami. 

Je

Je

ż

ż

eli warto

eli warto

ść

ść

minimalna lub maksymalna powtarza si

minimalna lub maksymalna powtarza si

ę

ę

w tabeli kilka razy 

w tabeli kilka razy 

zapami

zapami

ę

ę

tujemy ich ostatnie wyst

tujemy ich ostatnie wyst

ą

ą

pienie w tabeli. Zaprezentowa

pienie w tabeli. Zaprezentowa

ć

ć

warto

warto

ś

ś

ci 

ci 

pocz

pocz

ą

ą

tkowe tablicy A, oraz warto

tkowe tablicy A, oraz warto

ś

ś

ci ko

ci ko

ń

ń

cowe tablicy. Program ma mie

cowe tablicy. Program ma mie

ć

ć

posta

posta

ć

ć

strukturaln

strukturaln

ą

ą

.

.

Deklaracja i inicjalizacja tablic:

Deklaracja i inicjalizacja tablic:

jednowymiarowe:

jednowymiarowe:

int

int

A[3] = {1, 5, 3};

A[3] = {1, 5, 3};

wielowymiarowe:

wielowymiarowe:

int

int

B[2, 3] = { {2, 5, 8}, {4, 1, 0}};

B[2, 3] = { {2, 5, 8}, {4, 1, 0}};

lub

lub

int

int

B[2, 3] = { 2, 5, 8, 4, 1, 0};

B[2, 3] = { 2, 5, 8, 4, 1, 0};

a inicjalizacja postaci:

a inicjalizacja postaci:

int

int

C[2, 3] = { 2, 5, 8, 4};

C[2, 3] = { 2, 5, 8, 4};

jest r

jest r

ó

ó

wnowa

wnowa

ż

ż

na

na

int

int

C[2, 3] = { 2, 5, 8, 4, 0, 0};

C[2, 3] = { 2, 5, 8, 4, 0, 0};

zerowanie tablicy:

zerowanie tablicy:

int

int

C[2, 3] = {0}, B[5]={0};

C[2, 3] = {0}, B[5]={0};

Inicjalizacja bez podania wymiaru:

Inicjalizacja bez podania wymiaru:

int

int

C[ ] = {4, 5, 7, 9]; jest traktowane jako

C[ ] = {4, 5, 7, 9]; jest traktowane jako

int

int

C[ 4] = {4, 5, 7, 9];

C[ 4] = {4, 5, 7, 9];

Inny uk

Inny uk

ł

ł

ad danych

ad danych

Generowanie liczb losowych ca

Generowanie liczb losowych ca

ł

ł

kowitych z zadanego przedzia

kowitych z zadanego przedzia

ł

ł

u:

u:

Aby wygenerowa

Aby wygenerowa

ć

ć

ca

ca

ł

ł

kowit

kowit

ą

ą

liczb

liczb

ę

ę

losow

losow

ą

ą

trzeba doda

trzeba doda

ć

ć

biblioteki:

biblioteki:

#

#

include

include

<

<

stdlib.h

stdlib.h

>

>

#

#

include

include

<

<

time.h

time.h

>

>

Przed rozpocz

Przed rozpocz

ę

ę

ciem procesu generowania liczb, 

ciem procesu generowania liczb, 

np

np

. na pocz

. na pocz

ą

ą

tku bloku 

tku bloku 

main

main

()  

()  

wywo

wywo

ł

ł

ujemy funkcj

ujemy funkcj

ę

ę

srand

srand

():

():

srand((unsigned)time(NULL

srand((unsigned)time(NULL

)); 

)); 

a generowanie ca

a generowanie ca

ł

ł

kowitych liczb losowych realizujemy wywo

kowitych liczb losowych realizujemy wywo

ł

ł

uj

uj

ą

ą

c funkcj

c funkcj

ę

ę

rand():

rand():

np

np

.  dla zakresu:  (   1;     10)    

.  dla zakresu:  (   1;     10)    

‐

‐

n=rand()%10 + 1

n=rand()%10 + 1

(   1;   200)    

(   1;   200)    

‐

‐

n=rand()%200 + 1

n=rand()%200 + 1

(101; 1000)    

(101; 1000)    

‐

‐

n=100 + rand()%900 + 1

n=100 + rand()%900 + 1

generalnie przy okre

generalnie przy okre

ś

ś

laniu zakresu losowanych liczb okre

laniu zakresu losowanych liczb okre

ś

ś

lamy:

lamy:

n = 

n = 

zakres_dolny+rand()%(zakres_gorny

zakres_dolny+rand()%(zakres_gorny

‐

‐

zakres_dolny

zakres_dolny

+1) + 1; 

+1) + 1; 

zakres liczb:  [1,  200]

zakres liczb:  [1,  200]

Ponowne uruchomienie

Ponowne uruchomienie

koniec lab.2

koniec lab.2