Az S. 1. feladat értékelése és megoldása

S. 1. Írjunk programot, amely tizedestörteket közönséges törtekké alakít. A program olvassa be a tizedestörteket; minden egyes sor legfeljebb tizennégy számjegyet és egy tizedespontot tartalmaz. (A bemenő adatok mindig helyesek lesznek, az ellenőrzéstől eltekinthetünk.) Minden egyes sorhoz keresse meg a lehető legkisebb nemnegatív a és pozitív b számokat, amelyekre az \(\displaystyle \frac{a}{b}\) szám tizedestört alakjának eleje (kerekítés nélkül) megegyezik a megadott sorozattal és írja ki az \(\displaystyle \frac{a}{b}\) törtet.

Példa:

0
1.01
1.010
1.0100
3.14
3.1415926535897

0/1
52/51
92/91
101/100
22/7
20530996/6535219

A programokat különböző méretű - legfeljebb hat-, tíz, illetve tizennégy számjegyből álló - adatokon fogjuk tesztelni. A maximális pontszám eléréséhez a programnak a legnagyobb adatokon is gyorsan (legfeljebb néhány perc alatt) le kell futnia. Akinek a programja csak a hat- vagy tízjegyű adatokra fut le adott idő alatt, az 6, illetve 8 pontot kaphat.

(10 pont)

A beérkezett dolgozatok típushibái

A feladat meglepően nehéznek bizonyult, a maximális 10 pontot senkinek sem sikerült elérni. Nem akadt ugyanis olyan program, amely a 14-jegyű adatokra is lefutott volna, és a legtöbb megoldás a kisebb adatokra is gyakran hibás eredményeket adott. Mielőtt a megoldást bemutatnánk, szeretnénk rámutatni a beküldött dolgozatok típushibáira és a feladat tanulságaira.

Formai hibák és hiányosságok

A legtöbb munka súlyos formai hiányosságokat tartalmazott. Ezek mögött feltehetően az áll, hogy a versenyzők sem a feladat szövegét, sem a versenykiírást nem olvasták el elég figyelmesen.

A feladat szövegéből egyértelműen kiderül, hogy a programnak nem egy, hanem több tizedestörtet kell feldolgoznia, amiket az input sorai tartalmaznak, a program kimenetére pedig csak a végeredményeket kértük. Ezzel szemben a beküldött programok túlnyomó többsége csupán az első sort olvasta el és különböző egyéb szövegeket írt a képernyőre.

A tesztelést igyekeztünk automatizálni; a programokat több, előre elkészített adatsorozaton próbáltuk ki, az eredmények helyességét is egy külön programmal ellenőriztük. A formai hibák ezt megnehezítették, a beküldött dolgozatokat szinte kivétel nélkül módosítanunk kellett, hogy a feltételeknek megfeleljenek.

A másik gyakori formai hiányosság a dokumentáció és a feladatbeli megjegyzések kisebb-nagyobb - vagy éppen teljes - hiánya. Pedig a versenykiírás elég világosan fogalmaz:

,,A maximális pontszám eléréséhez nem elég csupán egy működő programot beküldeni. A programokat el kell látni - ésszerű mennyiségű - megjegyzéssel, amelyekből a javítók könnyen megérthetik a programok működését. Bonyolultabb algoritmusok esetén az algoritmust külön fájlban, legfeljebb két-három oldalon kérjük.''

A legtöbb beküldött program algoritmusa elég egyszerű volt, a leírása nem igényelt (volna) külön fájlt. Elég lett volna odaírni megjegyzésként a program elejére vagy a keresés elé, hogy ,,végigpróbálgatjuk a lehetséges nevezőket.'' Sokszor még ez is hiányzott.

Az is gyakran előfordult, hogy a szerző megjegyzéseket írt a program apró részleteihez, de a fontosabb változók tartalmáról vagy az egyes eljárások céljáról és működéséről nem írt semmit. Ez azt mutatja, hogy a versenyzők egy része nincs tisztában a programbeli megjegyzések céljával. A megjegyzéseket azért tesszük bele a programba, hogy ha valak más - vagy éppen néhány hónap múlva mi magunk - el akarja olvasni a programot, akkor könnyen megértse a működését. (Mindenki kipróbálhatja, hogy megérti-e a néhány hónappal korábban írt programját.)

Több esetben hiányzott a fejléc (feladat, név, osztály, város, iskola, e-mail cím). A következő hónaptól kezdve az ilyen megoldásokat "nem versenyszerűnek" fogjuk értékelni függetlenül attól, hogy működnek-e.

A számábrázolások megválasztása

A feladat megoldása nagy pontosságú számításokat igényel. A feldolgozandó tizedestört akár 14 értékes jegyet tartalmazhatott, és emiatt az outputban is előfordultak 14-jegyű számok. A típusok megválasztásához figyelembe kell vennünk, hogy 14 értékes jegy ábrázolásához legalább 47, előjeles számok esetén legalább 48 bit szükséges. Amennyiben ekkora számok szorzata is előfordul a kódban, a szükséges méret megduplázódik.

Rosszul megválasztott típusok esetén a kívánt pontosságot nem tudjuk elérni, az egész típusok pedig túlcsordulhatnak. Ennek ellenére több program használt túlságosan kicsi, 32-bites egészeket és 6-bájtos lebegőpontos számokat.

Lebegőpontos számítások és kerekítési hibák

Nagyon sok program használt lebegőpontos számokat; például a tizedes tört által meghatározott intervallum végpontjait lebegőpontos számként tárolták. Ez kerekítési hibákhoz, a kerekítési hibák pedig hibás döntésekhez vezetnek. Ha két érték túlságosan közel van egymáshoz (túl sok értékes jegyben megegyeznek), az összehasonlítás téves eredményt adhat.

A kerekítési hibák miatt szinte mindegyik program produkált hibás eredményeket. Sokszor még a feladatban megadott mintákra is hibás eredményt kaptunk.

Több versenyző úgy próbálta a kerekítésből származó hibákat elkerülni, hogy az összehasonlításoknál a megfelelő oldalt egy kis értékkel módosította, valahogy így:

if a<b*t+epszilon then ...

Azokban az esetekben, amikor elméletileg egyenlőség állna fenn, de a kerekítési hibák miatt b*t értéke mégis kisebb lett a-nál, ilyen módon elkerülhető, hogy az összehasonlítás hibás eredményt adjon.

A versenyzők az epszilon értékét 10^-15 körülinek választották, ami látszólag megfelel az elvárt pontosságnak. Sajnos azonban a legfeljebb 10¹⁴ nevezőjű törtek nagyjából 10^-28 távolságra vannak egymástól, ezért ez a pontosság kevés, a módosított összehasonlítás más esetekben ad téves eredményt.

Ha az epszilon értékét sokkal kisebbnek, 10^-28 körülinek választjuk - és mindenhol legalább 28 értékes jeggyel számolunk -, akkor a hibák elkerülhetők.

Az algoritmusok hatékonysága

A legtöbb program a lehetséges nevezőket (1,2,3,...) próbálgatta sorban, amíg nem talált valamelyikhez megfelelő számlálót. (Más programok a számlálókat próbálgatták, ami majdnem ugyanaz.) A legfeljebb 10-jegyű adatokra ez még le is futhat néhány perc alatt, mert a nevező nem lesz nagyobb, mint tízmilliárd. A 14-jegyű adatok esetében az ilyen keresés már minden esetben túl lassú volt; voltak ugyanis olyan tesztadataink, amiknél a végeredmény számlálója és nevezője is 14-jegyű volt.

Volt néhány program, ami a 0/1 törtből kiindulva minden lépésben 1-gyel növelte a számlálót vagy a nevezőt attól föggően, hogy az aktuális tört túl éppen kicsi vagy túl nagy volt. Ezeket a programokat lehetett volna egy kicsit javítani azzal, hogy egyesével növelés helyett minden esetben kiszámítjuk a legkisebb szóba jövő számlálót, illetve nevezőt, de ez sem növelte volna minden esetben a hatékonyságot. Például a 0.999..99 alakú számokra a javított algoritmus is felváltva növeli egyesével a számlálót és a nevezőt.

A beérkezett dolgozatok tehát kivétel nélkül exponenciális ideig futottak; n-jegyű inputból kiindulva a lépésszám legrosszabb esetben kb. 10ⁿ volt. Mivel a tízjegyű inputokra még lefuthattak (volna), megfelelő számábrázolásokkal, a kerekítési hibák elkerülésével és elegendő dokumentációval legfeljebb 8 pontot lehetett kapni rájuk.

Egy lehetséges megoldás

Most egy lehetséges megoldást mutatunk be két változatban, C++ nyelven.

Számábrázolások

Az egész számok ábrázolására az int64_t típust fogjuk használni, amely, mint neve is mutatja, egész számokat tárol 64 biten. A lebegőpontos számok helyett közönséges törteket, azaz számlálót és nevezőt fogunk használni.

Az inputként kapott törtet is p/q alakba írjuk át, ahol a q nevező a 10 hatványa, a kitevője a tizedespont utáni jegyek száma. Például \(\displaystyle {\tt0}=\frac01\), \(\displaystyle {\tt3.14}=\frac{314}{100}\). A feladat ezután a legkisebb olyan a/b tört megkeresése, amire teljesül, hogy

Rekurzív keresés lánctörtekkel

A keresési algoritmusunk alapötlete, hogy a feladatot egy ,,kisebb'' keresési feladatra vezetjük vissza és azt oldjuk meg. Az új feladat attól lesz kisebb, hogy az előforduló számok kisebbek. A kisebb feladatot azután visszavezetjük egy még kisebbre egészen addig, amíg végül triviális lesz.

A feladat minden esetben a legkisebb tört megkeresése egy intervallumban. Az intervallum csupa pozitív számot tartalmaz, az egyik végén zárt, a másik végén nyílt. Előfordulhat az is, hogy az intervallum nyílt végpontja a 0 vagy a +\(\displaystyle \infty\).

A feladatot a következőképpen oldjuk meg. Ha az intervallumban van legalább egy egész szám, akkor a feladat triviális; a legkisebb ilyen egész szám a megoldás. Ha az intervallumban nincs egész szám, akkor minden elemének ugyanaz az egész része; jelöljük ezt e-vel. Az intervallumot toljuk el (-e)-vel, majd vegyük minden elemének a reciprokát. Az így kapott új intervallumban keressük meg a legkisebb számlálójú és nevezőjű törtet, vegyük ennek a reciprokát, végül adjunk hozzá e-t.

Nézzük meg az algoritmus működését egy konkrét példán, a 3.141 inputon. A kezdeti feladat a legkisebb számlálójú és nevezőjű tört - jelöljük x₁-gyel - keresése a \(\displaystyle \left[\displaystyle\frac{3141}{1000};\displaystyle\frac{3142}{1000}\right)\) intervallumban.

Az intervallumban nincs egész szám, és minden elemének 3 az egész része. A megoldást ezért \(\displaystyle x_1=3+\displaystyle\frac1{x_2}\) alakban keressük, ahol x₂ a legkisebb számlálójú és nevezőjű tört a \(\displaystyle \left(\displaystyle\frac{1000}{142};\displaystyle\frac{1000}{141}\right]\) intervallumban.

A \(\displaystyle \left(\displaystyle\frac{1000}{142};\displaystyle\frac{1000}{141}\right]\) intervallumban nincs egész szám és mindegyik elem egész része 7. Az x₂ szám tehát \(\displaystyle x_2=7+\displaystyle\frac1{x_3}\) alakú, \(\displaystyle x_3\in\left[\displaystyle\frac{141}{13};\displaystyle\frac{142}6\right)\).

A \(\displaystyle \left[\displaystyle\frac{141}{13};\displaystyle\frac{142}6\right)\) intervallum több egész számot is tartalmaz, ezek közül a legkisebb a 11. Így tehát \(\displaystyle x_3=\displaystyle\frac{11}1\), \(\displaystyle x_2=7+\displaystyle\frac1{11}=\displaystyle\frac{78}{11}\) és \(\displaystyle x_1=3+\displaystyle\frac{11}{78}=\displaystyle\frac{245}{78}\).

A bemutatott algoritmus valójában felírja az intervallum két végpontjának lánctört alakját egészen addig a pontig, ahol különböznek, ott beír egy megfelelő egész számot és elvágja. A példában a kiinduló törtek lánctört alakja:

\(\displaystyle \displaystyle\frac{3141}{1000}=3+\displaystyle\frac1{7+\displaystyle\frac1{10+\displaystyle\frac1{1+\displaystyle\frac1{5+\displaystyle\frac15}}}}, \qquad\displaystyle\frac{3142}{1000}=3+\displaystyle\frac1{7+\displaystyle\frac1{23+\displaystyle\frac1{1+\displaystyle\frac12}}}; \)

a megoldás pedig

\(\displaystyle \displaystyle\frac{245}{78}=3+\displaystyle\frac1{7+\displaystyle\frac1{11}}.\)

A lépések száma legfeljebb akkora, mint a lánctörtek hossza. Ismeretes, hogy egy tetszőleges \(\displaystyle \frac{a}{b}\) szám lánctört alakjának hossza legfeljebb \(\displaystyle \log_{\frac{1+\sqrt5}2}b+2\), ami 14-jegyű számok esetében kevesebb, mint 70. (Természetesen ennél valamivel gyengébb becslés is elég. Például nem nehéz igazolni, hogy a számláló és a nevező mindig legfeljebb feleakkora, mint két lépéssel korábban, és a lépések száma 100-nál kisebb.)

A kereső algoritmust egy olyan függvényként valósítjuk meg, amely a nemtriviális esetekben felírja a redukált feladatot és meghívja saját magát - ezt hívjuk rekurziónak - a redukált feladat megoldására. Mint láttuk, a rekurzió mélysége biztosan kisebb, mint 70, tehát nem kell veremtúlcsordulástól tartanunk.

A függvénynek összesen 5 bemenő paramétere lesz: az intervallum két végpontja tört alakban (ez tehát 2x2=4 egész szám, és annak jelzése, hogy az intervallum balról vagy jobbról zárt. A két kimenő paraméter a legkisebb lehetséges számláló és nevező.

Keresés rekurzió nélkül

A keresést rekurzió nélkül is meg lehet valósítani; a megoldás így ugyan kevésbé lesz elegáns, de nem szükséges a veremtúlcsordulás veszélyével foglalkoznunk.

Ezúttal is, minden egyes lépésben lesz egy intervallumunk (ugyanaz, mint az előbb), és egy függvényünk, ami megmondja, hogy hogyan kell az intervallumba eső legkisebb számlálójú és nevezőjű törtből kiszámítani az eredeti feladat megoldását. A feladat redukálásakor az új intervallumot és a hozzá tartozó függvényt is felírjuk; ezután az előző értékeket eldobjuk és az új feladattal foglalkozunk tovább. Ezt addig ismételgetjük, amíg a feladat triviális nem lesz.

Az n-edik feladat megoldását jelöljük most \(\displaystyle \displaystyle\frac{a_n}{b_n}\)-nel. Az eredeti feladat megoldását két lineáris kifejezés fogja megadni: a₁=A_na_n+B_nb_n, b₁=C_na_n+D_nb_n, ahol A_n,B_n,C_n,D_n alkalmas egész számok. A kezdeti feladatban természetesen A₁=1, B₁=0, C₁=0 és D₁=1.

Az aktuális intervallum leírásához ugyanúgy öt változóra lesz szükségünk: a végpontok számlálójára és nevezőjére, valamint arra, hogy az intervallum melyik oldalról zárt.

Működő C++ kód

Az alábbi C++ programban mindkét algoritmust megvalósítottuk. A REKURZIV makró értékével lehet megadni, hogy a rekurzív vagy a nem rekurzív algoritmust szeretnénk.

A programot Linux alatt, GCC 3.3.1 fordítóval teszteltük.

// S. 1.
// Mekk Elek 12. o. t..
// Nekeresd, Ezermesterképző Intézet
// kaposzta@nekeresd.hu

#include <iostream>
#include <string>
#include <stdint.h>

#define REKURZIV 1   // 1=rekurzív, 0=nem rekurzív

//-------------------------------------------------------------------------

// Tizedestört átírása p/q alakúra. A nevező mindig 10-hatvány, a
// kitevője a tizedespont utáni jegyek száma. A tizedestörtet a
// "ttort" stringben kapjuk, az eredményt a "szamlalo" és "nevezo"
// nevű változókba írjuk. A visszatérési érték true, ha az átalakítás
// sikerült.
bool TizedesbolTort( const std::string &ttort, int64_t &szamlalo, int64_t &nevezo )
{
  bool volt_tpont = false;   // Volt-e már tizedespont?
  bool volt_szjegy = false;  // Volt-e már számjegy?
  szamlalo = 0;
  nevezo   = 1;
  for (std::string::const_iterator i = ttort.begin(); i!=ttort.end(); ++i)
  {
    if (*i=='.' || *i==',')               // Tizedespontot/vesszőt találtunk
    {
      if (volt_tpont) return false;       // Két tizedespont nem lehet
      volt_tpont = true;
    }
    else if (*i>='0' && *i<='9')          // Számjegy, az értéke *i-'0'
    {
      szamlalo = 10 * szamlalo + *i - '0';
      if (volt_tpont) nevezo *= 10;
      volt_szjegy = true;
    }
    else
    {
      return false;                       // valami mást találtunk (hiba)
    }
  }

  // Akkor sikerült az átalakítás, ha volt legalább egy számjegy
  return volt_szjegy;
}

//-------------------------------------------------------------------------

// A legkisebb tört keresése rekurzív módon egy félig nyílt
// intervallumban. Az intervallum végpontjai p/q és r/s, Ha bzart
// értéke igaz, akkor az intervallum balról zárt, jobbról nyílt. Ha
// bzart értéke hamis, akkor balról nyílt és jobbról zárt. Az eredmény
// számlálóját és nevezőjét az a, illetve b változókba írjuk.
// Megengedjük a p=0 és s=0 eseteket is, ilyenkor az alsó végpont 0,
// illetve a felső végpont végtelen.
void RekurzivKereses( int64_t p, int64_t q,
                      int64_t r, int64_t s, bool bzart,
                      int64_t &a, int64_t &b )
{
  // Kiszámítjuk a/b egész részét (e), és a legkisebb olyan egészt
  // (f), ami p/q-nál nagyobb (vagy egyenlő, ha bzart=igaz); ez
  // legfeljebb 1-gyel nagyobb, mint e.
  int64_t e = p / q;
  int64_t f = (q*e<p || (q*e==p && !bzart)) ? e+1 : e;

  // Ha az f benne van az intervallumban, akkor a feladat triviális,
  // az eredmény f/1.
  if (s*f<r || (s*f==r && !bzart))
  {
    a = f; b = 1;
    return;
  }

  // Az eredményt e+u/v alakban keressük. Ehhez a v/u törtet kell
  // megtalálnunk. Az intervallumot eltoljuk (-e)-vel és vesszük
  // mindennek a reciprokát. Az így kapott intervallumban kell lennie
  // v/u-nak.
  int64_t u,v;

  // Az eltolt intervallum végpontjai: (p-e*q)/q, (r-e*s)/s. A
  // reciprok intervallumé s/(r-e*s), q/(p-e*q). A reciprok
  // intervallum az ellenkező végén zárt.
  RekurzivKereses( s, r-e*s, q, p-e*q, !bzart, v, u );

  // A végeredmény (u+e*v)/v
  a = u+e*v; b = v;
}

//-------------------------------------------------------------------------

// A legkisebb tört keresése rekurzíó nélkül.
void NemRekurzivKereses( int64_t p, int64_t q,
                         int64_t r, int64_t s,
                         int64_t &a, int64_t &b )
{
  // A törtet a kjövetkező alakban keressük: a = Au+Bv, b = Cu + Bv,
  // ahol A,B,C,D nemnegatív egészek lesznek, u/v pedig a legkisebb
  // számlálójú/nevezőjű tört egy intervallumban. Az intervallum
  // végpontjai P/Q és R/S; ha bzart=true, akkor balról zárt,
  // ellenkező esetben jobbról zárt.

  int64_t A=1, B=0, C=0, D=1;   // kezdetben a=u, b=v,
  int64_t P=p, Q=q, R=r, S=s;   // az intervallum pedig az eredeti intervallum,
  bool bzart = true;            // ami balról zárt.

  while (1) // addig keresünk, amíg meg nem találjuk...
  {
    // Kiszámítjuk a/b egész részét (e), és a legkisebb olyan egészt
    // (f), ami P/Q-nál nagyobb (vagy egyenlő, ha bzart=igaz); ez
    // legfeljebb 1-gyel nagyobb, mint e.
    int64_t e = P / Q;
    int64_t f = (Q*e<P || (Q*e==P && !bzart)) ? e+1 : e;

    // Ha az f benne van az intervallumban, akkor az eredmény triviálisan f/1
    if (S*f<R || (R*f==S && !bzart))
    {
      // Behelyettesítjük az u = f, v = 1 értékeket
      a = A*f+B; b = C*f+D;
      return;
    }

    // Az intervallumot eltoljuk (-e)-vel és vesszük a reciprokát,
    int64_t P1=S, Q1=R-e*S, R1=Q, S1=P-e*Q;  // az új intervallum végpontjai
    
    // Ha az új intervallumba eső, legkisebb számlálójú/nevezőjű tört x/y, akkor
    // u/v = e+y/x, azaz u=e*x+y és v=x, továbbá
    int64_t A1=A*e+B, B1 = A;  // a = A*u+B*v = A*(e*x+y)+B*x = (A*e+B)*x+A*y és
    int64_t C1=C*e+D, D1 = C;  // b = C*u+D*v = C*(e*x+y)+D*x = (C*e+D)*x+C*y

    // A régi feladatot eldobjuk és az újat tesszük a helyére
    A = A1; B = B1; C = C1; D = D1;
    P = P1; Q = Q1; R = R1; S = S1;
    bzart = !bzart; // Az új intervallum az ellenkező végén zárt
  }
}

//-------------------------------------------------------------------------

int main()
{
  std::string ttort;
  int64_t a,b,p,q;
  while ( std::cin >> ttort )  // Amíg csak sikerül olvasni valamit
  {
    if ( TizedesbolTort( ttort, p, q ) )  // konverzió
    {
#if REKURZIV
      // A törtet a p/q, (p+1)/q számok között keressük, az
      // intervallum balról zárt
      RekurzivKereses( p, q, p+1, q, true, a, b );
#else
      // A törtet a p/q, (p+1)/q számok között keressük
      NemRekurzivKereses( p, q, p+1, q, a, b );
#endif
      // Kiírjuk a végeredményt
      std::cout << a << "/" << b << std::endl;
    }
    else
    {
      // Nem sikerült a konverzió
      std::cout << "Hibás adat" << std::endl;
    }
  }
  return 0;
}