 |
Az I. 168. feladat (2007. október) |
I. 168. Egy téglalap alakú teremben három ,,drót nélküli'' (WiFi) jeladót helyeztünk el, ezek segítségével szeretnénk az ott dolgozó munkatársak számítógépeit hálózatba kötni. Tételezzük föl, hogy a jeladók erőssége a jeladótól vett távolsággal négyzetes arányban csökken, és a dolgozók számítógépe automatikusan ahhoz a jeladóhoz kapcsolódik, amelyiktől a legerősebb jelet érzékeli. Az egyszerűség kedvéért a terem mindig lefedhető 1 méter oldalhosszúságú négyzetekkel. A jeladók és a számítógépek mindegyike valamelyik így kapott mező belsejében van. Bármely két mező közötti távolságot úgy kapjuk meg, hogy megszámoljuk, legkevesebb hány mező érintésével lehet egyikből a másikba eljutni. Egy mező így önmagától 1 távolságra van. Az így kiszámított jelerősséget egész számra kerekítjük.
Például egy 4.3 négyzetméteres helyiségben, a (4;3) mezőben elhelyezett 90-es jelerősségű adó, az (1;1) mezőben levő 70-es jelerősségű adó, és az (1;3) mezőben levő 60-as jelerősségű adó esetén az alábbi ,,lefedettségi'' táblázatot kapjuk:
Azaz a (4;3)-as mezőn belül a jelerősség 90, mivel a távolság itt 1 egység. A vele szomszédos mezőkben (mivel azok távolsága tőle 2 egység) a jelerősség , ami kerekítve 23.
Készítsünk programot, amely tetszőleges, legfeljebb 25×25-ös teremre elkészíti a fenti táblázatot. A program a felhasználótól kérje be a terem méreteit, majd a három sugárzó koordinátáit és jelerősségeit. Az elkészült táblázatban minden szám egészre kerekítve, 3 karakter helyen jelenjen meg, és azt a program írja soronként a standard kimenetre.
Beküldendő a program forráskódja (i168.pas, i168.cpp, ...), a megoldás rövid dokumentációja (i168.txt, i168.pdf, ...) valamint a megoldáskor alkalmazott fordítóprogram neve és verziószáma (pl. Free Pascal 2.0, Borland C++ 3.1, ...).
(10 pont)
A beküldési határidő 2007. november 15-én LEJÁRT.
Megoldás
Englert Péter (11. osztály, Zalaegerszeg, Zrínyi M. Gimn.) munkája Pascal nyelven:
C++ nyelven készült mintamegoldás:
Külön szeretnénk felhívni a figyelmet a mintamegoldásra, amely sehol sem használ lebegőpontos értékeket vagy kerekítést.
Típushibák, tanulságok
A feladat a könnyebbek közé tartozott, három jellegzetes hiba legalább egyikét azonban mégis sokan elkövettétek.
Az első két hiba szinte kizárólag együtt fordult elő. Sok megoldás nem kezelte helyesen, ha egy mezőn lévő jeladó gyengébb volt, mint egy máshonnan odaérkező jel, illetve ha egy mezőn több jeladó is volt. Ahogy sokan jól észrevették, ezen úgy lehetett segíteni, hogy a jeladó(ka)t tartalmazó mezőket ugyanúgy kezeltük, mint minden más mezőt, és ugyanúgy vettük rá a 3 jeladó pontbeli erősségének maximumát, ahogy a többi mezőre is. (Ezért is volt egy mező önmagától 1 távolságra.)
Adódott probléma az osztás-kerekítés elvégzésével is. Ez abból adódott, hogy egyes nyelvek (C#), ill. fordítók (Free Pascal) kerekítésre alapesetben nem a szokványos ("away from zero") eljárást alkalmazzák, hanem a kerekítési hiba mérséklése érdekében a félúton lévő számokat a legközelebbi páros számra kerekítik ("to even"). Így pl. Turbo Pascalban round(12.5)=13 , de Free Pascalban 12.
A probléma ugyanakkor roppant elegánsan megoldható kizárólag egészekkel és maradékos osztással (div), mégpedig egészen egyszerűen úgy, hogy az osztandóhoz hozzáadjuk az osztó felét, majd ezt az összeget osztjuk. Így nyelvtől és platformtól függetlenül mindig helyes eredményt kapunk.
A feladatspecifikációban szereplő korlátokról
A feladatok szövegében gyakran találkozunk a bemenetre vonatkozó megszorításokkal, korlátokkal: pl. "N egész, (0<N
50000)", "legfeljebb 25×25-ös táblázat", "3 darab szóközzel elválasztott egész szám".
Rendkívül fontos azonban megérteni, hogy ezek a feltételek nem a programmal, hanem a felhasználóval szemben támasztanak bizonyos elvárásokat.
Gyakran találkozunk azzal a helytelen értelmezéssel, hogy - a fenti példánál maradva - a kód N értékét beolvasva azt összeveti a határokkal; ellenőrzi, hogy a terem szélessége és magassága 1 és 25 közé esik-e; a sorban valóban 3 szám szerepel-e, stb. Az ilyesfajta ellenőrzések akár több tíz, esetleg száz sor terjedelműek is lehetnek, jelentősen megnövelve a megoldás elkészítéséhez szükséges időt.
Örömmel jelenthetjük, hogy az ilyesfajta vizsgálódás nemcsak nem kötelező, hanem teljes mértékben felesleges. Attól a pillanattól kezdve ugyanis, hogy feladatspecifikációban rögzítettük a bemenetre vonatkozó korlátokat, minden ettől eltérő bemenet következményéért (rossz eredmény, végtelen ciklus...) a felhasználó felel. A specifikációt egyfajta szerződésként képzelhetjük el a program és a környezete közt: kizárólag az abban rögzített feltételek teljesülése esetén tudjuk garantálni a program helyes működését.
Természetesen komoly programoknál az első bekezdésben leírtakhoz hasonló kikötések nem szerepelhetnek a specifikációban, ott szinte kötelező, hogy a bemenet helyességét, értelmességét ellenőrizzük, a program "bolondbiztos" legyen. Ez általában rengeteg monoton, unalmas többletmunkát és -kódot eredményez.
A feladatszövegekben szereplő korlátokkal épp ettől a munkától szeretnénk megkímélni titeket, annak érdekében, hogy minden erőtökkel a feladat érdemi, kihívást jelentő, "szép" részére koncentrálhassatok. Ennek értelmében a megoldások tesztelése során mindig igazodni fogunk a specifikációhoz, így e feltételek teljesülését a program írása során tényként kezelhetitek.
A feladatkiírásban szereplő megkötések tehát - a fenti példáknál maradva - helyesen a következőképp értelmezendők:
- N biztosan egy pozitív, 50000-nél nem nagyobb egész szám, tehát nyugodtan beolvashatom egy előjel nélküli, 16 bites egész változóba, nem fog túlcsordulni. Nyugodtan oszthatok vele, nem fordulhat elő 0-val osztás.
- A táblázat számára egy fix méretű 25x25-ös tömböt foglalok, és az értékeket ebbe fogom beolvasni, legfeljebb nem használom a teljes táblázatot. A tömb túlindexelése nem fordulhat elő.
- A sor biztosan 3 darab egész számot fog tartalmazni legalább 1 szóközzel elválasztva, így formázott beolvasás esetén a 3 egész számot váró scanf/readln hívás biztosan sikeres lesz.
Ugyanakkor szeretnénk arra is felhívni figyelmeteket, hogy a specifikációt a másik oldalról is ugyanilyen szigorúan vesszük: biztosak lehettek benne, hogy a megoldásokat olyan tesztadatokkal is fogjuk ellenőrizni, melyben N értéke 1 vagy 50000; a táblázat mérete 1x1, 1x25 vagy 25x25. A teljes pontszám eléréséhez a programnak ezekben az esetekben is jól kell működnie.
Statisztika:
19 dolgozat érkezett. 10 pontot kapott: Englert Péter, Fábián András, Hodosy Gábor, Horváth 135 Loránd, Kaposvári Tamás, Pap 987 Dávid, Póta Kristóf, Szpisják Dániel, Véges Márton. 9 pontot kapott: Erdős Gergely, Szabó 313 Gábor. 8 pontot kapott: 1 versenyző. 7 pontot kapott: 2 versenyző. 6 pontot kapott: 2 versenyző. 5 pontot kapott: 1 versenyző. 4 pontot kapott: 1 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2007. októberi informatika feladatai