Šį semestrą universitete teko pasimokyti nedaug dalykų. Tačiau buvo ir tokių, kuriuose reikėjo programuoti.
Viename dalyke reikėjo naudotis žiniomis iš kokių dešimties anksčiau praeitų dalykų, ir daugiausia programuoti Perl kalba. Taip pat reikėjo naudotis R kalba, bei grafikos programomis...
Kitame dalyke reikėjo suprogramuoti grafą apdorojantį algoritmą. Programa turėjo surasti ir išvesti atstumus tarp grafo taškų.
Gavosi taip, kad praktiškai nepasimokiau abiejų dalykų, ir neparašiau daugumos programų. Priežastys kažkur anapus. O universitetas tikrai patiko.
***
Savaitgaliais teko, jau nebijau pavadint - tradiciškai, dalyvauti OpenCup'e. Bet tik ankstyvo žiemsario turuose. Prie manęs į komandą prisijungė jaunas protas. Deja matematiškas, funkcinės mąstysenos garbintojas, dievinantis Python'o kosmines funkcines galimybes ir dar net nežinojęs kaip šioje kalboje nuskaityti duomenis iš failo ar standartinės įvesties (stdin) :) .
Sekėsi mūsų komandai prastokai, bet man vistiek ji patiko. Aš imdavausi spręsti lengviausius ir suprantamiausius, bei trumpiausių sąlygų uždavinius, o linksmasis ir kupinas optimizmo komandos draugas - pačius sunkiausius ir labiausiai matematiškus uždavinius. Nei jam, nei man nepavykdavo išspręsti savų uždavinių, nors gal kokį lengvesnį ir buvau išsprendęs. Mėginau Perlu ir kartą - Rubiu.
Po to laisvalaikiais užsikabinau dalyvauti (kaip šios srities liaudis vadina - "pakibinėti") Codeforces turnyrėliuose. Sudalyvavau iš viso 12-oje.
Patiko dalyvauti. Nors sekdavosi sunkiai. Viską rašiau Perlu. Po 12-os turnyrėlių antrąjį kartą nusileidau į labai žemą reitingą (esu "Newbie") - tas mano reitingas yra pats žemiausias iš visų apie trisdešimties registruotų svetainėje lietuviškų akauntų. Nesistebiu, nes programuoju labai silpnai ir lėtai. Lėtai sekasi koduoti, ir susikaupti. Daug klaidų ir neteisinga metodika. Sprendžiu uždavinius sudėtingėjimo eiliškumu.
Labai patiko paskutinio turo trečias uždavinys. Jį išsprendžiau tik šįryt. Pasirodo, jį išsprendę tik ~700 Codeforces vartotojų. Reiškia, kad išsprendžiau ne lengvą, bet "vidutinį" uždavinį - tai džiugina. Tačiau deja išspręsti per varžybų laiką nepavyko.
Uždavinys toks, kad:
pateiktas simboliais "." ir "E" užpildytas kvadratas.
Reikia nurodyti minimaliausią kiekį koordinačių porų (bet kurių tinkamų), kurių kiekviena reiškia kvadrato vietą, kurioje yra taškas, ir nuo kurios į visas keturias puses esantys langeliai ir pats langelis "užmigdomi". Ir visos koordinačių poros "užmigdo" visą kvadratą. Antraip išvesti "-1". 329A.
Problema, kad uždavinį išsprendžiau mintyse neteisingai, ir tokį pradėjau programuoti. Suprogramavau. Tačiau testų nepraėjo. Vėliau supratau, kad ne apie visus atvejus pagalvojau, ir dar kartą išsprendžiau, bet ir vėl neteisingai - vėl ne apie visus atvejus buvo pagalvota. Šįkart jau buvo lengviau, nes pasibaigus turnyrui - galėjau matyti, kokių testinių atvejų programa nepraeina, iš jų supratau, kad nors ir suprogramavau teisingai, bet ne visai tokį uždavinį. T.y. aš jo teisingai neišsprendžiau. Kai supratau, kaip yra teisingai, tada ir suprogramavau taip, bei sprendimas buvo užskaitytas. Kartais būna, kad pilnai išspręstas visiems atvejams uždavinys lengviau suprogramuojamas, negu neteisingai išspręstas (ne visiems pastebėtiems atvejams), o kartais - sunkiau. Šįkart teisingas sprendimas buvo lengviau suprogramuojamas, negu neteisingas. Jeigu būčiau jį sugalvojęs tik ką susipažinęs su uždaviniu, tuomet gal net spėčiau jį atlikti per turnyrinį laiką (likusias ~1,5 val.). Uždavinys grakštus.
Uždaviniui išspręsti, man reikėjo pasirašyti procedūrą, kuri transponuoja mano simbolių kvadratą. Ši procedūra (subrutina) pasirašė per ~1/3 laiko, naudoto spręsti teisingai sprendžiamą užduotį.
Tačiau teko gyvenime jau keletą sykių rašyti atskirą transponavimo užduotį (porą kart - golfe, kartą - opencup'e). Dėl to, ją rašiau greičiau. Tačiau, juk galėčiau pačią subrutiną naudoti kiekvienam kode, kad nereikėtų per naują rašyti to paties. Bet neaišku, ar taip daryti verta.
Bendrai paėmus, programavimu ir tobulėjimu jo srityje skurdus gavosi pusmetis.
2013 m. liepos 22 d., pirmadienis
2013 m. vasario 16 d., šeštadienis
Anarchy golfas - 2
Anarchy golf puslapyje daugiausia žaidžiau su Perl kalba, bet kelis kartus pamėginau ir su FPC, bei su Ruby.
Svetainė tikrai anarchiška, nes net pats pasirodo, galiu joje kurti užduotis. Prieš mėnesį tą ir pradėjau išmėginti.
Sukūriau dvi [1, 2] užduotėles, kurios sulaukė normalaus populiarumo, ir vieną - kuri itin nepopuliari, reiškia - nepatikusi [3].
***
Dar įkelsiu keletą neitin prasmingų mano pasispardymų:
1. Užduotis "alternating case lines": kas antra eilutė verčiama aperkeisu pradedant pirmąja, kitos - lavuerkeisu. Taip kito kodas:
print++$i%2?uc:lc for<>
O štai taip atrodo geriausias sprendimas (žavu!):
print uc,lc<>while<> # autorius: tanon
2. Užduotis "repeated number". Taip kito kodas:
print((chop||next)x$_,"\n")for 21..89
Ta pati užduotis kaip sekėsi su Ruby:
(21..89).each{|i|i%10!=0&&puts((i%10).to_s*(i/10))}
Svetainė tikrai anarchiška, nes net pats pasirodo, galiu joje kurti užduotis. Prieš mėnesį tą ir pradėjau išmėginti.
Sukūriau dvi [1, 2] užduotėles, kurios sulaukė normalaus populiarumo, ir vieną - kuri itin nepopuliari, reiškia - nepatikusi [3].
***
Dar įkelsiu keletą neitin prasmingų mano pasispardymų:
1. Užduotis "alternating case lines": kas antra eilutė verčiama aperkeisu pradedant pirmąja, kitos - lavuerkeisu. Taip kito kodas:
print++$i%2?uc:lc for<>
O štai taip atrodo geriausias sprendimas (žavu!):
print uc,lc<>while<> # autorius: tanon
2. Užduotis "repeated number". Taip kito kodas:
print((chop||next)x$_,"\n")for 21..89
Ta pati užduotis kaip sekėsi su Ruby:
2013 m. vasario 2 d., šeštadienis
Pusmečio (2012 rudens semestro) apžvalga
Šio semestro medžiaga (dalykai) universitete labai patiko. Kai kurių dalykų net teko anksčiau ar vėliau pasimokyti. Kai kurių ne.
Buvo galimybė mokytis kompiuterinių tinklų. Šį praskipinau.
Ganėtinai stipriai patiko, bei manau, kad buvo man naudingas, dalykas apie naudojimąsi Unix terpe, komandine eilute, rašyti kažkokius skriptukus, naudotis "mikrokalbomis" (awk, sed berods). Dar tame dalyke teko pasimokyti dirbti su Subversija (svn). Bei kurti Makefailus, bei juos naudoti kuriamos programos testavimui, iš kart naudojant keletą testinių failų.
Anksčiau (ir dabar) programas rašydavau taip, kad turėdavau daug jos kopijų, ir versijų. Taip pat retai rašydavau įrašus (log'us) naujoms versijoms, dėl to po kiek laiko atsivertęs - pasimesdavau - kuo viena nuo kitos skiriasi. Beigi būdavo įvairių versijų atšakų. Susipažinimas su SVN buvo naudingas - teko juo naudotis, tačiau "revert'inti" programas teko retai, ir atsikėlinėt senesnes versijas - irgi teko retai.
Subversija veikia taip: yra kažkur nutolęs serveris, kuriame yra sukurta repozitorija. Internetu bendraujama su ta repozitorija, ir į ją "įdedama" saugojimui rašoma programa. Kiti, turintys priėjimą, gali tą programą atsisiųsti ir naudoti, ar net patys ją keisti, plėsti, išsaugoti. Taip sukuriama galimybė nuotoliniam bendradarbiavimui. Tokio išbandyti neteko. Ciklas toks: iš repozitorijos atsisiunčiama programa (jos kopija), ji modifikuojama, ir vėliau commit'inama (nusiunčiama atgal). Kitą kartą vėl ji bus atsisiunčiama (checkout'inama), modifikuojama, commit'inama. Ne tik programa, bet apskritai bet kurie failai ar folderiai. O jeigu norėsis atsisiųsti senesnę failo versiją, tai reikės tiesiog įvesti senesnės revizijos (commit'inimo) numerį (komanda: svn update -r N; N- numeris). Kiekvieną kart commit'inant, SVN'as prašo įvesti log'ą - parašyt, kas naujo prisidėjo naujoje revizijoje, ar kas buvo pakeist, kad po to būtų lengvaiu atsekti.
Daugiau konkrečiai programavimo dalykų nebuvo, tačiau buvo susijusių dalykų.
Viename buvo mokomasi statistikos ir įvairių testų, bei tam buvo naudojamas MĖ Excelis, bei mokomasi ir naudojamasi R programavimo kalba. Duomenų generavimui, apdorojimui ir atvaizdavimui. Neteko išmokt. O pats R'as patiko. Ir nemokamas, ir gana draugiškas, ir daug modulių jam sukurta.
Kitame teko mokytis visokių kodavimų, ir bereikėjo parašyti kelias programas, kurios atlieka kodavimą ir dekodavimą. Rašiau jas "de novo", bet pačių kodavimo algoritmų gerai neišmaniau, tad naudojausi Wikipedija ir internetais, kad pagal algoritmų iliustruoto veikimo pavyzdžius, parašyčiau programas. Naudojau Perl kalbą. Pavyko parašyti su klaidom, ir neefektyviais algoritmais, bet patiko bent tiek, kiek pavyko.
Dar viename dalyke buvo visokių mokymųsi naudotis jau sukurtomis ir plačiai naudojamomis programomis... Be to reikėjo parašyti ir patiems įvairių užklausų. Tai šitą irgi beveik nepasimokiau.
*****
Be mokomųjų dalykų, sekmadieniais teko dalyvauti OpenCup varžybose (contest'uose), fakultete ar iš namų. Dalyvavau rečiau negu pavasarį. Buvau šį kart vienas komandoje. Tai, kadangi vienas ir nekoks programuotojas, tai isšpresdavau vos po ~1 uždavinį per etapą - nedaug. Kai kada ne visas 5 valandas dalyvaudavau, o kaip išeidavo.
Nespėdavau įsigilinti ar net perskaityti visų sąlygų. Imdavau lengvesniuosius uždavinius. Kelis teko spręsti Pascal'iu, tačiau jau šį semestrą ėmiau naudotis ir Perl'u. Ypač padėjo ten, kur reikėjo apdoroti eilutes.
[Papildau keliais uždavinių sprendimais (įkeliu į Ideone.com svetainę).
* Su išsamesniu kodo pakomentavimu,
* karalium nueit iš vieno langelio į kitą,
* chupakabros eina į vieną pusę, barmolėjai į kitą, ir valgo mažesnius berods (-1 yra tuščias laukas),
apskaičiuoti kiek kurių liks,
* ištrinti bug'ų "žymes" iš kodo (perl'o regexp'ų žavumas)]
Pusmečiui įpusėjus, šiek tiek susidomėjau (gana primityviai) golf'ingu, ir gruodžio-sausio mėn. ėmiau žaisti golf'ą. Rezultatai neįpatingi, bet retkarčiais tiesiog būna įdomu.
O iškart po sesijos - atostoginę savaitę kiek daugiau užsiimiau laiko praleidimu prie programų. Tai buvo golfingas (Perlu), Ruby kalbos pagrindų mokymasis, ir contest'inių programavimo užduočių sprendimas. Contestin'es užduotis pasprendžiau pačias lengviausias, užsiregistravęs į Codeforces ir Timus OJ.
Codeforces labai patiko - viskas puikiai paruošta turnyrui, kurio formatas gana žaismingas. Taip pat neturnyro metu galima žiūrėti dalyvių kodus - kaip jie sprendžia kokias užduotis, kur klysta.
Buvo galimybė mokytis kompiuterinių tinklų. Šį praskipinau.
Ganėtinai stipriai patiko, bei manau, kad buvo man naudingas, dalykas apie naudojimąsi Unix terpe, komandine eilute, rašyti kažkokius skriptukus, naudotis "mikrokalbomis" (awk, sed berods). Dar tame dalyke teko pasimokyti dirbti su Subversija (svn). Bei kurti Makefailus, bei juos naudoti kuriamos programos testavimui, iš kart naudojant keletą testinių failų.
Anksčiau (ir dabar) programas rašydavau taip, kad turėdavau daug jos kopijų, ir versijų. Taip pat retai rašydavau įrašus (log'us) naujoms versijoms, dėl to po kiek laiko atsivertęs - pasimesdavau - kuo viena nuo kitos skiriasi. Beigi būdavo įvairių versijų atšakų. Susipažinimas su SVN buvo naudingas - teko juo naudotis, tačiau "revert'inti" programas teko retai, ir atsikėlinėt senesnes versijas - irgi teko retai.
Subversija veikia taip: yra kažkur nutolęs serveris, kuriame yra sukurta repozitorija. Internetu bendraujama su ta repozitorija, ir į ją "įdedama" saugojimui rašoma programa. Kiti, turintys priėjimą, gali tą programą atsisiųsti ir naudoti, ar net patys ją keisti, plėsti, išsaugoti. Taip sukuriama galimybė nuotoliniam bendradarbiavimui. Tokio išbandyti neteko. Ciklas toks: iš repozitorijos atsisiunčiama programa (jos kopija), ji modifikuojama, ir vėliau commit'inama (nusiunčiama atgal). Kitą kartą vėl ji bus atsisiunčiama (checkout'inama), modifikuojama, commit'inama. Ne tik programa, bet apskritai bet kurie failai ar folderiai. O jeigu norėsis atsisiųsti senesnę failo versiją, tai reikės tiesiog įvesti senesnės revizijos (commit'inimo) numerį (komanda: svn update -r N; N- numeris). Kiekvieną kart commit'inant, SVN'as prašo įvesti log'ą - parašyt, kas naujo prisidėjo naujoje revizijoje, ar kas buvo pakeist, kad po to būtų lengvaiu atsekti.
Daugiau konkrečiai programavimo dalykų nebuvo, tačiau buvo susijusių dalykų.
Viename buvo mokomasi statistikos ir įvairių testų, bei tam buvo naudojamas MĖ Excelis, bei mokomasi ir naudojamasi R programavimo kalba. Duomenų generavimui, apdorojimui ir atvaizdavimui. Neteko išmokt. O pats R'as patiko. Ir nemokamas, ir gana draugiškas, ir daug modulių jam sukurta.
Kitame teko mokytis visokių kodavimų, ir bereikėjo parašyti kelias programas, kurios atlieka kodavimą ir dekodavimą. Rašiau jas "de novo", bet pačių kodavimo algoritmų gerai neišmaniau, tad naudojausi Wikipedija ir internetais, kad pagal algoritmų iliustruoto veikimo pavyzdžius, parašyčiau programas. Naudojau Perl kalbą. Pavyko parašyti su klaidom, ir neefektyviais algoritmais, bet patiko bent tiek, kiek pavyko.
Dar viename dalyke buvo visokių mokymųsi naudotis jau sukurtomis ir plačiai naudojamomis programomis... Be to reikėjo parašyti ir patiems įvairių užklausų. Tai šitą irgi beveik nepasimokiau.
*****
Be mokomųjų dalykų, sekmadieniais teko dalyvauti OpenCup varžybose (contest'uose), fakultete ar iš namų. Dalyvavau rečiau negu pavasarį. Buvau šį kart vienas komandoje. Tai, kadangi vienas ir nekoks programuotojas, tai isšpresdavau vos po ~1 uždavinį per etapą - nedaug. Kai kada ne visas 5 valandas dalyvaudavau, o kaip išeidavo.
Nespėdavau įsigilinti ar net perskaityti visų sąlygų. Imdavau lengvesniuosius uždavinius. Kelis teko spręsti Pascal'iu, tačiau jau šį semestrą ėmiau naudotis ir Perl'u. Ypač padėjo ten, kur reikėjo apdoroti eilutes.
[Papildau keliais uždavinių sprendimais (įkeliu į Ideone.com svetainę).
* Su išsamesniu kodo pakomentavimu,
* karalium nueit iš vieno langelio į kitą,
* chupakabros eina į vieną pusę, barmolėjai į kitą, ir valgo mažesnius berods (-1 yra tuščias laukas),
apskaičiuoti kiek kurių liks,
* ištrinti bug'ų "žymes" iš kodo (perl'o regexp'ų žavumas)]
Pusmečiui įpusėjus, šiek tiek susidomėjau (gana primityviai) golf'ingu, ir gruodžio-sausio mėn. ėmiau žaisti golf'ą. Rezultatai neįpatingi, bet retkarčiais tiesiog būna įdomu.
O iškart po sesijos - atostoginę savaitę kiek daugiau užsiimiau laiko praleidimu prie programų. Tai buvo golfingas (Perlu), Ruby kalbos pagrindų mokymasis, ir contest'inių programavimo užduočių sprendimas. Contestin'es užduotis pasprendžiau pačias lengviausias, užsiregistravęs į Codeforces ir Timus OJ.
Codeforces labai patiko - viskas puikiai paruošta turnyrui, kurio formatas gana žaismingas. Taip pat neturnyro metu galima žiūrėti dalyvių kodus - kaip jie sprendžia kokias užduotis, kur klysta.
2013 m. sausio 16 d., trečiadienis
Anarchy golfas - 1 (Perlu)
Šį semestrą (2012 rudens), suradau dar vieną prokrastinacijos būdą. Toks fun "žaidimas" - programinimas sunaudojant kuo mažiau keystrokų - kuo mažiau vargo pirštams (dėmesio šis žaidimas - tinginiams! kitiems nerekomenduoju ;) ).
Būtų viskas gerai, jeigu duotų naudos, ir jei pavyktų "suspausti" kodą iki mažai simbolių, tačiau dažniausiai - keblu būna suspausti, ir naudos iš tokio "programavimo" - nedaug.
Būtų viskas gerai, jeigu duotų naudos, ir jei pavyktų "suspausti" kodą iki mažai simbolių, tačiau dažniausiai - keblu būna suspausti, ir naudos iš tokio "programavimo" - nedaug.
Kodėl pasirinkau būtent "pakibti" ant tokių programavimo žaidimų - tema išeina iš už blogo paskirties.
Taigi - Perl golf!
Pagooglinau svetainių. Suradau šią - http://golf.shinh.org/all.rb , ir joje apsistojau. Čia pateikta daug paprastučių ir sudėtingesnių uždavinukų, kuriuos galima submitinti visokiomis programavimo kalbomis (sąrašas nemažas, plius pridėtos specialiai golfui skirtos kalbos).
Pats submitinau tik Perlu.
Statistikoje galima išskirti kalbas, kuriomis Golfą pavyksta sužaisti dažniausiai geriau.
Tai specialios golfingo kalbos.
Tai kai kurios mikrokalbos (sed, awk).
Taigi - Perl golf!
Pagooglinau svetainių. Suradau šią - http://golf.shinh.org/all.rb , ir joje apsistojau. Čia pateikta daug paprastučių ir sudėtingesnių uždavinukų, kuriuos galima submitinti visokiomis programavimo kalbomis (sąrašas nemažas, plius pridėtos specialiai golfui skirtos kalbos).
Pats submitinau tik Perlu.
Statistikoje galima išskirti kalbas, kuriomis Golfą pavyksta sužaisti dažniausiai geriau.
Tai specialios golfingo kalbos.
Tai kai kurios mikrokalbos (sed, awk).
Ir Perl vs Ruby.
***
Perlo kodas sutrumpėja, naudojant specialiuosius kintamuosius, ir reguliariasias išraiškas. Kai kurių specialiųjų kintamųjų nenaudoju, bet matu naudotus kitų programose. Jų dar nepasimokiau. Tai $., $&, $/ , kt.. Taip pat kai kurių konstrukcijų dar nesu supratęs, ar žinantis. Bet šiek tiek išmokau naujo žiūrėdamas kitų parašytus kodus.
***
Pateiksiu keletą užduočių ir jų sprendimų.
1. http://golf.shinh.org/p.rb?two+kinds+of+digit - čia reik, kad programa išspausdintų visus skaičius nuo 1 iki 10k, kurie sudaryti iš dviejų skirtingų skaitmenų.
***
Pateiksiu keletą užduočių ir jų sprendimų.
1. http://golf.shinh.org/p.rb?two+kinds+of+digit - čia reik, kad programa išspausdintų visus skaičius nuo 1 iki 10k, kurie sudaryti iš dviejų skirtingų skaitmenų.
Kodas:
for(1..10000){$b=$c=-2;/$b/&&$c++while($b++<9);$c||print"$_\n"}
for(1..10000){$b=$c=-2;/$b/&&$c++while($b++<9);$c||print"$_\n"}
2. Identity Matrix - perskaityti matricos kraštinę, ir išspausdinti vienetinę matricą. Pvz. 2. Ats.:
1 0
1 0
0 1
Kodas:
$a=<>;$_="1"." 0"x--$a."\n";{print;s/(.+) 0$/0 $1/;redo if$a--}
Toliau pateiksiu kelis uždavinius, su jų pradiniais sprendimais, o dar toliau - tų užduočių patobulintus (sutrumpintus) sprendimus:
3a) "Reduce fractions" - http://golf.shinh.org/p.rb?Reduce+fractions - reikia "suprastinti" trupmenas.
3a) "Reduce fractions" - http://golf.shinh.org/p.rb?Reduce+fractions - reikia "suprastinti" trupmenas.
Kodas:
while(<>){chomp;@_=split/\//;$a=2;while($a<$_[1]){if(!($_[0]%$a)&& !($_[1]%$a)){for$i(0,1){$_[$i]=$_[$i]/$a};redo}$a++}print"$_[0]/$_[1]\n"}
4a) "Back and forth" - http://golf.shinh.org/p.rb?Back+and+forth , žiūrėti pvz.
Kodas:
Kodas:
$_=join"",@_=<>;s/(\S+)/$i++%2?print" "x($j-=length$1).reverse"\n$1":print" "x$j,"$1\n";$j+=length$1if$i%2/meg;
5a) "Paragraph counter" - skaičiuoja kiek eilučių. Išveda atsakymą.
Kodas:
6aI) "Cross product of 2 strings" - http://golf.shinh.org/p.rb?Cross+Product+of+two+Strings .
Kodas:
Kodas:
6aII) Kodas:
---
3b)
while(<>){chomp;$_=@_=split/\//;while($_<$_[1]){if(!($_[0]%$_||$_[1]%$_)){for$i(0,1){$_[$i]/=$_}redo}$_++}print"$_[0]/$_[1]\n"}
4b-final)
5b)
6b-final)
---
3c-final)
for(<>){$_=($a,$b)=/(\d+).(\d+)/;while($_<$b){until($a%$_||$b%$_){$a/=$_;$b/=$_}$_++}print"$a/$b\n"}
5c-final)
/.$/&&$i++for<>;print$i
*-*-*-*-*
Toliau pateiksiu kelis kodus, be paaiškinimų, ką jie atlieka.
Taip golf-kodas kartais būna ir obfuscation-kodas (t.y. nesuprantamas), nors nevisada...
7.
8. (šis kodas užima 66 simbolius, ir tai yra prasčiausias rezultatas iš visų submitintų Perlu. Geriausias rezultatas - 56 simboliai. Tačiau mane tai labai pradžiugino, nes dažniausiai mano kodai nuo "varžovų" atsilieka per 1,5 ar 2, ar net 3 kartus)
9.
<>;while(<>){$_=<>;while(/ /){s/(\d+) (\d+)//;for$i(1..$1){$2%$i||$1%$i or$j=$i}s/^/$j/}print}
*-*-*-*-*
Taip pat parodysiu kelių užduočių kodo kitimo istoriją.
10. "Liouville number" - išspausdinti Liovilio skaičių (http://en.wikipedia.org/wiki/Liouville_number) iki 1000-ojo skaitmens po kablelio.
$_="0.".$i++x1e3;$i*=++$j,substr$_,$i+1,1,1while$j<6;print
11. "Simple preprocessor" - http://golf.shinh.org/p.rb?Simple+Preprocessor
$_=join"",<>;s/^\s*(#.*\n)?|\s+$//mg,print
2012 m. birželio 30 d., šeštadienis
Metų apžvalga nuo birželio iki birželio.
Taigi, prabėgo dar metai mokslų, vėl birželis. Per tuos metus šiek tiek, bet nedaug, programavimo ir informatikos prasme patobulėjau.
Rudens semestrą turėjau Duomenų Struktūrų dalyką, kuris sekėsi gana sunkiai, ir baigęs kursą žinau, kad mažai jį nutuokiu. Tai buvo vienintelis programinimo dalykas tą semestrą, tad kaip laisvąjį pasirinkau dar "Algoritmavimo seminarą". Pastarasis dalykas buvo toks, kad reikėjo pasirinkti ICPC ( http://mif.vu.lt/icpc/ ) puslapyje sezoną ir iš jame pateiktų ~10-15 užduočių pasirinkti ir išspręsti keturias (4). Tai - uždaviniai, reikalaujantys parašyti programavimo kalba kodą, kuris per ribotą (trumpą) laiką išspręstų, bet kokį užduoties atvejį.
Šį dalyką atsiskaityti susigriebiau tik paskutinėmis semestro savaitėmis, ir per savaitgalį ir pirmadienį, viską sudėjus, tai būtų apie parą laiko, parašiau 5 užduotis, o vienai iš nesigavusių buvau skyręs daug laiko, nes užduotis patiko ir šiaip nenorėjau pasiduoti. Viską rašiau Pascal'iu.
Prieš pradedant rašyti programas, paskaičiau e-knygą "Informatikos olimpiados: algoritmai ir taikymo pavyzdžiai.", perskaičiau apie trečdalį; patiko.
Na, o pavasario semestre jau turėjau daugiau programavimo. Buvo du dalykai: Interneto Technologijos ir programavimas Perl kalba.
Interneto technologijas įsisavinau prastokai, nedaug joms skyriau laiko ir domėjimosi, nebuvo ir polinkio. Tai buvo tinklalapių kūrimo praktika. Egzaminą laikiau labai sunkiai, praktikos darbai irgi ėjosi sunkiai, daug temų liko neįsisavintos.
Perl kalba visai normali. Vietomis ir labai patiko, ir vietomis labai nepatiko. Patiko kai kurie "abstrahavimai": funkcijai ir procedūrai naudojamas bendras sub(){}, eilutėms pildyti, modifikuoti, iškirpinėti fragmentams naudojamas bendras substr(), patiko "einamasieji" kintamasis/masyvas/asoc.masyvas - $_, @_, %_, aišku patiko RegExp - reguliariosios išraiškos, žargoniškai - įpraiškos. Nepatiko, kad dažnai padarau kokių nors klaidų kode, ir negaliu suprasti, kur jos, ilgai užtrunka jų aptikimas; kai kur yra archajiškumų, kuriuos reikia tiesiog žinoti; nepatiko pažindinimasis su paketais ir moduliais.
Prieš egzaminą pakūriau mini-testuką RegExp'ams, naudodamasis Google apklausa. Ji ir jos rezultatai - vieši; pirmoje eilutėje - atsakymai, kurių didžioji dauguma - teisingi. Kas nori, gali išsibandyti testuką čia, vėliau peržiūrėti ats.
Dar pavasario semestro metu teko užsiregistruoti į OpenCup turnyrėlį. Prisijungiau prie komandos, tapome tryse. Ir daugmaž kas antrą savaitgalį, sekmadieniais, vykstančiame 6 valandas konkurse, rinkdavomės spręsti uždavinius, panašius į ICPC uždavinius. Dalyvavome antrojoje divizijoje, kurioje uždaviniai yra silpnesni. Ir išspręsdavome per duotą laiką apie 1-3 uždavinius, iš ~10. Gana mažai. Na, bet toks mūsų lygis. Užtat spręsti būdavo įdomu, o ir sąlygos neretai pralinksmindavo.
Sprendėme kiekvienas komandos narys savo mėgiama kalba, tai buvo C/C++, Python, ir žinoma - Pascal :)
Labiausiai man patikusios užduotys:
1 ture - užduotis su TV bokštu [neišsprendėm]
2 ture - Knife to me (torto pjaustymas) [išsprendėm]
3 ture - Lenktynės [neišsprendžiau; namie vėliau išsprendžiau] ir Žirgas [neišsprendžiau]
4 ture - Rectadarts (ru: Прямоудартс) [išsprendėm gal ir teisingai, bet per lėtas algoritmas]
6 ture - Building (statybos) [išsprendžiau]
7 ture - Giant Soccer (visai lengvas, bet linksmas) [išsprendžiau]
Pirmieji šeši išvardytieji yra geometriniai.
Building užduoties kodas:
O Perl'o dalyke teko irgi keletą programų rašyti. Iš pradžių lengvesnes: a) faile esančių skaičių suma, vidurkis, b) faile esančių žodžių ilgių vidurkis, išrikiavimas ir atspausdinimas lietuviškos abėcėlės tvarka, c) <...>
Vėliau pabandžiau šiaip mažučių subroutinų pasirašyti. Štai programa su pora subroutinų, šiek tiek modifikuojančių tekstinį failą:
#!/usr/bin/perl
#RS 2012-06-10
print("koki faila formatuosime?\n");
$failas=<>;
chomp($failas);
open(f, "$failas") or die "Negaliu atidaryti failo";
open(g, ">r_$failas") or die "Negaliu atidaryti failo";
sub trina_tuscias_eil {
my $eil=shift;
$eil=~/^\n$/ && chomp($eil);
return $eil;
}
sub trina_tarpu_pertekliu { # neliecia komentaru
my $eil=shift;
while ($eil=~/^[^#]*\x20{2,}/) {
$eil=~s/(^[^#]*)\x20{2,}/$1\x20/;
}
return $eil;
}
while ($eil=<f>) {
$eil=trina_tuscias_eil($eil);
$eil=trina_tarpu_pertekliu($eil);
print g $eil;
}
$readkey=<>;
close(f);
close(g);
Rudens semestrą turėjau Duomenų Struktūrų dalyką, kuris sekėsi gana sunkiai, ir baigęs kursą žinau, kad mažai jį nutuokiu. Tai buvo vienintelis programinimo dalykas tą semestrą, tad kaip laisvąjį pasirinkau dar "Algoritmavimo seminarą". Pastarasis dalykas buvo toks, kad reikėjo pasirinkti ICPC ( http://mif.vu.lt/icpc/ ) puslapyje sezoną ir iš jame pateiktų ~10-15 užduočių pasirinkti ir išspręsti keturias (4). Tai - uždaviniai, reikalaujantys parašyti programavimo kalba kodą, kuris per ribotą (trumpą) laiką išspręstų, bet kokį užduoties atvejį.
Šį dalyką atsiskaityti susigriebiau tik paskutinėmis semestro savaitėmis, ir per savaitgalį ir pirmadienį, viską sudėjus, tai būtų apie parą laiko, parašiau 5 užduotis, o vienai iš nesigavusių buvau skyręs daug laiko, nes užduotis patiko ir šiaip nenorėjau pasiduoti. Viską rašiau Pascal'iu.
Prieš pradedant rašyti programas, paskaičiau e-knygą "Informatikos olimpiados: algoritmai ir taikymo pavyzdžiai.", perskaičiau apie trečdalį; patiko.
Na, o pavasario semestre jau turėjau daugiau programavimo. Buvo du dalykai: Interneto Technologijos ir programavimas Perl kalba.
Interneto technologijas įsisavinau prastokai, nedaug joms skyriau laiko ir domėjimosi, nebuvo ir polinkio. Tai buvo tinklalapių kūrimo praktika. Egzaminą laikiau labai sunkiai, praktikos darbai irgi ėjosi sunkiai, daug temų liko neįsisavintos.
Perl kalba visai normali. Vietomis ir labai patiko, ir vietomis labai nepatiko. Patiko kai kurie "abstrahavimai": funkcijai ir procedūrai naudojamas bendras sub(){}, eilutėms pildyti, modifikuoti, iškirpinėti fragmentams naudojamas bendras substr(), patiko "einamasieji" kintamasis/masyvas/asoc.masyvas - $_, @_, %_, aišku patiko RegExp - reguliariosios išraiškos, žargoniškai - įpraiškos. Nepatiko, kad dažnai padarau kokių nors klaidų kode, ir negaliu suprasti, kur jos, ilgai užtrunka jų aptikimas; kai kur yra archajiškumų, kuriuos reikia tiesiog žinoti; nepatiko pažindinimasis su paketais ir moduliais.
Prieš egzaminą pakūriau mini-testuką RegExp'ams, naudodamasis Google apklausa. Ji ir jos rezultatai - vieši; pirmoje eilutėje - atsakymai, kurių didžioji dauguma - teisingi. Kas nori, gali išsibandyti testuką čia, vėliau peržiūrėti ats.
Dar pavasario semestro metu teko užsiregistruoti į OpenCup turnyrėlį. Prisijungiau prie komandos, tapome tryse. Ir daugmaž kas antrą savaitgalį, sekmadieniais, vykstančiame 6 valandas konkurse, rinkdavomės spręsti uždavinius, panašius į ICPC uždavinius. Dalyvavome antrojoje divizijoje, kurioje uždaviniai yra silpnesni. Ir išspręsdavome per duotą laiką apie 1-3 uždavinius, iš ~10. Gana mažai. Na, bet toks mūsų lygis. Užtat spręsti būdavo įdomu, o ir sąlygos neretai pralinksmindavo.
Sprendėme kiekvienas komandos narys savo mėgiama kalba, tai buvo C/C++, Python, ir žinoma - Pascal :)
Labiausiai man patikusios užduotys:
1 ture - užduotis su TV bokštu [neišsprendėm]
2 ture - Knife to me (torto pjaustymas) [išsprendėm]
3 ture - Lenktynės [neišsprendžiau; namie vėliau išsprendžiau] ir Žirgas [neišsprendžiau]
4 ture - Rectadarts (ru: Прямоудартс) [išsprendėm gal ir teisingai, bet per lėtas algoritmas]
6 ture - Building (statybos) [išsprendžiau]
7 ture - Giant Soccer (visai lengvas, bet linksmas) [išsprendžiau]
Pirmieji šeši išvardytieji yra geometriniai.
Building užduoties kodas:
program Building;
var
l, w, n, r, x, y, ats, i, j : smallint;
a : array[1..16] of boolean;
begin
read(l, w, n); readln(r);
for i:=1 to 15 do a[i]:=false;
a[16]:=true;
ats:=4;
for i:=1 to n do begin
read(x); readln(y);
if (x<-l/2-r) or (x>l/2+r) or (y<-w/2-r) or (y>w/2+r) then continue;
for j:=1 to 4 do a[j]:=false;
if sqrt( sqr(-l/2 - x) + sqr(y) ) <= r then begin a[1]:=true; a[12]:=true; end;
if sqrt( sqr(+l/2 - x) + sqr(y) ) <= r then begin a[2]:=true; a[13]:=true; end;
if sqrt( sqr(-w/2 - y) + sqr(x) ) <= r then begin a[3]:=true; a[14]:=true; end;
if sqrt( sqr(+w/2 - y) + sqr(x) ) <= r then begin a[4]:=true; a[15]:=true; end;
if a[1] and a[2] and a[3] and a[4] then begin ats:=1; break; end;
if ats <= 2 then continue;
if not (a[1] or a[2] or a[3] or a[4]) then continue;
if (a[1] and a[2] and a[3]) or (a[4] and a[2] and a[3]) or (a[1] and a[2] and a[4]) or (a[1] and a[4] and a[3]) then begin
ats:=2; continue;
end;
if (a[1] and a[2]) then a[5]:=true;
if (a[1] and a[3]) then a[6]:=true;
if (a[1] and a[4]) then a[7]:=true;
if (a[2] and a[3]) then a[8]:=true;
if (a[2] and a[4]) then a[9]:=true;
if (a[3] and a[4]) then a[10]:=true;
end;
for i:=12 to 15 do a[16]:=a[16] and a[i];
if not a[16] then writeln('Impossible')
else
if ats <= 2 then writeln(ats)
else begin
for i:=5 to 10 do a[11]:=a[11] or a[i];
if not a[11] then writeln(ats)
else begin
if (a[5] and a[10]) or (a[6] and a[9]) or (a[7] and a[8]) then
begin ats:=2; writeln(ats); end
else begin ats:=3; writeln(ats); end;
end;
end;
end.
var
l, w, n, r, x, y, ats, i, j : smallint;
a : array[1..16] of boolean;
begin
read(l, w, n); readln(r);
for i:=1 to 15 do a[i]:=false;
a[16]:=true;
ats:=4;
for i:=1 to n do begin
read(x); readln(y);
if (x<-l/2-r) or (x>l/2+r) or (y<-w/2-r) or (y>w/2+r) then continue;
for j:=1 to 4 do a[j]:=false;
if sqrt( sqr(-l/2 - x) + sqr(y) ) <= r then begin a[1]:=true; a[12]:=true; end;
if sqrt( sqr(+l/2 - x) + sqr(y) ) <= r then begin a[2]:=true; a[13]:=true; end;
if sqrt( sqr(-w/2 - y) + sqr(x) ) <= r then begin a[3]:=true; a[14]:=true; end;
if sqrt( sqr(+w/2 - y) + sqr(x) ) <= r then begin a[4]:=true; a[15]:=true; end;
if a[1] and a[2] and a[3] and a[4] then begin ats:=1; break; end;
if ats <= 2 then continue;
if not (a[1] or a[2] or a[3] or a[4]) then continue;
if (a[1] and a[2] and a[3]) or (a[4] and a[2] and a[3]) or (a[1] and a[2] and a[4]) or (a[1] and a[4] and a[3]) then begin
ats:=2; continue;
end;
if (a[1] and a[2]) then a[5]:=true;
if (a[1] and a[3]) then a[6]:=true;
if (a[1] and a[4]) then a[7]:=true;
if (a[2] and a[3]) then a[8]:=true;
if (a[2] and a[4]) then a[9]:=true;
if (a[3] and a[4]) then a[10]:=true;
end;
for i:=12 to 15 do a[16]:=a[16] and a[i];
if not a[16] then writeln('Impossible')
else
if ats <= 2 then writeln(ats)
else begin
for i:=5 to 10 do a[11]:=a[11] or a[i];
if not a[11] then writeln(ats)
else begin
if (a[5] and a[10]) or (a[6] and a[9]) or (a[7] and a[8]) then
begin ats:=2; writeln(ats); end
else begin ats:=3; writeln(ats); end;
end;
end;
end.
O Perl'o dalyke teko irgi keletą programų rašyti. Iš pradžių lengvesnes: a) faile esančių skaičių suma, vidurkis, b) faile esančių žodžių ilgių vidurkis, išrikiavimas ir atspausdinimas lietuviškos abėcėlės tvarka, c) <...>
Vėliau pabandžiau šiaip mažučių subroutinų pasirašyti. Štai programa su pora subroutinų, šiek tiek modifikuojančių tekstinį failą:
#!/usr/bin/perl
#RS 2012-06-10
print("koki faila formatuosime?\n");
$failas=<>;
chomp($failas);
open(f, "$failas") or die "Negaliu atidaryti failo";
open(g, ">r_$failas") or die "Negaliu atidaryti failo";
sub trina_tuscias_eil {
my $eil=shift;
$eil=~/^\n$/ && chomp($eil);
return $eil;
}
sub trina_tarpu_pertekliu { # neliecia komentaru
my $eil=shift;
while ($eil=~/^[^#]*\x20{2,}/) {
$eil=~s/(^[^#]*)\x20{2,}/$1\x20/;
}
return $eil;
}
while ($eil=<f>) {
$eil=trina_tuscias_eil($eil);
$eil=trina_tarpu_pertekliu($eil);
print g $eil;
}
$readkey=<>;
close(f);
close(g);
2011 m. birželio 6 d., pirmadienis
AVL medis
Norint gauti papildomų balų neštis į egzaminą, galima buvo suprogramuoti AVL medį. Iš kursiokės paėmiau jos AVL programą ir aiškinausi pusę nakties prieš atsiskaitymo dieną. Pagalvojau, kad galbūt galima bus gauti nors ne maksimumą, bet bent pusę taškų už nepaties programuotą programą, jeigu gerai ją sugebėsiu paaiškinti bet kurioje eilutėje, bei jeigu parašysiu programai kažkokių papildomų įrankių. Kitą pusnaktę tuos įrankius ir bandžiau rašyti. Pavyko parašyti procedūrą, kuri sunumeruoja dvejetainio AVL medžio elementus man reikiama hierarchine tvarka, ir antrą procedūrą, kuri tuos elementus išspausdina ekrane atidėdama atitinkamą skaičių tarpų.
AVL programa tai dvejetainis medis, kuris pildomas naujais elementais, balansuojasi. Dvejetainis medis skirtas ten įdėto elemento paieškai. Jeigu į medį bus dedami elementai vienas po kito didėjantys, arba vienas po kito mažėjantys, tai medis turės vieną ilgą šaką, o jei bus dedami įvairūs elementai, tai jis bus šakotas bei trumpašakis ir bus greičiau vykdoma paieška. AVL medis - besibalansuojantis medis. Kuomet viena jo šaka pasidaro ilgesnė už bet kurią kitą 2 sąlyginiai vienetais, tai ji deformuojasi, vykdomas "posūkis": šaka ale nupjaunama, perlaužiama perpus, tada suklijuojama "V" raide ir pritvirtinama prie šakos pamato.
Taip atrodo programos interfeiso fragmentas, atlikus vieno skaičiaus įterpimą į AVL medį:
(dvejetas ir trejetas paraudoninti, neryškiai čia matosi)
Beje, formulę su DIV'ais tai galvojau ir testavau tikrai kokias 3 valandas. O medžio išspausdinimą padariau su lygiavimo klaida (buvo ne visai gražu), kurią sugalvojau kaip pataisyti tik kai prisėdau savaitę po atsiskaitymo.
Pateiksiu tik programos procedūras, kurios paruošia masyvą ir išspausdina medį pseudografiškai.
( uses crt;
type Pnode=^node;
node=record
l,r,t : Pnode;
n: integer;
end;
var root :Pnode; skait: array[1..255] of integer;
function auksciai( rod : Pnode) : integer;
var a1, a2 : integer;
begin
if (rod <> nil)
then
begin
a1 := auksciai(rod^.l) + 1 ;
a2 := auksciai(rod^.r) + 1 ;
if a1>=a2 then auksciai:=a1
else auksciai:=a2 ;
end
else auksciai := -1;
end; )
procedure isEilesMasyvas;
var te:Pnode; au,n,el,power,k,kn: integer;
begin
au:=auksciai(root);
power:=1; el:=0;
for n:=1 to au+1 do begin power:=power*2; el:=el+power div 2; end;
for n:=1 to el do
begin k:=1; kn:=n;
while k*2<=n do k:=k*2; te:=root;
while (kn<>1 ) and (k<>1) and (kn div k <>0) and (te<>nil) do
begin if kn mod k div (k div 2) = 0 then te:=te^.l else te:=te^.r; k:=k div 2; end;
if te <> nil then skait[n]:=te^.n else skait[n]:=0;
end;
writeln('stai isEilesMasyvo ',el, ' elementai: ');
for n:=1 to el do write(skait[n],' ');
end;
procedure piestiMedi(reiksme: integer);
var au,i,j,k,s,power,tarpai: integer;
begin
au:=auksciai(root);
s:=0;
writeln;
writeln('isspausdinu visus Medzio elementus: ');
for i:=1 to au+1 do
begin
power:=1;
for j:=au+1-i downto 1 do begin power:=power*2; end;
tarpai:=power*2-2;
power:=1;
for j:=1 to i do power:=power*2;
for k:=1 to power div 2 do
begin
for j:=1 to tarpai do write(' ');
if k>1 then for j:=1 to tarpai do write(' ');
s:=s+1;
if (skait[s]<10) and (skait[s]>0) then write(' ');
if skait[s]<>0 then
begin write(' ');
if skait[s]<>reiksme then write(skait[s])
else begin textcolor(12); write(skait[s]); textcolor(7); end;
write(' ');
end
else write(' ');
end;
writeln;
end;
end;
AVL programa tai dvejetainis medis, kuris pildomas naujais elementais, balansuojasi. Dvejetainis medis skirtas ten įdėto elemento paieškai. Jeigu į medį bus dedami elementai vienas po kito didėjantys, arba vienas po kito mažėjantys, tai medis turės vieną ilgą šaką, o jei bus dedami įvairūs elementai, tai jis bus šakotas bei trumpašakis ir bus greičiau vykdoma paieška. AVL medis - besibalansuojantis medis. Kuomet viena jo šaka pasidaro ilgesnė už bet kurią kitą 2 sąlyginiai vienetais, tai ji deformuojasi, vykdomas "posūkis": šaka ale nupjaunama, perlaužiama perpus, tada suklijuojama "V" raide ir pritvirtinama prie šakos pamato.
Taip atrodo programos interfeiso fragmentas, atlikus vieno skaičiaus įterpimą į AVL medį:
(dvejetas ir trejetas paraudoninti, neryškiai čia matosi)
Beje, formulę su DIV'ais tai galvojau ir testavau tikrai kokias 3 valandas. O medžio išspausdinimą padariau su lygiavimo klaida (buvo ne visai gražu), kurią sugalvojau kaip pataisyti tik kai prisėdau savaitę po atsiskaitymo.
Pateiksiu tik programos procedūras, kurios paruošia masyvą ir išspausdina medį pseudografiškai.
( uses crt;
type Pnode=^node;
node=record
l,r,t : Pnode;
n: integer;
end;
var root :Pnode; skait: array[1..255] of integer;
function auksciai( rod : Pnode) : integer;
var a1, a2 : integer;
begin
if (rod <> nil)
then
begin
a1 := auksciai(rod^.l) + 1 ;
a2 := auksciai(rod^.r) + 1 ;
if a1>=a2 then auksciai:=a1
else auksciai:=a2 ;
end
else auksciai := -1;
end; )
procedure isEilesMasyvas;
var te:Pnode; au,n,el,power,k,kn: integer;
begin
au:=auksciai(root);
power:=1; el:=0;
for n:=1 to au+1 do begin power:=power*2; el:=el+power div 2; end;
for n:=1 to el do
begin k:=1; kn:=n;
while k*2<=n do k:=k*2; te:=root;
while (kn<>1 ) and (k<>1) and (kn div k <>0) and (te<>nil) do
begin if kn mod k div (k div 2) = 0 then te:=te^.l else te:=te^.r; k:=k div 2; end;
if te <> nil then skait[n]:=te^.n else skait[n]:=0;
end;
writeln('stai isEilesMasyvo ',el, ' elementai: ');
for n:=1 to el do write(skait[n],' ');
end;
procedure piestiMedi(reiksme: integer);
var au,i,j,k,s,power,tarpai: integer;
begin
au:=auksciai(root);
s:=0;
writeln;
writeln('isspausdinu visus Medzio elementus: ');
for i:=1 to au+1 do
begin
power:=1;
for j:=au+1-i downto 1 do begin power:=power*2; end;
tarpai:=power*2-2;
power:=1;
for j:=1 to i do power:=power*2;
for k:=1 to power div 2 do
begin
for j:=1 to tarpai do write(' ');
if k>1 then for j:=1 to tarpai do write(' ');
s:=s+1;
if (skait[s]<10) and (skait[s]>0) then write(' ');
if skait[s]<>0 then
begin write(' ');
if skait[s]<>reiksme then write(skait[s])
else begin textcolor(12); write(skait[s]); textcolor(7); end;
write(' ');
end
else write(' ');
end;
writeln;
end;
end;
Kibirų pilstymas
Prieš porą savaičių dėstytojas uždavė studentams klausimą, už kurį buvo galima gauti papildomų taškelių neštis į egzaminą. Visi kursiokai ėmė spręsti ir bent penkias minutes tvyrojo tyla. Po to staiga net tryse priėjom sprendimą bemaž tuo pačiu metu, bet buvau truputį aplenktas.
Uždavinys toks:
Yra trys kibirai, kurių tūriai 10, 7, 2 litrai. Į pirmąjį įpilta 10 litrų magiško skysčio, kiti - tušti.
Užduotis: reikia neišpilstant magiško skysčio, gauti lygiai 5 litrus viename iš indų.
Jau tą pačią dieną kilo mintis parašyti programą, sprendžiančią tokį uždavinį, tačiau žinojau, kad su mano programavimo tempais, tai užtruks ilgai, tad atsidėjau laisvesnei dienai.
Šiandien per pusiaudienį suprogramavau. Pirmiausia kelias valandas rašiau į sąsiuvinį, ir galiausiai programa užėmė apie vieną pilną pusiau pribraukytą puslapį. Padėjęs pagrindus, persikėliau į PC.
Patiko tai, kad sugebėjau suprogramuoti viską gana lanksčiai, t.y. vartotojui yra leidžiama pasirinkti kibirų skaičius, kibirų tūriai, ir į kokius kibirus ir kiek jis norėtų pripilti skysčio, bei kokį vieną skaičių jam reikia gauti. Visa tai realizuota masyvais ir daug FOR ciklų, vienoje vietoje siekiančių net 4 ciklų "gylį" (i, j, k, k1);
Nepatiko tai, kad programa neieško geriausių pilstymo variantų. Ir dar labiau nepatiko, kad neieško visų pilstymo variantų, dėl ko negalima pasakyti ar ji veikia visais atvejais teisingai.
Dėstytojo uždavinį programa išsprendžia per 15 pilstymų, nors yra bent 2 greitesni būdai kaip gauti 5 litrus.
Taigi, čia programos kodas:
program LitrasSenLitrasTen;
label 0;
const NN=5; NNN=1000;
type WM = array[1..NNN,1..NN] of integer;
var w: WM;
v, x, t: array[1..NN] of integer;
i,j,k,k1,m,m1,m2 :integer; //skaitliukai
t1,t2 :integer; //temporary
N, gauti, def :integer;
total, tot, nutraukti :boolean;
procedure perpilti(a, b, bV: integer; var a1, b1: integer);
begin
if a>=bV-b then
begin
a1:=a-(bV-b);
b1:=bV
end
else
begin
b1:=b+a;
a1:=0
end;
end;
begin
writeln('RS 2011-06-06');
writeln('Programa: pilstymas is kibiro i kibira, kol gaunamas norimas turis');
writeln;
writeln('NE - 0, TAIP - kitas skaicius');
writeln('Norite ivesti savus parametrus?');
writeln('(Jeigu NE, tai programa veiks su DEFAULT parametrais: ');
writeln('Kibiru skaicius: 3, pirmojo V = 10, antrojo V = 7, treciojo V = 2');
writeln('Pirmame kibire yra 10 litru, kiti - tusti. Bandoma gauti 5 litrus.)');
readln(def);
if def = 0 then
begin
N:=3;
v[1]:=10; v[2]:=7; v[3]:=2;
x[1]:=10; x[2]:=0; x[3]:=0;
gauti:=5;
end
else
begin
writeln('Iveskite kibiru skaiciu');
readln(N);
writeln('Iveskite visu kibiru turius');
for i:=1 to N do readln(v[i]);
writeln('Iveskite visu kibiru turini');
for i:=1 to N do readln(x[i]);
writeln('Koki litru skaiciu norite gauti?');
readln(gauti);
end;
for i:=1 to N do
w[1,i]:=x[i];
m:=1; m2:=0; nutraukti := false;
write(0:3,'| ');
for i:=1 to N do write(x[i]:2,' ');
writeln;
repeat
begin
m1:=m;
// writeln('m1:=m; - ',m);
for i:=1 to N do
begin
0:
for j:=1 to N do
if (i<>j) and (x[j]<>v[j]) and (x[i]<>0) then
begin
// writeln('i ir j - ',i,' ',j);
// writeln('x[i],x[j],v[j] - ',x[i],' ',x[j],' ',v[j]);
perpilti(x[i],x[j],v[j], t1,t2);
// writeln('t1,t2 - ',t1,' ',t2);
for k:=1 to N do
if k in [i,j] then
if k=i then
t[k]:=t1
else
t[k]:=t2
else
t[k]:=x[k];
total:=true;
for k:=1 to m do
begin
tot:=true;
for k1:=1 to N do
tot:=tot and (w[k,k1] = t[k1]);
total:=total and (not tot);
// writeln('total, k - ',total,' ',k);
// readln;
end;
if total then
begin
write(m:3,'| ');
for k:=1 to N do
begin
x[k]:=t[k];
w[m+1,k]:=t[k];
write(x[k]:2,' ');
if k=N then writeln;
if t[k]=gauti then nutraukti:= true;
end;
m:=m+1;
goto 0;
end;
end;
end;
if m=m1 then m2:=m2+1 else m2:=0;
end;
until (m2=2) or (m>100) or (nutraukti);
if m2=2 then writeln('m2=2');
if m>1000 then writeln('m>1000');
if nutraukti then writeln('nutraukti');
readln;
end.
Uždavinys toks:
Yra trys kibirai, kurių tūriai 10, 7, 2 litrai. Į pirmąjį įpilta 10 litrų magiško skysčio, kiti - tušti.
Užduotis: reikia neišpilstant magiško skysčio, gauti lygiai 5 litrus viename iš indų.
Jau tą pačią dieną kilo mintis parašyti programą, sprendžiančią tokį uždavinį, tačiau žinojau, kad su mano programavimo tempais, tai užtruks ilgai, tad atsidėjau laisvesnei dienai.
Šiandien per pusiaudienį suprogramavau. Pirmiausia kelias valandas rašiau į sąsiuvinį, ir galiausiai programa užėmė apie vieną pilną pusiau pribraukytą puslapį. Padėjęs pagrindus, persikėliau į PC.
Patiko tai, kad sugebėjau suprogramuoti viską gana lanksčiai, t.y. vartotojui yra leidžiama pasirinkti kibirų skaičius, kibirų tūriai, ir į kokius kibirus ir kiek jis norėtų pripilti skysčio, bei kokį vieną skaičių jam reikia gauti. Visa tai realizuota masyvais ir daug FOR ciklų, vienoje vietoje siekiančių net 4 ciklų "gylį" (i, j, k, k1);
Nepatiko tai, kad programa neieško geriausių pilstymo variantų. Ir dar labiau nepatiko, kad neieško visų pilstymo variantų, dėl ko negalima pasakyti ar ji veikia visais atvejais teisingai.
Dėstytojo uždavinį programa išsprendžia per 15 pilstymų, nors yra bent 2 greitesni būdai kaip gauti 5 litrus.
Taigi, čia programos kodas:
program LitrasSenLitrasTen;
label 0;
const NN=5; NNN=1000;
type WM = array[1..NNN,1..NN] of integer;
var w: WM;
v, x, t: array[1..NN] of integer;
i,j,k,k1,m,m1,m2 :integer; //skaitliukai
t1,t2 :integer; //temporary
N, gauti, def :integer;
total, tot, nutraukti :boolean;
procedure perpilti(a, b, bV: integer; var a1, b1: integer);
begin
if a>=bV-b then
begin
a1:=a-(bV-b);
b1:=bV
end
else
begin
b1:=b+a;
a1:=0
end;
end;
begin
writeln('RS 2011-06-06');
writeln('Programa: pilstymas is kibiro i kibira, kol gaunamas norimas turis');
writeln;
writeln('NE - 0, TAIP - kitas skaicius');
writeln('Norite ivesti savus parametrus?');
writeln('(Jeigu NE, tai programa veiks su DEFAULT parametrais: ');
writeln('Kibiru skaicius: 3, pirmojo V = 10, antrojo V = 7, treciojo V = 2');
writeln('Pirmame kibire yra 10 litru, kiti - tusti. Bandoma gauti 5 litrus.)');
readln(def);
if def = 0 then
begin
N:=3;
v[1]:=10; v[2]:=7; v[3]:=2;
x[1]:=10; x[2]:=0; x[3]:=0;
gauti:=5;
end
else
begin
writeln('Iveskite kibiru skaiciu');
readln(N);
writeln('Iveskite visu kibiru turius');
for i:=1 to N do readln(v[i]);
writeln('Iveskite visu kibiru turini');
for i:=1 to N do readln(x[i]);
writeln('Koki litru skaiciu norite gauti?');
readln(gauti);
end;
for i:=1 to N do
w[1,i]:=x[i];
m:=1; m2:=0; nutraukti := false;
write(0:3,'| ');
for i:=1 to N do write(x[i]:2,' ');
writeln;
repeat
begin
m1:=m;
// writeln('m1:=m; - ',m);
for i:=1 to N do
begin
0:
for j:=1 to N do
if (i<>j) and (x[j]<>v[j]) and (x[i]<>0) then
begin
// writeln('i ir j - ',i,' ',j);
// writeln('x[i],x[j],v[j] - ',x[i],' ',x[j],' ',v[j]);
perpilti(x[i],x[j],v[j], t1,t2);
// writeln('t1,t2 - ',t1,' ',t2);
for k:=1 to N do
if k in [i,j] then
if k=i then
t[k]:=t1
else
t[k]:=t2
else
t[k]:=x[k];
total:=true;
for k:=1 to m do
begin
tot:=true;
for k1:=1 to N do
tot:=tot and (w[k,k1] = t[k1]);
total:=total and (not tot);
// writeln('total, k - ',total,' ',k);
// readln;
end;
if total then
begin
write(m:3,'| ');
for k:=1 to N do
begin
x[k]:=t[k];
w[m+1,k]:=t[k];
write(x[k]:2,' ');
if k=N then writeln;
if t[k]=gauti then nutraukti:= true;
end;
m:=m+1;
goto 0;
end;
end;
end;
if m=m1 then m2:=m2+1 else m2:=0;
end;
until (m2=2) or (m>100) or (nutraukti);
if m2=2 then writeln('m2=2');
if m>1000 then writeln('m>1000');
if nutraukti then writeln('nutraukti');
readln;
end.
Užsisakykite:
Pranešimai (Atom)