XXXVII, 1989.-1990. õppeaasta

Lõppvooru ülesanded

1. ülesanne

Olgu antud programm Basic 'us

10 INPUT A,B
20 K=0 : SC=0
30 PT=1 : R=A
40 IF K=B THEN 110
50 IF K+PT <= B THEN 80
60 PT=1 : R=A
70 GOTO 40
80 K=K+PT : PT=PT+PT
90 SC=SC+R : R=R+R
100 GOTO 40
110 PRINT SC
120 END

või Pascal 'is

begin 
   readln(A,B);
   K:=0; SC:=0; PT:=1; R:=A;
   while KB do 
      if K+PT <= B then
         begin 
         K:=K+PT; PT:=PT+PT;
         SC:=SC+R; R:=R+R;
         end
      else
        begin
        PT:=1; R:=A;
        end;
      writeln(SC);
end.

Kuidas avaldub SC lõppväärtus A ja B kaudu?

B naturaalarvulist väärust, mille korral else osa (Basic-programmis rida 60) täidetakse korduvalt, nim. ebasoodsaks .

a) Leida ilmutatult (st valemiga) kõik B ebasoodsad väärtused.

b) Näidata, et tsükli täitmise kordade arv ei sõltu A väärtusest.

c) Ebasoodsa B väärtuse jaoks väljendada ilmutatult täitmiskordade arv

1. then -- haru jaoks (BASIC-programmis read 80,90)

2. else -- haru jaoks (rida 60).

2. ülesanne

Tasandil on antud n punkti koordinaatidega

(X1,Y1), (X2,Y2), .. , (Xn,Yn).

Koostada algoritm ja programm leidmaks neist sellised punktinelikud, mis oleksid mingi ruudu tippudeks. Leida nii määratud ruutude hulgast selline, mis hõlmaks maksimaalse hulga vaadeldavaid punkte. Seejuures lugeda ruutu kuuluvaks ka selle külgedele sattunud punktid.

Praktiline voor

1. Putukate arv N[i] mingil aastal on määratud valemiga

N[i] = a*N[i-1] - b*N[i-1]^2,

kus N[i-1] on putukate arv eelmisel aastal, a on paljunemiskordaja ning b üleasustuskordaja. Leida tingimused kordajatele a ja b selleks, et paljude aastate möödudes putukate arvukus:

a) stabiliseeruks;

b) muutuks kaheaastase perioodiga;

c) muutuks nelja-aastase perioodiga;

d) muutuks seaduspäratult.

2. Lahendada jõukohane variant järgmisest ülesandest: lugeda stringina aritmeetiline avaldis ja arvutada selle väärtus, kui avaldis koosneb:

1) naturaalarvudest ja märkidest +, -;

2) naturaalarvudest ja märkidest +, -, *, /;

3) naturaalarvudest, sulgudest ja märkidest +, -, *, /.

Avaldise sisestamisel peab programm teatama, millest võib avaldis koosneda.

3. Linna metroojaamad on tähistatud tähtedega A, B, C, ... (kuni 30 jaama) ja liinid sõnadega, mis koosnevad jaamade tähtedest liinil asumise järjekorras (ringliini korral on sõna esimene ja viimane täht võrdsed). Kui jaamas saab teisele liinile ümber istuda, siis on ta mõlemal liinil tähistatud sama tähega. On teada, et metroo koosneb mitmest osast ja ühestki jaamast ei saa sõita kõigisse teistesse (isegi ümberistumisi kasutades).

Lugeda sisse metrooliinid ja kahe jaama tähised.

1) Kontrollida, kas esimesest jaamast saab sõita teise.

2) Kui saab, siis leida kiireim tee kahe loetud jaama vahel (lugedes ajakulu sõitmisel peatusest naaberpeatusse kõikjal ühesuguseks ning 3 korda väiksemaks kui ümberistumisele kuluv aeg).