A KöMaL 2007. szeptemberi informatika feladatai

I-jelű feladatok A beküldési határidő 2007. október 15-én LEJÁRT.

I. 163. A digitális adatátvitel során fellépő hibák javítására alkalmazott kódok közül az egyik leghíresebb Richard Wesley Hamming nevéhez fűződik. A kód egyik változata 7 bitenként legfeljebb egy ú.n. átállítódásos hiba (az átvitel során egy bit értéke invertálódik, azaz ellentettjére változik) javítására képes.

A kódolás menete a következő. A továbbítandó adatokat 4 bites egységekre bontjuk, majd ezeket 3 ellenőrzőbittel egészítjük ki az alábbiak szerint:

(Ahol a modulo 2 összeadás, a ,,kizáró vagy'' művelet: akkor és csak akkor, ha x₁,x₂,...,x_n bitek közül páratlan sok egyes.)

Az így kapott 7 bites k₇...k₁ kódszókat visszük át, a vevő által érzékelt (esetleg hibás) kódot jelöljük f₇...f₁-gyel.

A dekódolás a következőképp zajlik. A megfelelő f_j-kből újból kiszámoljuk az ellenőrzőösszegeket, és az eredményt összevetjük az f₄, f₂ és f₁ ellenőrzőbitekkel. (Tehát például f₂-t az összeggel.) Azokat az i indexeket, melyekre az f_i ellenőrzőbit értéke helytelen, összeadjuk. Ha az így kapott érték 0, akkor a kódszó hibátlan, egyébként pedig, és itt mutatkozik meg a kód igazi szépsége, a hiba helyét adja, így azt invertálással rögtön javíthatjuk. Ezután a (már) helyes kódszó megfelelő bitjeit kiolvasva megkapjuk az adatot.

Írjunk programot, amely attól függően, hogy első parancssori argumentuma ,,be'' vagy ,,ki'', a második argumentumként kapott fájlt be-, illetve kikódolja a harmadik argumentumként kapott fájlba. A fájlokban az adat- és kódszavak szóközzel elválasztott 0-1 sorozatok legyenek. A kódbitek kódszón belüli sorrendje tetszőleges.

(Az első kódban az f₄ ellenőrző bit jelez hibát, így a 4. bitet, f₄-et invertáljuk. A második kód helyes, a harmadikban pedig f₄ és f₂ is hibát jelez, így a 6. bitet, f₆-ot kell javítani.)

Beküldendő a program forráskódja (i163.pas, i163.cpp, ...), valamint a program rövid dokumentációja (i163.txt, i163.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

megoldás, statisztika

I. 164. A sejtautomata játék egy változatában a világot egy 27×27-es méretű négyzetrácsnak tekintjük, melynek mezőin sejtek élnek, egy mezőn legfeljebb kettő. A négyzetrács szélén lévő cellák érdekessége, hogy nekik is négy élszomszédjuk van: a felső sorban lévő cellák szomszédosak az alsó sor megfelelő celláival és viszont, hasonlóan a bal oldali oszlop cellái a jobb oldali oszlop celláival.

Szabályos időközönként új generációk jönnek létre. Minden sejt négyfelé osztódik, s ő maga elpusztul (egy-egy utód kerül a négy szomszédos cellák mindegyikébe). Ha egy cellába több utód is kerül, akkor azok hármasával elpusztítják egymást, amíg legfeljebb 1 vagy 2 marad.

Írjunk programot, amely a sejtek jelenlegi elhelyezkedése alapján meghatározza, hogy hogyan fog kinézni a világ N generáció múlva.

A program a szükséges adatokat a standard bemenetről olvassa. A bemenet első sora a generációk N () számát tartalmazza, az ezt követő 27 sor pedig rendre 27 számjegyet, a megfelelő cellákban élő sejtek számát (0, 1 vagy 2). Az eredményt a standard kimenetre írjuk, a bemenettel megegyező formátumban.

Ügyeljünk rá, hogy a program nagy N-ekre is gyorsan lefusson. Keressünk szabályosságot.

Helyszűke miatt itt egy kisebb (de minden más szempontból azonosan működő) példát közlünk:

Egy teljes 27×27-es példa letölthető az Internetről.

Beküldendő a program forráskódja (i164.pas, i164.cpp, ...), valamint a program rövid dokumentációja (i164.txt, i164.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

27×27-es példa bemenet

27×27-es példa kimenet

(10 pont)

megoldás, statisztika

I. 165. Egy Excel táblázat első munkalapjának ,,A'' oszlopában 0 és 1-es számjegyeket tárolunk. A számsor első néhány eleme 0, majd 8 darab 1-es jelzi az értékes adatok elejét. Az ezután következő 8-as számcsoportok egy bájt bitjeit tárolja. Az adat egy szöveges állományból származik, minden bájt egy ASCII karakternek felel meg. Az utolsó adat után a cellák üresek.

A B1-es cellába készítsük el azt a képletet, amely helyreállítja az eredeti szöveget. A szöveg legfeljebb néhány száz karaktert tartalmaz. A szükséges képleteket, mellékszámításokat a kettes munkalapon végezzük.

Például: ha az ,,A'' oszlop tartalma:

A kimenet (B1 cella) értéke: 6aA.

Beküldendő a táblázatkezelő munkafüzet (i165.xls, i165.ods, ...) illetve egy rövid dokumentáció (i165.txt, i165.pdf, ...) amelyben szerepel a megoldáskor alkalmazott táblázatkezelő neve, verziója, valamint a megoldás rövid leírása.

(10 pont)

megoldás, statisztika

S-jelű feladatok A beküldési határidő 2007. október 15-én LEJÁRT.

S. 28. A römi játék egy változatát két csomag francia kártyával játsszák. A játékot az nyeri, aki elsőként tudja a kezében lévő kártyákat az előírt szabályok szerint az asztalra rakni. A lerakás szabályai a következők:

1. A kártyákat legalább három lapból álló csoportokban lehet az asztalra helyezni úgy, hogy abban a lapok vagy azonos színű sorozatot alkotnak, vagy különböző színűek, de azonos számot vagy figurát tartalmaznak. Az első esetre példa a Kör 3-as, Kör 4-es, Kör 5-ös, Kör 6-os lapokból álló négyes, a másodikra példa a Kör király, Káró király, Pikk király lapokból álló hármas csoport. Nem helyes azonban a Kör 4-es, Kör 5-ös, Káró 6-os, vagy a Pikk ász, Pikk ász, Treff ász csoport.

2. A sorozatok csak azonos színű kártyákból állhatnak, a lapok sorrendje 2-es, 3-as, ..., 9-es, 10-es, bubi, dáma, király, ász, vagy ász, 2-es, 3-as, ..., 9-es, 10-es, bubi, dáma, király. Az ász kártya tehát vagy kezdő, vagy záró tagja egy sorozatnak. Helyes sorozat például a Treff 10, Treff bubi, Treff dáma, vagy a Kör ász, Kör 2-es, Kör 3-as, Kör 4-es; nem megfelelő a Pikk király, Pikk ász, Pikk 2-es.

3. A csoportok képzésénél tetszőleges lap helyettesíthető Joker kártyával, de a csoportban a nem Joker lapok száma nagyobb kell, hogy legyen a Joker lapok számánál. Helyes csoport példaként a Kör 9-es, Kör 10-es, Joker, Joker, Kör király sorozat, de nem helyes a Joker, Pikk 4-es, Joker, vagy a Kör 5-ös, Joker, Joker, Kör 8-as.

A játékosok játék közben a kezükben lévő lapokat tehetik le az asztalra, illetve a már az asztalon lévő lapokat rendezhetik át úgy, hogy a lapok az átrendezés után is a leírt szabályoknak megfelelően helyezkedjenek el. Legyen például az asztalon a Kör 5-ös, Káró 5-ös, Treff 5-ös, Pikk 5-ös lapnégyes, a játékos kezében pedig a Treff 4-es és a Treff 6-os. Ekkor a játékos kialakíthat egy Kör 5-ös, Káró 5-ös, Pikk 5-ös, illetve egy Treff 4-es, Treff 5-ös és Treff 6-os csoportot - így a kezében lévő két kártyát az asztalon lévő lapok átrendezésével lerakhatja.

A soron következő játékos az asztalról lapot nem vehet fel, és amennyiben nem tud letenni, úgy a még ki nem osztott lapokból húznia kell. Készítsünk programot s28 néven, amely az asztalon és a játékos kezében található lapok esetén a lehető legtöbb kártya asztalra helyezését végzi el. A program olvassa be a parancssorban megadott első állományából az asztalon lévő lapokat, a második állományból a játékos kezében lévő lapokat, és írja a standard kimenetre az asztal átrendezés és lerakás utáni helyzetét, valamint a kezében lévő lapokat.

A bemeneti állományokban és a kimeneten a francia kártya Kör, Káró, Treff, Pikk színét a K, R, T, P betű, a lapok értékét a 2, 3, ..., 9, 0 szám, illetve a J, Q, K, A betű jelölje. A K4 tehát a Kör 4-es, az RA a Káró ász, a T0 a Treff 10-es, a PJ a Pikk bubi, a PQ a Pikk dáma jelölése. A Joker lapoknak nincs színük, jelölésük JJ.

Az első bemeneti állomány az asztalon található lapokat csoportonként egy-egy sorban, laponként egymástól szóközzel elválasztva, a sorozatok tagjait növekvő sorrendben tartalmazza. A bemeneti állomány lehet üres, ekkor az asztalon még nincs lerakva egy kártya sem. A második bemeneti állomány a játékos kezében lévő lapokat tartalmazza egy sorban, egymástól szóközzel elválasztva. Ez az állomány nem lehet üres, legkevesebb egy kártyát tartalmaz. A kimenet először az asztalon lévő kártyákat adja meg csoportonként egy-egy sorban, egymástól szóközzel elválasztva, a sorozatok kártyáit növekvő sorrendben, majd a kézben maradt lapokat egy sorban, szóközzel elválasztva.

Példa: Legyen az asztalon található lapokat megadó szöveges fájl (a.txt) tartalma:

K4 JJ K6 K7
PQ KQ TQ
TA T2 T3 T4 T5

A játékos kezében lévő kártyákat leíró (b.txt) tartalma:

K5 K5 JJ TK T0

Ekkor a program az s28 a.txt b.txt meghívás eredményeként a kimenetre a következőket írja:

K4 K5 K6 K7
TQ TK TA
PQ KQ JJ
T2 T3 T4
K5 T5 JJ
T0

Beküldendő a program forráskódja (s28.pas, s28.cpp, ...), valamint a program rövid dokumentációja (s28.txt, s28.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

megoldás, statisztika