Informatika gyűjtemény

NézetNyomtat

Zászló (Megoldás)
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2009 > Második forduló > 11-13. osztály

Algoritmus

Röviden: fontos, hogy tároljuk az előző sort, hogy össze tudjuk vetni az adott sorral, ezt két pufferrel valósítjuk meg: egyikből olvasunk, másikba írunk, majd a sor vizsgálatánál váltunk (a jelenlegi sorból lesz az "előző"). Nyomon kell azt is követni, hogy volt-e egyezés, és ha igen, akkor melyik pozíciótól kezdődően. Egy adott sor vizsgálatánál, fontos, hogy különbözik-e a két karakter:
  • Ha igen: Ha eddig mindig volt egyezés, akkor megjegyezzük, hogy melyik pozíciótól kezdődően van eltérés. Ha még mindig nincs egyezés, akkor megint két ágra bomlunk: új karakterben különbözik, vagy még mindig ugyan az a karakter: első esetben bezárjuk az eddigi differenciát, és újat kezdünk, másik esetben folytatjuk.
  • Ha nem: Ha eddig mindig volt egyezés, akkor jók vagyunk, ha nem, akkor most vége van egy differenciának, tehát ezt el kell tárolni.
{ VÁLTOZÓK }
char[] prevLine[] := feltöltjük nem színt jelentő karakterrel, mondjuk '0'-val. {előző sor}
char[] curLine[] {jelenlegi sort tartalmazza -- figyelem nem úgy ahogy a bemenetben, itt már szóközök nélkül!}
int start := -1 {a differencia kezdetét tároljuk benne}
char ch {az új karaktert tároljuk}
{ VÁLTOZÓK VÉGE }

Ciklus j:=1-től N-ig
    curLine := beolvas() {beolvassunk egy adott sort a képből}
    start := -1
    Ciklus i:=1-től M-ig
        Ha curLine[i] != prevLine[i] Akkor
            Ha start = -1 Akkor {eddig nem volt differencia}
                start := i {itt kezdődik!}
                ch := curLine[i] {elmentjük a karaktert}
            Különben
                {egy differencián belül vagyunk, kérdés, hogy még mindig ugyan az a karakter vagy új?}
                Ha ch != curLine[i] Akkor
                    {ebben a sorban [start,i-1] intervallumban, ch-val különbözik}
                    ujDifferencia( j, start, i-1, ch );
                    start := i {új differenciát kezdünk}
                    ch := curLine[i] {új karakter}
                Elágazás vége
            Elágazás vége
        Különben Ha start != -1 Akkor
            {megint egyezés van, de eddig különbözött}
            ujDifferencia( j, start, i-1, ch )
            start := -1 {egyezés van, nincs differencia!}
        Elágazás vége
        prevLine := curLine {puffer csere}
    Ciklus vége
    Ha start != -1 Akkor
        {sor végén járunk, de egy differenciát elkezdtünk, zárjuk be!}
        ujDifferencia( j, start, M, ch ) {start-tól a sor végéig (M-ig)}
    Elágazás vége
Ciklus vége
Nincs más dolgunk a végén mint az ujDifferencia(sor, tol, ig, karakter) függvény által kapott sor, pozíciótól, pozícióig, karakter adatokat kiírjuk a fájlba.

Megoldások

Kriván Bálint (C#): kb_zaszlo.cs