Tehnika programiranja BACKTRACK

Tehnika programiranja BACKTRACK

Važna oblast i važna i specifična i univerzalna  tehnika proramiranja   je opisana u prilogu:

bektrek-NikolaDojcinovic     , iz priloga:

“Suština bektreka, kao načina programiranja, je veoma zanimljiva i njene tajne se mogu nazresti iz samog naziva bektrek (back-pozadi; track-staza). No ipak, naziv bektrek ne možemo prevesti bukvalno, te se on kod nas najčešće prevodi kao pretraga sa vraćanjem. Sam postupak programiranja se vrći dosta postupno, korak po korak. Za odredjivanje sledećeg koraka u cilju dolaska do delimično krajnjeg i krajnjeg rešenja na raspolaganju za taj korak imamo više mogućnosti, za koje mi unapred ne možemo znati koja vode do rešenja, a koja su samo utopijski pravci koji ne vode do krajnjeg rešenja. Za sledeći korak u odredjivanju rešenja uzima se jedna od preostalih mogućnosti i u odnosu na nju se rešenje odredjuje od kraja. Ukoliko ne postoji sledeći korak koji zadovoljava zadate uslove, vraća se korak unazad (back) i kao sledeći korak uzimaju neka druga solucija. Kraj programa je situacija kada su sve moguće putanje isprobane i ne postoji više ni jedno rešenje koje može zadovoljiti uslove zadatka. Samo rešenje problema bektrekom predstavqa, na neki kačin, jednu putanju (track) koja se sastoji od niza adresa polja koja pokazuju jadna na drugu.”

Ovo  je još jedana provera spremnosti za buduće takmičare, morate biti u stanju da sami savladate lekciju iz priloga. Mali mogući problem sa fontovima u prilogu biće usko razrešen.

Zadaci uz ovaj post:

Japanski problemi SUDOKU su postali vrlo pouplarni. ima ih gotovo u svakoj novini ali i u posenim publikacijam za zabavu. Tamo se moćete o tome informistai. S druge strane nisu retki problemi s greškama koji se objavljuju, pa da im pomognemo. Zadaci:

1. Napisati program i algoritam koji u sastavljenom SUDOKU problemu otkriva grešku.

2. Kako  broj zadatah brojeva u SUDOKU problemu predstavlja i težinu samog problema (sami odgovorite zašto) napisati program i algoritam koji koji za zadato n (25<= n <= 30) formira SUDOKU problem bez greške.

3. Napisati algoritam i program koji za šahovsku figuru koja se unosi pocetnim slovom:  p-pešak, s-skakač,l-lovac, t-top, d-dama,k-kralj  i poziciju na kojoj se nalazi ta figura :primer a4, b3… na izlazu  daje pregled polja koja predstavljaju moguće poteze unete figure. Pregled polja sortirati u rastući redosled.

Rešenja slati kao što je već više puta objašnjeno.

Oranizacija takmičenja

KAKO SE TAKMIČI
===============

Najčešća organizacija zadaci-pregledavanje:
Dobijate TEKST zadatka sa slikama i eventualnim dodatnim objašnjenjem. Dobijate OPIS (izgled) ULAZNE datoteke (PRIMER)  sa TEST podacima
ZAD1.DAT  ( 1 – broj zadatka)  i  ZAD1.RES,  IZLAZNA DATOTEKA sa primerom ( TEST resenje).
Program koji napisete (EXE verzija, u istom folderu sa datotekom zadatka-ZAD1.DAT),  pre svega je potrebno da OD TEST PRIMERA daje kao izlaz ZAD1.RES koji je  isti kao u test primeru.
Program se TESTIRA NA 10 TEST PRIMERA ZAD10.DAT – ZAD19.DAT koji se preimenujuu ZAD1.DAT,  dobija  ZAD1.RES ( x – broj test primera ) i to se uporedjuje sa resenjem ZAD1X.RES .  Uporedjivanje mozete izvrsiti iz Commandera opcijom uporedjivanja dva fajla “Compare by content” )  u meniju  Commandera u “File”  .

Evo uputstva za pregledavanje zadataka sa takmičenja  iz 2006. godine koje se objavljuje uz odobrenje sa zvaničnog sajta takmičenja. Promene, danas, su  samo u automatizaciji pregledavanja.

“Тестирање такмичарских решења изводите користећи тест-примере који се налазе на дискети. На дискети се налазе архива TestPr.ZIP. У архиви се налазе фолдери Zad1, Zad2, Zad3, Zad4 и Zad5. У тим фолдерима се налазе датотеке ZADX1.DAT до  ZADX0.DAT и ZADX1.RES до ZADX0.RES (где  је X, 1 или 2 или 3 или 4 или 5 , и то се односи на редни број задатка). У првим датотекама су улазни подаци за задатке, а у другим решења за одговарајући задатак (како симбол непосредно испред тачке може бити било која цифра од 1 до 0, има укупно 10 тест примера за сваки задатак). Поред тога у фолдерима се налазе програми CheckerX (где  је X, 1 или 2 или 3 или 4 или 5 , и то се односи на редни број задатка). Они служе за проверавање исправности такмичаревог резултата (решења). Потребно је да датотеку са улазним подацима прекопирате у датотеку чије име се поклапа са именом које је наведено у поставци задатка, покренете такмичичарев програм. Затим покрећете програм CheckerX (где  је X, 1 или 2 или 3 или 4 или 5) тако што куцате CheckerX ulaz izlaz tacnor, где је ulaz име улазне датотеке, izlaz име излазне датотеке и tacnor име датотеке у коме је тачно решење (то је датотека са тачним решењем и налази се на дискети). На пример, ако тестирате први тест пример за трећи задатак (улазни подаци су у датотеци zad31.dat, а тачно решење је у zad31.res) куцаћете команду checker3 zad3.dat zad3.res zad31.res. Овај програм ће испитати да ли је такмичарево решење добро и исписати колико такмичар добија поена у датоетку tmp.txt. Осим тога, број освојених поена ће бити исписан и на екрану. Водите рачуна и временском ограничењу за извршавање такмичаревог програма.

При тестирању програма морате прво проценити колико је рачунар на коме тестирате спорији или бржи од рачунара према коме је комисија одредила време извршавања. У прилогу вам шаљемо датотеку speed.zip у којој је програм speed.exe. Ако покренете тај програм он ће одредити којим фактором треба да множите временско ограничење из поставки проблема да бисте добили максимално време извршавања такмичарских програма на рачунару на коме тестирате такмичарске програме.”

Još jedna prilika da se proverite u ovoj PREDPRIPREMI za takmičenje. Dva zadataka sa takmičenja, zadaci su algoritamski vrlo zanimljivi:

Okr0506_Zad_1

Rešenja zadataka  slati kao što je već objašnjeno u prethodnim postovima. Evo i  priloga SINTAKSNA I ALGORITAMSKA NOTACIJA koji može pomoći kod dostavljanja algoritama rešenja zadataka.

SINTAKSNA I ALGORITAMSKA NOTACIJA

Takodje je dobrodošao svaki predlog besplatnog softvera za crtanje algoritama, kako bi smo izabrali najprihvatljivije rešenje za ovu pripremu.

Organizacija PRIPREME

Organizacija PRIPREME

Prvih pet postova ovog bloga su prilika da se što bolje upoznamo sa znanjima i metodama rešavanja zadataka na ovom elitnom takmičenju. Time će potencijalni takmičari moći da procene  da pored zanimljivosti i izazova koje nosi učešće na takmičenju bi trebalo  i očekivati i ozbiljan rad i ozbiljno vreme angažovanja koje će možda ugroziti i redovne obaveze budućih takmičara. Odluka se mora doneti oprezno i odgovorno i naravno može se odustati u bilo kojoj fazi pripreme.

KAKO RADIMO
============

Prava priprema će početi šestim postom, koji se predvidja za 12.12.2011.god.
Planirano je da se najmanje dva zadatka kompletno reše ( algoritam (pseudo kod) i program (source i exe)) u toku jedne nedelje  i to zadaci sa prethodnih takmicenja ili neki posebni zanimljivi zadaci. 2 zadatka nedeljno su obaveza bloga , a broj zadataka zavisiće i od aktivnosti članova grupe koji mogu  neograničeno da postavljaju i rešavaju odgovarajuće zadatke. Do sada su postavljena  dva  zadatka i  zadatak  povezivanja zadataka sa takmičenja sa oblastima takmičenja koja se koriste u tim zadacima. Naravno prednost
imaju resenja ucenika.
U koliko do šestog posta na ovom blogu  ne stignu resenja učesnika u  prpremi postavljenih zadataka, resenja će na blog postaviti organizator ove pripreme.
Kako bi trebalo dostavljati resenja:
Rešenjas dostavljati u komentarima bloga, source code, i eventualno neke zanimljive beleške, a KOMPLETNO REŠENJE sa algoritmom i exe fajlom rešenja( ekstenziju exe preimenovati u jpg, zbog slanja e-poštom) na  e-mail   djs53@yahoo.com

Algoritamski blokovi-jezik

1.  Jako je poželjno dostaviti ALGORITAM rešenja ( Prema algoritamskim blokovima na slici AlgoBlokovi.jpg ali je moguće rešenja dostavljati i u drugim algorittamskim  notacijama ) 
zato što se pojednostavljuje rešavanje zadatka u drugim programskim jezicima u odnosu na jeziku kojem je resenje poslato.
2. Uz algoritam, programe dostavljati obavezno u SORCE i EXE verziji. Programski jezici C, C++, PASCAL – zvanicne verzije takmicenja
3. Ocekuju se resenja ucenika,  i dostavljaju se samo NOVA resenja, različit algoritam, i/ili programski jezik u kojem rešenje već nije dostavljeno i objavljeno. Naravno,  i ISPRAVKE osporenih poslatih resenja  ali sa preciznim dokazom zasto je poslato resenje pogresno.
4. Takodje je POZELJNO pogledati resenja na www.yuoi.nis.edu.rs , za zadatke sa tog sajta kao stručno odabrana i proslediti ih ovde za blog sa uradjenim algoritmom ili preprogramirana na drugi programski jezik koji ovde koristimo.

Paradigmatični zadaci u pripremi za takmičenje

Paradigmatični zadaci u pripremi za takmičenje iz programiranja
po oblastima za srednjoškolska takmičenja iz programiranja U Srbiji
– OKRUZNO TAKMICENJE

Okružno Takmičenje 2006.

Oblasti za okružno takmičenje, prema zvaničnom sajtu TAKMIČENJA IZ PROGRAMIRANJA Srbije, prema PRAVILNIKU sa sajta:

Okružno takmičenje
Jednostavne strukture podataka
(slogovi, nizovi, stringovi, matrice, liste, skupovi)
Jednostavni matematički postupci
(sumiranja, brojni sistemi, prosti brojevi, Euklidov algoritam)
Rekurzija, bektrek, kombinatorna prebrajanja
Operacije sa velikim brojevima
Elementarni algoritmi za sortiranje
(selection sort, insertion sort, bubble sort, counting sort)
Predstavljanje osnovnih geometrijskih objekta
(tačke, duži, prave, kruznice), jednostavni postupci nad njima (nalaženje preseka, udaljenosti, uglova), analitička geometrija

ZADATAK:
Pronadjite i odaberite na INTERNET-u lekciju-lekcije Po svakoj oblasti i u komentaru objavite te linkove odmah ispod navedene oblasti i tako formirajte svoj predlog literature za pripreme.
U okviru istog komentara medju Zadacima na sajtu TAKMIČENJA IZ PROGRAMIRANJA pronadjite bar po jedan zadatak koji predstavlja odredjenu oblast takmičenja za OKRUŽNO i taj zadata dodajte ispod oblasti u svom komentaru, navodeći godinu i takmičenje na kom je zadatak postavljen. Primer:

1)Jednostavni matematički postupci
(sumiranja, brojni sistemi, prosti brojevi, Euklidov algoritam)
literatura:
Naslovl_1 , http://www.link_1.ext
Naslov1_2 , http://www.link_2.ext
…
Naslov1_n , http://www.link_n.ext

zadatak sa takmičenja: Tekst zadatka… , OKRUŽNO 2007

i tako za sve oblasti…

Ne samo što ćete do kraja razjasniti potrebna znanja za takmičenje i osnovne primene tog znanja u zadacima već stvarate i dobru pripremnu bazu znanja za takmičare sledećih generacija.

Pripreme za takmičenje iz PROGRAMIRANJA

TAKMIČENJA IZ PROGRAMIRANJA

Pripreme za OKRUŽNO takmicenje

iz PROGRAMIRANJA

Elitno takmicenje iz programiranja srednjoškolaca Srbije veoma dobro i sasvim kompletno je predstavljeno i na WEB-u:  www.yuoi.nis.edu.yu                 logo by Igor Antolović

Pravilnik srednjoškolskih takmičenja iz programiranja

Možete preuzeti pravilnik kao poseban fajl:  pravilnik takmicenja iz programiranja.pdf    , iz pravilnika KATEGORIJE TAKMIČENJA:

Takmičari su podeljeni u dve kategorije: “A” i “B”. Razlika između kategorija je u zadacima koje takmičari rešavaju i u granici prolaznosti na sledeći nivo takmičenja. Svi takmičari koji su učenici odeljenja koja rade po programu matematičke gimnazije takmiče se u “A” kategoriji, dok takmičari koji su učenici ostalih odeljenja, mogu da biraju u kojoj će se kategoriji takmičiti.

Na BLOGU  će se obraditi pre svega program (iz pravilnika) za okružno takmicenje:

Okružno takmičenje

• Jednostavne strukture podataka (slogovi, nizovi, stringovi, matrice, liste, skupovi)
• Jednostavni matematički postupci (sumiranja, brojni sistemi, prosti brojevi, Euklidov algoritam)
• Rekurzija, bektrek, kombinatorna prebrajanja
• Operacije sa velikim brojevima
• Elementarni algoritmi za sortiranje (selection sort, insertion sort, bubble sort, counting sort)
• Predstavljanje osnovnih geometrijskih objekta (tačke, duži, prave, kruznice), jednostavni postupci nad njima (nalaženje preseka, udaljenosti, uglova), analitička geometrija

Pored kategorija takmičenja  i programa u praviniku možete pogledati:

Sadržaj

Sadržaj
Uvod
Takmičari
Opšta pravila
Nivoi takmičenja

Okružno takmičenje
Državno takmičenje
Srpska informatička olimpijada
Izborno takmičenje

Zadaci
Programsko okruzenje
Tipovi zadataka

Standardni zadaci
Interaktivni zadaci
Zadaci sa poznatim ulazom

Program takmičenja

Planirano je da se najmanje dva zadatka kompletno reše ( algoritam (pseudo kod) i program (source i exe)) u  svakom postu na blogu, i to zadaci sa prethodnih takmicenja ili neki posebni zanimljivi zadaci. Broj zadataka zavisice i od aktivnosti članova grupe koji mogu neograniceno da postavljaju i rešavaju odgovarajuce zadatke. Koriste navedeni programski jezici u Pravilniku.
S obzirom na ALGORITAMSKU osnovu zadataka takmcenja, prevodjenje
resenja prog.jezik1 – prog.jezik2 ne bi trebalo da predstavlja problem. Zato je uz rešenje zadtka potrebno i obavezno poslati algoritamsko rečenje koje možete nacrtati u programu po sopstvenom izboru. Očekujemo da eventualno i predložite neki bespltni softver za crtanje algoritama tako da bi unificirali najbolje rešenje.

BLOG je namenjen srednjoškolcima opštine Leskovac kao pomoć i za oživljavanje uspešne  tradicije leskovačkih talenata. Naravno, u radu BLOGA mogu učestvovati svi zainteresovani.

Proverite svoju spremnost da dalje pratite objave na blogu preko sledecih zadataka:

1. Zadatak  (zanimljivi zadaci)
Ucitava se n i toliko celih brojeva.Stampati najveci parni.

2) Zadatak  (zanimljivi zadaci)
U nekoj oblasti N gradova nalaze se na kruznom putu (N>2).Rastojanja izmedju susednih gradova redom se smestaju u niz A duzine N,tako da pocetni element niza sadrzi rastojanje izmedju prvog i drugog grada, sledeci izmedju drugog i treceg i tako dalje, dok poslednji element niza sadrzi rastojanje izmedju poslednjeg i prvog grada. Posto je put kruzni, izmedju svaka dva grada postoje dve putanje. Potrebno je za svaki moguci par gradova naci duzinu krace putanje izmedju njih i ove duzine smestiti u matricu R dimenzija NxN (matrica je simetricna u odnosu na glavnu dijagonalu, na kojoj se nalaze nule). Napisati program, koji ucitava broj gradova N, formira niz A i u njega ucitava rastojanja,a zatim formira mtricu R na opisni nacin.Zatim,sadrzaj te matrice treba ispisati na glavnoj izlaznoj jedinici,vrstu po vrstu. Pretpostaviti da su sva zadata rastojanja nenegativna.

Resenja slati u komentarima i/ili  na e-mail sdjs53@yahoo.com
( algoritam (ili pseudo kod) i program  (source kod))

KORISNI LINKOVI

ZVANIČNI SAJT TAKMIČENJA IZ PROGRAMIRANJA
PRIPREME I PREDTAKMIČENJA IZ PROGRAMIRANJA