Raigedas
Sausis 10, 2007

Skaldyk ir valdyk!

Pagautas įkvėpimo parašiau šį straipsnį, pamačiau kaip sesė kankinosi su keletu informatikos užduočių. Vienos užduoties sprendimas tai man ypatingai nepatiko…

Užduotis skamba taip:
“Duotas laikas, saugomas kintamuosiuose val, min, sek. Atspausdinti koks buvo laikas, viena sekunde atgal.”
Jums gal ir juokingas/lengvas atrodo uždavinys, bet įsivaizduokit save vėl dešimtoku ar dešimtoke! Tai va… kaip ji sprendė:

read(val);
read(min);
read(sek);
if sek>0 then begin
sek:=sek-1;
writeln(val, min, sek);
end;
if sek=0 then begin
sek:=59;
min:=min-1;
if min ...
...

Aš tiksliai negaliu prisiminti kaip ji rašė, bet esmę parodžiau. O ir visą sprendimą tingiu rašyti, nes jis man per sudėtingas :)
Na ką.. viskas lyg ir neblogai - sprendė tvarkingai (net lygiavimas yra!). Būtų išsprendus, būtų gavus 10. Sakau “būtų”, nes taip nebuvo - aš įsikišau, negalėjau žiūrėti į tokį sprendimą. Ar gali būti blogiau išspręsta? Na, tiesą sakant, gali būti dar šiek tiek blogiau. Pvz.:

read(sek);
if sek>0 then begin
sek:=sek-1;
read(min);
read(val);
writeln(val, min, sek);
end;
if sek=0 then begin
sek:=59;
read(min);
read(sek);
min:=min-1;
if min ...
...

Ar matot kur link lenkiu? Aš apie programos struktūrą. Skaldymą į logines dalis - čia viskas eina per vien.. Kur įvedimo dalis, apdorojimas, išvedimas? Bent jau… O apdorojimą galima būtų dar skaldyti. Gerai, einam pažingsniui. Po pirmo pertvarkymo mano siūlomas variantas būtų toks:

{ įvedimas }
read(val);
read(min);
read(sek);
 
{apdorojimas}
if sek>0 then begin
sek:=sek-1;
end;
if sek=0 then begin
sek:=59;
min:=min-1;
if min ...
...
 
{išvedimas }
writeln(val, min, sek);

Na va, jau geriau. Bet man norisi, kad būtų dar geriau… Iš tikrųjų, užduotį “rasti viena sekunde atgal” galima išskaldyti į du nepriklausomus žingsnius:

  • atimame tiek kiek nurodyta (net jei būtų liepta atimti 999 sekundes, tiek ir atimtume)
  • pertvarkome duomenis, kad jie atitiktų “laiko formatą” - kad nebūtų neigiamų skaičių.

Tai rezultate pilna programa atrodytų taip:

{----------įvedimas----------}
read(val);
read(min);
read(sek);
 
{---------apdorojimas---------}
 
{atimam kiek liepta}
sek := sek -1;
 
{ performatuojam}
if sek<0 then begin
sek:=sek+60;
min:=min-1;
end;
if min<0 then begin
min:=min+60;
val:=val-1;
end;
if val<0 then val:=val+24;
 
{---------išvedimas-----------}
writeln(val, min, sek);

Ką mes turim?

  • programą, kurią buvo lengviau parašyt (taip lengviau: nereikėjo rašyti šimtus ELSE IF… ir tikrinti ar tikrai kur nesuklydom, ko nepamiršom);
  • programa lengviau skaitoma;
  • lengviau koreguojama;
  • …sugalvokite patys :)

Taip, lengviau koreguojama. Pavyzdžiui, sakykim, turim šiek tiek pakoreguotą užduotį: ne 1 sekunde atgal o 5. Ką mes darom? Programoj (apie galutinį variantą kalbu) vienoj vietoj vienetą pakeičiame į penketą! Pirmam programos variante reikėtų keisti tikrai ne vieną vietą (keliose vietose “1″ į “5″; “59″ į “55″ ir t.t.).

Sakysit - taip, žinom mes tai, rašinėji kas ir taip savaime aišku! Čia atrodo kiekvienam aiškus šitas principas. Bet jei aiškus tada ir naudokit jį visada, nepamirškit jo, kai sprendžiat realius uždavinius!

Aš čia pateikiau tik vieną pritaikymą “skaldyk ir valdyk” principo. Naudodami klases (OOP) dar geriau išnaudosit šį principą. Nesakau, kad būtinai eikit ir visą savo procedūrinį kodą paverskit klasėm. Galit tiesiog logiškai susijusias projekto dalis (kodo gabalus) perkelti į atskirus failus (units).

Kai suprasit, kokią galią turi šis principas, galėsit jį naudoti ne tik programavime. Pvz., dar mokykloje turbūt Jus mokė, kad ilgus sakinius reikia skaldyt į keletą mažesnių… Na, teisingai pritaikius šį principą galima efektyviau dirbti:)

Panašūs straipsniai


“Skaldyk ir valdyk!” komentarų: 21

  1. enc

    čia aišku pseudo kodas, bet:

    read(val);
    read(min);
    read(sec);

    timestamp = 3600 * val + 60 * min + sec;
    past = timestamp - 1;

    nval = past div 3600;
    rest = past mod 3600;
    nmin = rest div 60;
    nsec = rest mod 60;

    writeln(nval, nmin, nsec);

    nori pasiginčyti apie efektyvumą? .)

  2. care

    o isivaizduok, kad tu prie uzdavinio jau niekada negrisi ir tokiu uzdaviniu per diena turi issprest koki 100… ne visada verta daryti tvarkingai, gerai. kartais galim paaukoti kokybes dali.

  3. Paulius

    Neblogas straipsnis.

    Mano manymu, dar lengviau ši užduotis išsisprendžia pavertus visą laiką sekundėm. Tuomet atimi kiek reikia sekundžių ir verti į normalų formatą.

    Reikės dviejų convert funkcijų ir viskas ;]

  4. pypt

    Na nežinau. Mano supratimu, nors programa ir paprasta, bet komentarų turėtų būti daugiau bei jie turėtų paaiškinti, *kodėl* kažkas yra daroma, o ne tik *kas* daroma.

    Jei prieš ~1000 eilučių bloką įkaltum vienintelį komentarą:

    { Apskaičiuojam rezultatą }

    …ir dar visai nenaudotum indentation’o, tai po pusės metų į ją žiūrėti ir (o siaube!) pabandyti kažką pakeisti būtų didžiulis asspain’as.

  5. U-toks

    Straipsnyje:
    “Na ką.. viskas lyg ir neblogai - sprendė tvarkingai (net lygiavimas yra!). Būtų išsprendus, būtų gavus 10. Sakau “būtų”, nes taip nebuvo - aš įsikišau, negalėjau žiūrėti į tokį sprendimą.”

    Tai užsiminei, bet kiek ir kodėl gavo nepasakei… Tai kaip ten buvo - mokyotjui toks sprendimas nepatiko?

  6. Rimantas

    Yra nuomonių, kad kodą reikia rašyti taip, kad jam nereikėtų komentarų: t.y. kodas turi būti savaime suprantamas.
    Ir, tiesą sakant, toks variantas:

    val:=val-1; {atimam vientą iš val}

    būtų idiotizmas, o ne programos pagerinimas.

  7. slapukasss

    Sutinku su enc būdu. Tokiu atveju nereikai trijų if’ų, kodo yra daug mažiau ir jis paprastai suprantamas. Pius kaip ten norėjo autorius norint atimti kitą skaičių reikia tik vienoj vietoj pakeisti skaičių. Arba galų gale galima taip pat read() kokį skaičių atimti.
    Pirmame būde nėra nei vieno “div” nei “mod”, o tai jau manau kokioje 9toje klasėje turėjo būti dėstoma.

    Peace

  8. Raigedas

    nenorėjau ir nenoriu su niekuo ginčytis. Nenorėjau ir neparašiau idealiausio pasaulyje kodo. Norėjau tik su Jumis visais pasidalint mintim/idėja, kuri man atrodo labai svarbi… apie kodo komentarus taip pat neužsiminiau, nes ne tai buvo mano pagrindinė idėja.

    beja, ten kode turėjo matytis atitraukimai (indentavimas), nžn kodėl jo nerodo.

    enc: nesiginčyju. Bet dešimtokai (dešimtokės) nežino kas tai yra “timestamp” ir kolkas nereikia žinoti.. ech, jiem dar ciklų neišdėstė…

    care: sutinku su Tavim - nevisada verta vargti ilgiausiai prie kažkokios menkos užduoties, prie kurios niekad nebegryši.. Bet pirma: kaip minėjau (ir įrodžiau), mano siūlomu būdu mes net greičiau/lengviau išspresim tą užduotį. T.y. ne daugiau darbo įdėsim bet mažiau. Antra: nebūtina užsiciklinti ant šito pavyzdžio. Tikrai būna atveju, kai spresdami realius uždavinius gautume geresnius rezultatus (įvairiom prasmėm) jei naudotumėm šį “skaldyk ir valdyk principą”

    U-toks: nežinau kiek būtų gavusi su savo pirmu sprendimu - aš gi įsikišau nebaigus sprest, ir todėl ji persprendė kitaip. O rezultate gavo 10.

    Dėkui visiem už komentarus…

  9. Paulius

    P.S. tavo kode yra klaidų.
    Jei po atėmimo sekundžių yra

  10. mrkiller

    Galutinis kodas su komentarais:

    {nuskaitomi kintamieji val|min|sec}
    read(val, min, sec);

    {laikas konvertuojamas i sekundes}
    timestamp = 3600 * val + 60 * min + sec;

    past = timestamp - 1;

    {laikas konvertuojamas atgal i valandas, minutes, sekundes}
    nval = past div 3600;
    rest = past mod 3600;
    nmin = rest div 60;
    nsec = rest mod 60;

    {isvedami rezultatai}
    writeln(nval, nmin, nsec);

  11. foobar

    mrkiller, deja, bet laikui “00:00:00 - 1 sekundė” taviškė programa nieko gero neparodys ;)

  12. enc

    foobar - neigiamo laiko nebūna

  13. Gudis

    :) geras straipsnis

  14. blaH

    enc:
    00:00:00 - 1 = 23:59:59

  15. enc

    blaH - tokiam dalykui reikia sąlygos.

  16. abss

    :) Labai gražios optimizacijos pasirodo komentaruose, bet iš to gudrumo gauname, kad esant minėtai situacijai su laiku 00:00:00 programa veikia klaidingai, o norint, kad veiktų teisingai, prirašius dar būtino kodo programa taip gražiai nebeatrodytų, plius prirašius būtinus kintamųjų aprašymus pasimatytų, kad viskas dar negražiau (ko galima išvengti panaudojant tuos pačius kintamuosius kai kur, dėl ko, deja, nukenčia ir taip prastokas programos skaitomumas). Tad pagarba straipsnio autoriui, kad tokio paprasto pavyzdžio sugebėjo nesudarkyti ir pateikė labai švarią, gerai veikiančią ir be komentarų aiškiai suprantamą programą, kurioje panaudojo vos tris kintamuosius, kuriuos buvo nurodyta panaudoti užduotyje. Ne visiem duota :)

  17. Raigedas

    dėkui, abss.
    visgi mano pastangos nenuėjo veltui…

  18. skeptikas

    enc
    nori pasiginčyti apie efektyvumą? .)

    As manau Raigedo algoritmas daug efektyvesnis. Jeigu reikia atimti *tik* viena sekunde. Tai koks tikslas viska perskaiciuoti sekundem, kad atimti viena sekunde ? ..

  19. enc

    skeptikas - aš padarau - vieną patikrinimą - ar tu esi matęs turbo paskalio sukompiliuotą kodą? asm’ą? kiekvienas toks palyginimas reiškia labau daug, be to - aš parašiau, kad tai yra pseudo-kodas. t.y. tiesiog instrukcijos, jeigu reikia kažko papildymo - dasirašyk

    taip, aš pasiginčyčiau dėl efektyvumo, nes yra išvestos formulės, kurios nurodo algoritmo sudėtingumą bei efektyvumą, todėl aš esu be galo įsitikinęs, kad mano algoritmas yra efektyvesnis.

    juo labiau galėčiau pradėti ginčytis, kad sąlyga nebuvo iki galo apibrėžta (t.y. ar nors vienas laiko vienetas galėjo būti įvestas NEteigiamas).

  20. nieks

    na, del neigiamo laiko - labai paprastas sprendimas:
    tiesiog dadedame „parą”, arba enc pseudokodu:

    timestamp = 3600 * (val+24) + 60 * min + sec;
    ….
    nval = past div 3600 mod 24;

    Bet tikriausiai jau ir patys tai sugalvoję busite. :)

  21. Algerdas

    o ne paprasciau:
    WriteLn(TimeToStr(now-1/24/60/60));

Rašyti komentarą

Jūs privalote prisijungti jeigu norite rašyti komentarą.