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. szeptemberi 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. 28. Minden permutáció előállítható ciklikus módon. Az (i1,...,ik) ciklus azt jelenti, hogy az i1-edik elemet az i2-edik, az i2-edik elemet az i3-adik, ..., az ik-1-edik elemet az ik-adik, az ik-adik elemet pedig az i1-edik pozícióba kell mozgatni ahhoz, hogy mindegyikük a saját helyére kerüljön. Minden permutáció leírható egymástól független ciklusokkal.

Például az (1,2,3,4,5,6,7) sorozat egy permutációja a (4,3,2,7,5,1,6) sorozat ciklikus leírása az (1,4,7,6), (2,3), (5) három ciklusból álló sorozat, azaz az eredeti helyreállítható úgy, hogy az első elemet a negyedik helyre tesszük, a negyedik helyen levőt a hetedikre, ...

Készítsünk programot (I28.pas,...), amely beolvassa N értékét és az első N szám egy permutációját, majd megadja az ezt növekvő sorrendbe rendező ciklusokat! (10 pont)

Megoldás: 

Változók:
  N,i:Egész;
  permutacio,q:Tömb(1..255:Egész);
  
Permutacio;
Beolvassuk a permutációt ügyelve, hogy tényleg az első N elem permutációja legyen. Ennek algoritmusa később megtalálható. 
  Beolvas(N,permutacio) [permutacio az első N elem permutációja];
Ismétlünk, amíg fel nem dolgoztuk az összes elemet. 
  Ciklus
Megkeressük az első, persze n-nél kisebb fel nem dolgozott elemet. 
    i:=1;
    Ciklus amíg (q[i]=1) és (n>=i)
        i:=i+1;
    ciklus vége;
Kiíratjuk az első elemet. 
    Ha i<=n
      akkor Ki: i;
    elágazás vége;
Aztán kiíratjuk a ciklus többi elemét is. A már kiírt elem feldolgozását megjegyezzük a q tömb segítségével (0 feldolgozatlan, 1 feldolgozott). A következő elemet pedig úgy kapjuk, hogy az lesz a permutációfüggvény értéke az aktuális helyen. 
    Ciklus amíg (q[i]<>1) és (n>=i)
      q[i]:=1;
      i:=p[i];
      Ha q[i]=0
        akkor Ki: i;
      elágazás vége;
    ciklus vége
  amíg i<=n
  ciklus vége;
Eljárás vége;
A beolvasás közben ellenőrizni kell, hogy csak N-ig adjunk meg számokat illetve, hogy egy szám csak egyszer szerepeljen. Ehhez az ilyenmarvolt függvényt is használjuk segítségként. 
  Változók
    i:Byte;
    ok:Boolean;
    s:String;
    c:Integer;

    ilyenmarvolt:Boolean;
      Változó
        j:Egész;
Az elsőtől kezdve minden elemmel összehasonlítjuk, végül IGAZ az eredmény, ha ugyanez az elem kisebb indexnél is előfordul, különben HAMIS. 
      j:=1;
      Ciklus amíg (i>j) és (p[j]<>p[i])
        j:=j+1;
      ciklus vége;
      ilyenmarvolt:=(i>j);
    függvény vége;{_ilyenmarvolt}

  Beolvas(N,permutacio);
Beolvasunk egy egész számot 1 és MaxN között. 
    ok:=FALSE;
    Ciklus
      Be: n;
      ok:=(n>=1) és (MaxN>=n);
    amíg nem ok;
    ciklus vége;
Beolvasunk egy N elemű tömböt, melyben 1 és N közötti számok szerepelhetnek, de mindegyik csak egyszer. 
    i:=1;
    Ciklus amíg n>=i
      Be: p[i]
      Ha (1>p[i]) vagy (p[i]>n)
        akkor Ki: 'HIBA! Rossz szám.';
        különben Ha ilyenmarvolt
          akkor Ki: 'HIBA! Ilyen érték már szerepelt.';
          különben i:=i+1;
        elágazás vége;
      elágazás vége;
    Ciklus vége;
  Eljárás vége;
A megoldás Pascal nyelven letölthető innen.

I. 29. Egy körlemezt a középpontjával és sugarával adhatunk meg. A körlemezből kétféle módon vághatunk ki részeket: vagy egy körcikket (kezdőszöge az északi irányhoz képest az óramutató járása szerint ALFA fok, nyílásszöge BÉTA fok), vagy egy körgyürüt (a belső köríve a középponttól B, a külső pedig K távolságra van.

Készítsünk programot (I29.pas,...), amely egy körre alkalmaz adott darabszámú kivágás müveletet, s minden lépés után kirajzolja a megmaradt lemezt!

Példa: az alábbi ábrán lépésenként láthatjuk az egyes müveletek utáni eredményt.

Kör(150,150,100)Cikk(0,30)Gyűrű(10,20)Cikk(120,45)Gyűrű(50,75)

(10 pont)

Megoldás: 

Kor;
  Konstans
    maxdb=100;
  Változók
    q,i,j,xx,yy,r,x,y,db: Egész;
    b,k,alfa,beta:Tömb(1..maxdb:Egész);
    c: Tömb(1..maxdb:Karakter);
Beolvassuk a középpont koordinátáit, a kör sugarát illetve a műveletek számát. 
  Be: x,y,r,db;
Beolvassuk a db darab művelet típusát, majd a típustól függően a további adatokat. Körcikk esetén a kezdő- és nyílásszöget, körgyűrű esetén a belső és a külső sugarat. 
  Ciklus i:=1-től db-ig
    Be: c[i];
    Ha c[i]=KORCIKK
      akkor
        Be: alfa[i], beta[i];
      különben
        Be: b[i], k[i];
    elágazás vége;
  ciklus vége;
Beállítjuk grafikus rajzolást, majd kirajzoljuk a kezdeti kört. 
  GrafikusKépernyőInicializálása;
  KitöltésBeállítása(Teljes,Piros);
  EcsetszínBeállítása(Piros);
  RajzolásiMódBeállítása(Felülírás);
  SzögtartományRajzolása(x,y,0,360,r);
Minden műveletet kirajzolunk. A használt programozási nyelvekben a szögtartomány rajzolására van parancs, ezért ezt könnyű megvalósítani. 
  Ciklus i:=1-től db-ig
    Ha c[i]=KORCIKK
      akkor
        KitöltésBeállítása(Teljes,Fekete);
        EcsetszínBeállítása(Fekete);
        ha beta[i]=360
          akkor SzögtartományRajzolása(x,y,0,360,r)
          különben SzögtartományRajzolása(x,y,450-alfa[i],450-alfa[i]-beta[i],r);
        elágazás vége;
      különben
A körgyűrű rajzolását mi valósítjuk meg. A középpont középpontú két sugár nagyságú négyzetben vizsgáljuk végig a pontokat. Akkor rajzoljuk ki feketével, ha az adott pont a körgyűrű pontja, vagyis a középponttól való távolsága nagyobb, mint a belső sugár, de kisebb, mint a külső sugár. 
        ciklus xx:=x-k[i]-től x+k[i]-ig
		  ciklus yy:=y-k[i]-től y+k[i]-ig
            q:=kerekítés(négyzetgyök((xx-x)*(xx-x)+(yy-y)*(yy-y)));
            ha (q<=k[i]) és (q>=b[i])
              akkor PontRajzolás(xx,yy,Fekete);
            elágazás vége;
          ciklus vége;
        ciklus vége;
    elágazás 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 Pascal nyelven letölthető innen.

I. 30. A binomiális együtthatók szokásos elrendezése (Pascal háromszög) az ábrán látható alakú lehet. A szélső elemek kivételével mindegyikre igaz, hogy a fölötte levő, és az attól eggyel balra levő elem összege.

1      
11     
121    
1331   
14641  
15101051 
1615201561

Készítsünk Excel táblázatot (I30.xls), amely ilyen módon képes megadni a Pascal háromszög első 50 sorát! Fontos feltétel: a tábla 50x50-es méretü, s minden mezőbe ugyanazt a képletet kell írni! A legfelső elem a tábla B2-es pozícióján legyen!

Figyelem: a feladat szinte azonos az elmúlt évi I.9. feladattal, de a megoldás követelményei mások, így a tavalyi feladat megoldása most 0 pontot ér! (10 pont)

Megoldás:

Háromféle mező van a táblázatban. Van ahova 1-est, van ahova semmit és van olyan hely, ahova a felette levő sorból a felette levő és az azt megelőző elem összegét kell írni. Egyest az első oszlopba és az átlóba. Nem kell semmit sem írni a Pascal hárpmszögön kívül, vagyis oda, ahol az oszlop száma nagyobb, mint a sor száma. 
B2=IF(OR(COLUMN()=ROW();COLUMN()=1);1;IF(COLUMN()>ROW();"";A1+B1))
A megoldás Excelben letölthető innen.