Az S. 164. feladat (2022. október) |
S. 164. A fordítóprogramok nagyon alacsony szinten átrendezhetik a forrásprogramban kiszámítandó kifejezésben az elvégzendő műveletek sorrendjét azért, hogy időt vagy memóriát spóroljanak. Ez sokat javíthat egy programon, de nem változtathatja meg annak jelentését. Ebben a feladatban egy egyszerű számítás memóriaigényét próbáljuk csökkenteni.
Adott egy csak változókat, valamint összeadás és szorzás műveleteket tartalmazó kifejezés. Az egyszerűség kedvéért fordított lengyel jelölést használunk. Például az \(\displaystyle (a+b)*c\) kifejezés lengyel formában \(\displaystyle ab+c*{}\) lesz. Ennek előnye, hogy a számítógép ezt balról jobbra haladva egyszerűen végre tudja hajtani. Kezdetben az összes változó értéke bent van a memóriában, mindegyik egy egységnyi tárhelyet foglal el. Egy matematikai művelet végrehajtása után az eredmény egy új (egységnyi) memóriaterületre kerül. Az előző példában \(\displaystyle x=a+b\), \(\displaystyle y=x*c\). A program így 5 egységnyi memóriát használ, kezdetben \(\displaystyle a\), \(\displaystyle b\) és \(\displaystyle c\) értékének, majd \(\displaystyle x\) és \(\displaystyle y\) tárolására.
A kifejezés kiértékelése javítható, ha a később már nem használt (egységnyi) memóriaterületeket minden lehetséges alkalommal felülírjuk. A példa egy lehetséges végrehajtása ezzel a javítással: \(\displaystyle a=a+b\), \(\displaystyle b=a*c\). A program így 3 egységnyi memóriát használ a kezdeti változók miatt. (Nem számít, hogy az eredmény végül melyik változóba kerül.)
Készítsünk programot, amely egy lengyelformában adott kifejezés esetén megadja, hogy hány egységnyi tárhely szükséges a kifejezés kiértékeléséhez az eredeti és az optimalizált módszer felhasználásával.
A bemenet első és egyetlen sora egy számítást tartalmaz a fordított lengyel jelölés szerint. Ennek minden karaktere az angol abc egy kisbetűje, illetve a ,,+'' és ,,*'' karakter lehet.
A kimenet első sorába a számolás optimalizáció nélküli, a második sorába az optimalizáció utáni memóriaigényét kell írni.
Minta:
Bemenet | Kimenet (a / jel sortörést helyettesít) |
ab+bc+*ca+* | 8 / 4 |
Időlimit: 0,5 mp.
Értékelés: a pontok 20%-a kapható, ha a megoldás a kimenet első sorát helyesen határozza meg.
Beküldendő egy s164.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.
(10 pont)
A beküldési határidő 2022. november 15-én LEJÁRT.
Statisztika:
4 dolgozat érkezett. 9 pontot kapott: Horváth Milán. 2 pontot kapott: 3 versenyző.
A KöMaL 2022. októberi informatika feladatai