A KöMaL 2018. januári informatika feladatai

I-jelű feladatok A beküldési határidő 2018. február 12-én LEJÁRT.

I. 445. A matematikában a \(\displaystyle \pi\) nemcsak fontos természeti állandó, hanem a tudásterület egyik jelentős szimbóluma is. Minél pontosabb meghatározása ezért régóta foglalkoztatja nemcsak a matematikusokat, hanem a matematika iránt érdeklődő laikusokat is. Az évszázadok során sokféle közelítő eljárást dolgoztak ki a \(\displaystyle \pi\) meghatározására. Ezek közül Machin sorozata egy gyorsan konvergáló, tehát viszonylag kevés számú tag kiszámításával is kellően sok jegyre pontos eredményt adó megoldás. Machin a

\(\displaystyle \frac{\pi}{4}=4\arctg \frac{1}{5}-\arctg \frac{1}{239} \)

összefüggés sorbafejtésével a

\(\displaystyle \frac{\pi}{4} = 4\left[ \frac{1}{5}-\frac{1}{3}\left(\frac{1}{5}\right)^{\!\!3} +\frac{1}{5}\left(\frac{1}{5}\right)^{\!\!5} -\frac{1}{7}\left(\frac{1}{5}\right)^{\!\!7}+\cdots \right] -\)

\(\displaystyle {} -\left[\frac{1}{239}-\frac{1}{3} \left(\frac{1}{239}\right)^{\!\!3}+\frac{1}{5}\left(\frac{1}{239}\right)^{\!\!5}-\ldots \right]\)

képletet kapta.

Készítsünk programot, amely a fenti sorozat alkalmazásával meghatározza \(\displaystyle \pi\) értékét legalább 1000 tizedesjegy pontossággal. A nagy pontosságú aritmetikai műveleteket (összeadás, kivonás, szorzás, osztás) nekünk kell megvalósítanunk. A megoldás elkészítése során legfeljebb 32 bit pontosságú egész számokat használjunk, és a ne alkalmazzuk a programozási nyelv vagy fejlesztői környezet által biztosított, 32 bitnél több jeggyel dolgozó aritmetikai műveleteket támogató modulokat sem.

A kapott eredmény ellenőrzésére a http://www.geom.uiuc.edu/~huberty/math5337/groupe/digits.html címen található adatokat javasoljuk.

Beküldendő egy i445.zip tömörített állományban a megoldás forráskódja, a megoldás által készített, a \(\displaystyle \pi\) első 1000 tizedesjegyét tartalmazó szöveges állomány, továbbá a megoldás során használt eljárások rövid dokumentációja.

(10 pont)

megoldás, statisztika

I. 446. (É). A Rubicon egy történelmi ismeretterjesztő lap, melynek első lapszáma 1990. február 1-jén jelent meg. 2017. szeptemberéig összesen 311 számot adtak ki. Az eddig az időpontig megjelent lapszámok legfontosabb adataiból készítsünk adatbázist. Forrásként a kiadvany.txt és ajanlo.txt állományok állnak rendelkezésünkre, melyek UTF-8 kódolású szövegfájlok, az első sorok a mezőneveket tartalmazzák. Néhány számot dupla számként adtak ki, így többször szerepel két külön megjelenési hónapnál, azonos szám és különböző ,,azonosító'' számok alatt.

1. Készítsünk új adatbázist rubicon néven. A mellékelt adatállományokat importáljuk az adatbázisba a fájlnévvel azonos nevű táblákba. Beolvasáskor állítsuk be a megfelelő típusokat és kulcsokat.

Táblák:

Készítsük el a következő feladatok megoldásait. Az egyes lekérdezéseknél ügyeljünk arra, hogy mindig csak a kért értékek jelenjenek meg és más adatok viszont ne. A megoldásainkat a zárójelben lévő néven mentsük el.

2. Lekérdezés segítségével adjuk meg, hogy egy számnak hány alcíme van feltüntetve az adatbázisban. Minden szám egyszer jelenjen meg, és mellette legyen látható az alcímek száma. (2alcimek)

3. Lekérdezés segítségével adjuk meg azon számok főcímét, amelyek nevében van arab szám. (3szamok)

4. Lekérdezés segítségével írassuk ki azon számok főcímét, amik különszámok voltak. (4kulonszam)

5. Mennyibe kerülne megrendelni az összes 2015-ben kiadott lapot, 2 példányban? (5ossz2015)

6. Határozzuk meg, hogy van-e, és ha igen, melyik vagy melyek azok az évek, amikor az összes hónap lapszámát lehet utánrendelni. A különszámokat ne vizsgáljuk. (6mind)

7. Számoljuk össze, hány lapszám főcímében szerepel a szent szó. (7szent)

8. Van-e olyan szám, amihez nem tartozik alcím az adatbázisban? Ha igen, írassuk ki a számok főcímét és kiadásának dátumát. (8nincsalcim)

9. Az alcímek között néhány helyen meg van adva a cikk szerzője. Írassuk ki azoknak a nevét, akik többször is írtak cikket. (9tobbcikk)

10. Készítsünk jelentést, amely év szerint csoportosítva, a lapszám főcíme szerinti ábécérendben jeleníti meg az adott szám árát. Dupla szám esetében két hónapnál is megjelenhet az adott szám. Az ár mögött jelenjen meg a ,,Ft'' mértékegység. (10jelent)

Beküldendő egy tömörített i446.zip állományban az adatbázis, valamint egy rövid dokumentáció, amely megadja az alkalmazott adatbázis-kezelő nevét és verziószámát.

A feladat forrása: http://www.rubicon.hu/megrendelheto/termekek/folyoirat/ (utolsó letöltés: 2017. 10. 01.).

Letölthető fájlok: kiadvany.txt, ajanlo.txt.

(10 pont)

statisztika

I. 447. A most megjelenő C. 1460. feladatban leírt hópehely grafikus megvalósításával készítsünk hóesés szimulációt. A havazás egy percig tartson úgy, hogy kezdetben kevés, majd egyre több, végül ismét kevés hópehely jelenjen meg a képtér felső részén. A hópelyhek mérete változatos legyen, de a legnagyobb és legkisebb átmérőjének aránya ne érje el a kettőt. A hópelyhek a képtér tetején vegyesen, a képződés első vagy második lépése utáni állapotban hulljanak lefelé. A hópelyhek esési sebességét a méretükkel egyenesen arányosra állítsuk: a legkisebbek essenek a legnagyobb sebességgel. A képtér alján a hópelyhek tűnjenek el.

A feladat megoldásához a versenykiírásban szereplő programozási nyelvek mellett HTML/CSS/Javascript segítségével készült megoldásokat is elfogadunk. A versenykiírás szerinti programozási nyelveken készült megoldások legyenek fordíthatók és futtathatók kiegészítő grafikus könyvtárak nélkül, tehát csak a fejlesztői környezetben megtalálható, beépített grafikai modulok fölhasználásával. A böngészőben futó megoldásoknak offline is működniük kell, azaz nem tartalmazhatnak külső hivatkozásokat. Javasoljuk például a HTML5 Canvas használatát.

Beküldendő egy i447.zip tömörített állományban a program forráskódja, továbbá egy rövid dokumentáció, amely tartalmazza, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

megoldás, statisztika

I/S-jelű feladatok A beküldési határidő 2018. február 12-én LEJÁRT.

I/S. 23. Egy \(\displaystyle N\times N\)-es ,,sakktábla'' világos színű mezőin \(\displaystyle S\) számú sötét gyalogot helyezünk el. Feladatunk az, hogy egy világos futó segítségével közülük minél többet leüssünk. A futó a szokásos módon mozoghat a táblán, de irányt váltani csak akkor tud, ha olyan mezőre lép, amelyen éppen leüt egy gyalogot. A futó kezdeti helye nincs rögzítve, azt mi választhatjuk meg.

Készítsünk programot, amely megadja, hogy adott állások esetén legföljebb hány gyalogot lehet a tábláról levenni.

A program standard bemenete az \(\displaystyle N\) és \(\displaystyle S\) egészek, valamint a következő \(\displaystyle S\) sor mindegyikében egy egész számpár. A számpárok a sötét gyalogok helyzetét adják meg: a bal felső (sötét) mezőtől indulva az egyes gyalogok sorát és oszlopát. A program standard kimenete legyen a levehető gyalogok maximális száma.

Magyarázat: a 4 1, 1 4, 3 6 és 5 4 mezőkön lévő gyalogok leütése pl. ebben a sorrendben lehetséges, ha a futó a 4 1 mezőről indul, de sajnos a többi gyaloghoz a futó nem tud eljutni.

Korlátok: \(\displaystyle 4 \le N \le 100\), \(\displaystyle 4 \le S \le 2\cdot N\).

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb \(\displaystyle N\) értékek esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy is23.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.

(Az októberi számunkban megjelent K. 513. feladat alapján)

(10 pont)

megoldás, statisztika

S-jelű feladatok A beküldési határidő 2018. február 12-én LEJÁRT.

S. 122. Legyen \(\displaystyle A\) az első \(\displaystyle P\) prímszám halmaza, és \(\displaystyle B\) egy \(\displaystyle N\) elemű, pozitív egészeket tartalmazó halmaz. Készítsünk 1-től kiindulva egy sorozatot, amelyben a sorozat következő tagja az előzőnek egy \(\displaystyle A\)-beli prímmel vett szorzata. Feladatunk az, hogy úgy képezzük a sorozat tagjait, hogy abban a lehető legtöbb \(\displaystyle B\)-beli szám forduljon elő.

Készítsünk programot, amely megadja, hogy adott \(\displaystyle A\) és \(\displaystyle B\) halmaz esetén mennyi a legtöbb olyan \(\displaystyle B\)-beli szám, amely egy szorzással keletkező sorozat tagjaként a fenti módon előállítható. A program standard bemenete \(\displaystyle P\) és \(\displaystyle N\), valamint a következő \(\displaystyle N\) sor mindegyikében egy pozitív egész szám a \(\displaystyle B\) halmazból. A program standard kimenete a képzett sorozatban előforduló \(\displaystyle B\)-beli számok maximális száma.

Korlátok: \(\displaystyle 2 \le P \le 100\), \(\displaystyle 2 \le N \le 10^6\), a \(\displaystyle B\) halmaz minden eleme \(\displaystyle \le 10^9\).

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb \(\displaystyle P\) és \(\displaystyle N\) érték esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy s122.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.

(10 pont)

megoldás, statisztika