Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A 2002. októberi informatika feladatok megoldása

A közöltek csak megoldásvázlatok, esetleg csak végeredmények. A maximális pontszám eléréséhez általában ennél részletesebb megoldás szükséges. A részletes megoldásokat a beküldött dolgozatok alapján a KöMaL-ban folyamatosan közöljük.


I. 31. Az ókori Egyiptomban a 0 és 1 közötti racionális számokat egységtörtek összegeként \(\displaystyle \frac{1}{x_1}+\frac{1}{x_2}+\ldots+\frac{1}{x_k}\)alakban adták meg, ahol az xi-k különböző pozitív egész számok.

Például

\(\displaystyle \frac{2}{5}=\frac{1}{3}+\frac{1}{15},\quad\frac{9}{11}=\frac{1}{2}+\frac{1}{4}+\frac{1}{15}+\frac{1}{660},\quad\frac{19}{30}=\frac{1}{2}+\frac{1}{8}+\frac{1}{120}. \)

Készítsünk programot (I31.pas, ...), amely adott M (1 \(\displaystyle \le\)M<N) és N (2 \(\displaystyle \le\)N \(\displaystyle \le\)30) természetes számokra megadja M/N egységtörtekre bontását!

(10 pont)

Megoldás:
Rekurzív megoldást adunk.

Eljárás Reciprok;
  változók n,m: Egész;
  Be: N [1<N<=30];
  Be: M [1<=M<N];
  Ki: 'M/N=';
  REC(M,N);
Eljárás vége;
A REC eljárásban számoljuk ki az összeg legnagyobb tagját. Majd önmaga meghívásával a következő tagokat is.
Eljárás REC(m,n: Egész);
  változók p,q,r: Egész;
Speciálisan az első (m) paraméter kisebb, mint a második (n). Így ki tudjuk számolni a hányados értékét, vagyis a reciprokát. Ha vesszük a felső egész részét (q), akkor a reciprok (1/q) kisebb lesz, mint m/n, illetve pont keresett alakú.
  q:=n div m;
  Ha n mod m>0
    akkor inc(q);
  elágazás vége;
Kiíratjuk ezt a számot.
  Ki: '1/',Q;
Van még következő tag is, ha M/N>1/Q, vagyis M*Q-N>0. Ekkor még átrendezés után ezt kapjuk: (Q*M-N)/(N*Q), amit egyszerűsítünk, és keressük az összegtagot, vagyis rekurzívan meghíjuk ezt az eljárást.
  Ha m*q-n>0
    akkor r:=lnko(q,n);
	      q:=q div r;
          p:=lnko(q*m-n div r,q*n);
          Ki: '+';
		  REC((m*q-n div r) div p,q*n div p);
  elágazás vége;
Eljárás vége;
Felhasználjuk az a speciális ismeretünket, hogy a paraméterek között előbb a kisebb, majd a nagyobb szerepel. Így a legnagyobb közös osztót úgy számolhatjuk ki, hogy az a nagyobb szám, ha a kisebb nulla. Más esetben pedig megegyezik a nagyobb szám kissebbel való osztása során képzett maradékkal és a kisebb szám legnagyobb közös osztójával.
Függvény lnko(m,n: Egész): Egész;
  Ha m=0
    akkor lnko:=n;
	különben lnko:=lnko(n mod m,m);
  elágazás vége;
függvény vége;
A megoldás Pascal nyelven: Letöltés


I. 32. Kettőspoligont úgy kapunk, hogy két szabályos sokszöget ,,összefésülünk'', azaz az oldalaikat felváltva rajzoljuk le. (Az alábbi ábrán egy négyzetet és egy háromszöget fésültünk össze úgy, hogy mindkettőből 3 oldalt rajzoltunk meg. Ha 4 oldalt rajzolnánk, akkor a V2 vektorhoz az U3 vektort kellene illesztenünk, ahhoz pedig ismét a V0 vektort.)

A multipoligon ugyanígy készül, csak nem kettő, hanem több szabályos sokszögből.

Készítsünk programot (I32.pas, ...), amely beolvassa az összefésülendő sokszögek számát (1 \(\displaystyle \le\)DB \(\displaystyle \le\)100) és a mindegyikükből rajzolandó oldalak számát (1 \(\displaystyle \le\)N \(\displaystyle \le\)360), az egyes sokszögek oldalhosszát (1 \(\displaystyle \le\)H(i) \(\displaystyle \le\)100) és külső szögét (-120 \(\displaystyle \le\)S(i) \(\displaystyle \le\)120), majd kirajzolja a belőlük összeállított multipoligont!

Példa:

DB=2, N=3
H=50, SZ=90
H=50, SZ=120
DB=2, N=40
H=50, SZ=90
H=50, SZ=-40
DB=2, N=360
H=0.5, SZ=1
H=1, SZ=-1
DB=4, N=360
H=1, SZ=1
H=1, SZ=-8
H=1, SZ=16
H=1, SZ=-2

(10 pont)

Megoldás:

Eljárás multigon;
  változók
    i,j,n,db:Egész;
    sz:Tömb(1..100:Egész);
    h,s:Tömb(1..100:Valós);
    x,y,alfa:Valós;
Beolvassuk a kirajzolandó sokszögek illetve oldalaik számát. Majd a mindegyiknek az oldalhossz illetve külsőszög adatait. A szöget a fokból átszámoljuk radiánba.
   Be: N, DB;
   Ciklus i:=1-től db-ig
     Be: h[i],sz[i];
     s[i]:=3.14159*sz[i]/180;
   ciklus vége;
Beállítjuk a grafikus felületet és a képernyő közepére állítjuk a grafikus kurzort.
   GrafikusKépernyőInicializálása;
   x:=KépernyőMéretX div 2;
   y:=KépernyőMéretY div 2;
   PozícióraUgrás(kerekítés(x),kerekítés(y));
Egymásba ágyazott ciklusokkal, vagyis a kirajzolandó oldalszámszor a db darab sokszögből kirajzolunk egy-egy oldalt (szakaszt). A következő x és y koordinátákat számoljuk az aktuális oldalhossz és a bezárt szög segítségével. Ez a szög pedig éppen az aktuális sokszög külső szögének annyiszorosa, ahányadik oldalt rajzoljuk.
   Ciklus i:=1-től n-ig
     ciklus j:=1-től db-ig
       alfa:=i*s[j];
	   x:=x+sin(alfa)*h[j];
	   y:=y+cos(alfa)*h[j];
       SzakaszRajzolás(kerekítés(x),kerekítés(y));
     ciklus vége;
   ciklus vége;
Visszaállítjuk a karakteres képernyőt.
  GrafikusKépernyőLezárása;
eljárás vége.
A megoldás Delphiben: Letöltés


I. 33. Jóska és Pista számjátékot játszanak. Első lépésként felsorolnak N (1 \(\displaystyle \le\)N \(\displaystyle \le\)100) természetes számot, majd eldöntik, hogy mindegyikük M (1 \(\displaystyle \le\)M \(\displaystyle \le\)\leN) számot fog választani közülük. Szabályosan választanak, Jóska minden A-adik számot (1 \leA \leN), Pista pedig minden B-ediket (1 \leB \leN). Ha a sorozat végére érnek, elölről folytatják, azaz pl. az N+1. szám a felsorolás első tagja lesz, az N+2. a második és így tovább. Az győz, aki a kiválasztott számait összeadva nagyobb számot kap.

Készítsünk táblázatot (I33.xls), amelyben N, M, A, B megadása esetén megtudjuk, hogy ki győzött. A győztes betűjele (A vagy B) a táblázatban piros, a vesztesé pedig kék színű legyen! Döntetlen játék esetén mindkettőt feketével kell írni.

Példa:

N= 10 11 12 13 14 15 16 17 18 19 20    
M= 6                        
A: 3 14 17 20 13 16 19         A összege: 99
B: 4 15 19 13 17 11 15         B összege: 90

(10 pont)

Megoldás:
Három lépésben oldjuk meg a feladatot.
Először az első sorban levő sorozatból képezzük másik két sorozatot a harmadik illetve a negyedik sorba az allábi képlet segítségével.

D3:=IF(COLUMN()<=$B$2+2;INDEX($C$1:$IV$1;1;MOD((COLUMN()-2)*$B3;$B$1)+1);"")
vagy
D3:=HA(OSZLOP()<=$B$2+2;INDEX($C$1:$IV$1;1;MARADÉK((OSZLOP()-2)*$B3;$B$1)+1);"")
Vagyis csak a B2-es cellában levő darabszámnak megfelelő tagot kell kiíratni, többet nem. Oda pedig a C1:V1-es tartomány első (1) sorából egy mezőt, melynek oszlopindexét egy maradékos osztással kapunk. Oszlopindexet a lépésközzel szorozzuk, majd elosztjuk az eredeti sor méretével, hiszen tovább nem léphetünk, persze végül eggyel el kell tolnunk, mert nincs nulladik mező.
Második lépésben az összeget könnyen ki tudjuk számoltatni:
M3:=SUM(C3:L3)
Végül, ezt az értéket felhasználva a feltételes formázással színezzük ki a győztes betűjelét.
A megoldás Excelben: Letöltés