trening2012.pdf

(875 KB) Pobierz

Trening przed egzaminem z WdI, 31 maja 2012

1. Wyjanijnacenieterminów

a) Algorytm,

b) Prosty typ danych, strukturalny typ danych,

c) Statyczny i dynamiczny typ danych,

d) Zmienna lokalna, zmienna globalna,

e) Iteracja,rodajeptli,

f)

Procedura rekurencyjna,

g) f = Θ(g) , f = O(g) , gdzie f, g ąniekońconymiciągamiowyraachdodatnich,

h) Uporądkujunkcjewedługrelacji„byćconajwyżejrdu”

3 n , n 2 log n, 6n 3 , log 2 n 3 , n!, 6n 3 -n 2

i)

Problem nierozstrzygalny (nieobliczalny),

j)

Kompilator, kompilacja,

k) Sytemoperacyjny,budowaytemu,prykładyytemówoperacyjnych,

l) Sytemieciowyiwielodotpowy,

m) Siećkomputerowa,rodajeieci,

n) Szyfrowanie, szyfrogram, klucz, system szyfrowania z kluczem publicznym,

2.

Dana jest procedura

Function zagadka(m,n:integer):integer; {m, n – liczby naturalne}

var x,y,z:integer;

begin

z:=0; x:=m; y:=n;

while x>0 do

begin

if odd(x) then z:=z+y;

x:=x div 2; y:= 2*y;

end;

zagadka:=z;

end;

a) Narysuj schemat blokowy algorytmu zapisanego wtrecitejprocedury

START

Dane: m, n

z:=0; x:=m; y:=n

nie

Wynik: z

STOP

x>0

tak

nie

tak

z:=z+y;

odd(x)

x:=x div 2;

y:=2*y;

b) Predtawwtabelceprebiegobliceń(kolejnewartoci miennych)wywołania zagadka(7,5)

Numer iteracji

X

y

z

7

5

0

1

3

10

5

2

1

20

15

3

0

40

35

4

c) Jakijetwynikwywołania zagadka(m,n) dla dowolnych naturalnych m i n ?

Ztabelkiwidimy,że zagadka(7,5)=35 . Zauważmy,że Procedura ta opiujenatpującypoóbmnożenia

7*5 = 5+5+5+5+5+5+5 = 5+(5+5)+(5+5)+(5+5) = 5+10+10+10 =

5+10+(10+10) = 5+10+20 = 35

Wytuacjiogólnejmamy

zagadka(m,n)=m*n

d) Za rozmiar danej (m,n) pryjmujemylicbnaturalną m Jakijetrądłożonocicaowej tego algorytmu?

byutalićrądłożonocicaowejtegoalgorytmuwytarcyoacowaćlicbwykonańptli while Pokażdym

prebieguptliwartoćmiennej x jetpołowąjejwartocipopredniegoprebiegu,aiteracjakońcyi,gdy x

przyjmujewartoć 0 Ponieważpocątkowąwartocią x jest m ,tolicbawykonańptlijetunkcjądokładnierdu

funkcji log 2 m Stądrądłożonocicaowejalgorytmurównai Ѳ (log m).

1058458771.111.png

1058458771.122.png

1058458771.133.png

1058458771.143.png

1058458771.001.png

1058458771.012.png

1058458771.023.png

1058458771.034.png

1058458771.045.png

1058458771.056.png

1058458771.067.png

1058458771.069.png

1058458771.070.png

1058458771.071.png

1058458771.072.png

1058458771.073.png

1058458771.074.png

1058458771.075.png

1058458771.076.png

1058458771.077.png

1058458771.078.png

1058458771.079.png

1058458771.080.png

1058458771.081.png

1058458771.082.png

1058458771.083.png

1058458771.084.png

1058458771.085.png

3. Dlatałejnaturalnej n , typ tab zadeklarowano jako:

type tab= array[0..n] of 0..9;

Dana jest procedura

Procedure zagadka(A,B:tab; var C:tab);

var i,j,k:Integer;

begin

k:=0;

for i:=n downto 1 do

begin

j:=A[i]+B[i]+k;

C[i]:= j mod 10;

k:= j div 10;

end;

C[0]:=k;

end;

a) Przedtawwponiżejtabelceprebiegobliceńwptli for (kolejnewartocimiennych)wywołania

zagadka(X, Y, Z) dlatałej n=4 oraz X=[0 5 6 5 6] i Y=[0 6 8 7 4]

Numer iteracji

i

Z[i]

j

k

0

1

2

3

4

b) Jaki jest wynikdiałaniatejprocedurydladowolnychwektorów X i Y takich,że X[0]=Y[0]=0 ?

4. Zapałek układamykolejneiguryjaknaryunku

1

2

3

4 . . .

Napisz proceduryoblicającedladanego n ,licbapałek tworących n -tąigur

a) Procedura iteracyjna

byoblicyćlicbapałektworącychn-tąigurmożnaprykładowopoumowaćapałkiwedługchematu

przedstawionego na rysunku:

1058458771.086.png

1058458771.087.png

1058458771.088.png

1058458771.089.png

1058458771.090.png

1058458771.091.png

1058458771.092.png

1058458771.093.png

1058458771.094.png

1058458771.095.png

1058458771.096.png

1058458771.097.png

1058458771.098.png

1058458771.099.png

1058458771.100.png

1058458771.101.png

1058458771.102.png

1058458771.103.png

1058458771.104.png

1058458771.105.png

1058458771.106.png

1058458771.107.png

1058458771.108.png

1058458771.109.png

1058458771.110.png

1058458771.112.png

1058458771.113.png

1058458771.114.png

1058458771.115.png

1058458771.116.png

1058458771.117.png

1058458771.118.png

1058458771.119.png

1058458771.120.png

1058458771.121.png

1058458771.123.png

1058458771.124.png

1058458771.125.png

1058458771.126.png

1058458771.127.png

1058458771.128.png

1058458771.129.png

1058458771.130.png

1058458771.131.png

1058458771.132.png

1058458771.134.png

1058458771.135.png

1058458771.136.png

1058458771.137.png

Prowaditodonatpującejprocedury

Function zap(n:integer):integer;

var i,suma:integer;

begin

suma:=0;

for i:=1 to n do suma:=suma+2*i;

zap:=suma;

end;

Możnaumowaćapałkipoiomei pionowe oddzielnie. Patrz rysunek dla n=4 .

1058458771.138.png

1058458771.139.png

1058458771.140.png

1058458771.141.png

1058458771.142.png

1058458771.144.png

1058458771.145.png

1058458771.146.png

1058458771.147.png

1058458771.148.png

1058458771.149.png

1058458771.150.png

1058458771.151.png

1058458771.152.png

1058458771.153.png

1058458771.002.png

1058458771.003.png

1058458771.004.png

1058458771.005.png

1058458771.006.png

1058458771.007.png

1058458771.008.png

1058458771.009.png

1058458771.010.png

1058458771.011.png

1058458771.013.png

1058458771.014.png

1058458771.015.png

1058458771.016.png

1058458771.017.png

1058458771.018.png

1058458771.019.png

1058458771.020.png

1058458771.021.png

1058458771.022.png

1058458771.024.png

1058458771.025.png

1058458771.026.png

1058458771.027.png

1058458771.028.png

1058458771.029.png

1058458771.030.png

1058458771.031.png

1058458771.032.png

1058458771.033.png

1058458771.035.png

1058458771.036.png

1058458771.037.png

1058458771.038.png

1058458771.039.png

1058458771.040.png

1058458771.041.png

1058458771.042.png

1058458771.043.png

1058458771.044.png

1058458771.046.png

1058458771.047.png

1058458771.048.png

1058458771.049.png

1058458771.050.png

Stądmamy

Function zap(n:integer):integer;

var i,suma:integer;

begin

suma:=0;

for i:=1 to n do suma:=suma+i;

zap:=2*suma;

end;

b) Procedura rekurencyjna

bynapiaćprocedurrekurencyjnąwytarcyauważyćjakpowtaje n -ta figura z figury ( n-1)- ejJelipre

zap_rek(n) onacymylicbapałektworących n -tąigurtomamywory

zap_rek(1)=2,

zap_rek(n)=zap_rek(n-1)+2*n, dla n>1

Wyjanieniedla n=4 przedstawia rysunek

Stąd

Function zap_rek(n:integer):integer;

begin

if n=1 then zap_rek:=2 else zap_rek:=zap_rek(n-1)+2*n;

end;

c) Porównajobieprocedurypodwgldemłożonocicaowej

Liczba operacji elementarnych w trakcie obliczenia zap(n) jetunkcjąliniowąmiennej n ,wicłożonoćcaowa

użytegoalgorytmujetrówna Ѳ (n).

Obliczenie zap_rek(n) potrebujedokładnie n wywołańunkcji zap_rek na kolejnych argumentach od n do 1,

wicłożonoćcaowategoalgorytmujetteżrówna Ѳ (n).

d) Napirowiąaniediałającewtałymcaie

W tym celu wystarczy napiaćwórmatematycnynaumoblicanąwpunkcie a)

2*1+2*2+2*3+2*4+ ... +2*n = 2*(1+2+3+4+ ... +n)=

1058458771.051.png

1058458771.052.png

1058458771.053.png

1058458771.054.png

1058458771.055.png

1058458771.057.png

1058458771.058.png

1058458771.059.png

1058458771.060.png

1058458771.061.png

1058458771.062.png

1058458771.063.png

1058458771.064.png

1058458771.065.png

1058458771.066.png

1058458771.068.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin