KLASICKÁ ÚLOHA
Pro vás co se chcete přiučit něco zajímavého tu mám jeden
klasický příklad z programování. Tady máte jeho znění: Najděte
nejkratší cestu jezdce (šachového koně) z jednoho místa šachovnice na
druhé.
Ukážu vám, jak jsem ji vyřešil já a popíšu vám většinu svých
chyb, které jsem při tom napáchal, protože chybami se člověk učí.
Obecný algoritmus
Četli-li jste v minulé Výhni články o umělé inteligenci, měl by
vás napadnout algoritmus. Jeden vám tu popíšu, asi není nejlepší, ale
je snadno srozumitelný. Cestu jezdce si mohu představit jako nějaký
takovýhle strom. (jedu např. z bodu a1 do bodu c1)
a1
+-----+------+
b3 c2
+--+--+--+--+ +--+--+--+
a5 c5 d4 d2 c1 a3 b4 e3 e1
. .
. .
Každá větev stromu by se nakonec ke koncovému bodu dostala, ale mně
jde jen o nejkratší cestu takže rozvinu strom prozkoumám
nenarazím-li na koncový bod, a když ne rozvíjím strom dál.
Komunikace s uživatelem
Users interface (uživatelský meziksicht) je důležitou stránkou
programu a mnohdy je jeho nejdelší částí. Snažil jsem se ho udělat
co nejkratší a nejhezčí. Idea: šachovnice a po ní budu moci jezdit
kursorem a vybrat si políčka.
Nakreslit šachovnici: Dá se to udělat i takhle.
void prchebo{
byte c,d;
for (c=0;c<8;c+=2){
gotoxy(SX,SY+c);
printf("%i ",8-c);
gotoxy(SX,SY+c+1);
printf("%i ",7-c);
}
gotoxy(SX,SY+c);
printf(" a b c d e f g h\n");
}
Ale mně se to líbí jinak. Vím-li, že když sečteme souřadnice pole a
dostaneme liché číslo je políčko černé, dostaneme-li číslo sudé je
políčko bílé (lichost určíme podle nejnižšího bitu fcí. iseven).
Takže radši použiju tyto procedurky.
//vybarvi jedno policko
void fara(byte x, byte y){
const char pat[2][4]={" \x0"," \x0"};
gotoxy(x*3+SX+1,y+SY);
cprintf("%s",pat[iseven(x+y)]);
}
//kresli sachovnici
void prchebo(){
byte c,d;
textcolor(TC);
for (c=0;c<8;c++)
for (d=0;d<8;d++){
gotoxy(SX,SY+c);
printf("%i",8-c);
fara(c,d);
}
gotoxy(SX,SY+c);
textcolor(LIGHTGRAY);
cprintf(" a b c d e f g h\n");
}
Neni to rychlejší ani kratší, ale mně to připadá hezčí, a protože
programuju pro radost, napsal jsem to takhle.
A teď kursor. Jestli jste si nevšimli, tak proceduru na kreslení
kursoru už máme. Ano uhodli jste. Zavoláme fci. fara se změněnou
barvou písma. Takže fce. repric jen zkontroluje údaje, změní
souřadnice a zavolá fci. fara. Komunikaci s klávesnicí zajišťuje fce.
direc, která po stisknutí ENTERu vrátí nulu a po stisknutí kursorové
klávesy změní proměnné dx, dy. Avšak s kursorovými klávesami bývá
problém, protože jak jistě většina z vás ví, stisknutí šipky je
signalizováno nulou a následným znakem, kterým může být K, H, M nebo
P. Takže fce. direc může vypadat nějak takhle.
//cte klavesy hlida sipky a ENTER
byte direc(signed char * dx,signed char * dy){
byte c,n;
do{
c=getch();
if (c==13) return 0;
else if (c==0) {
c=getch();
switch (c) {
case 'K':*dx=-1;
break;
case 'H':*dy=-1;
break;
case 'M':*dx=1;
break;
case 'P':*dy=1;
break;
}
if (*dx+*dy!=0) c=1;
}
}while (c>1);
return 1;
}
Ale mně se to zase nelíbilo. Vždyť ty 4 písmena musí mít mezi sebou
nějaký vztah. A opravdu po probdělé hodině dějepisu jsem ho objevil.
Odečtete-li od kódu klávesy 76 tak získáme nějaké číslo. Je-li to 1
nebo -1 přiřadí se dx (1=doprava, -1=doleva), je-li toto číslo 4 či
-4 přiřadí se po vydělení 4mi do dy (-4=nahoru, 4=dolu). Touto fintou
se fce. direc výrazně zjednoduší.
//cte klavesy hlida sipky a ENTER
byte direc(signed char * dx,signed char * dy){
int c;
c=getch();
if (c==13) return 0;//je to ENTER?
else
if (c==0) {
c=getch();
c-=76;
if (abs(c)==4) *dy=c/4; //je +-4?
if (abs(c)==1) *dx=c;
}
return 1;
}
ALGORITMUS byl popsán už výše, ale s jeho praktickým využitím byly
drobné problémy.Idea: Šachovnici si představím jako dvourozměrné pole
8*8. Budu do něj označovat pole, na která už jsem se dostal, a když
nenajdu hledaný bod rozšířím hledání dál.
Postupoval jsem podle tohoto návodu, ale narazil jsem.
Problém 1. Jak poznám konec větve (přeci nebudu celý strom
prohledávat znovu a znovu)
Řešení :K označení poslední části větve přičtu konstantu (80),
a při rozšiřování stromu ji odečtu.
Problém 2. Jak při nalezení konce najdu cestu zpátky.
Řešení :K označení prohledaného políčka použiju kód políčka, ze
kterého jsem se na něj dostal. Např. bod a1 má kód 00, b3
12 (číselný kód zmenšený o 11 => a1 = 11;11 - 11 = 00)
První (nulté) pole má kód 78, koncové 79.
Problém 3.Při vyhodnocování bere některé právě rozšířené větve jako
ty, které má vyhodnocovat => nenajde nejkratší cestu.
Řešení :Rozšiřování ukládat do jednoho pole, vyhodnocovat jiné. Po
vyhodnocení je ale musíte sjednotit.
A teď už zbývá vyznačit nalezenou cestu. Protože jsem si chytře
nechal uložit kód políčka, ze kterého byl cíl nalezen a v tomto
políčku je uložen kód předešlého, mohu klidně dojí až do nultého bodu.
Kosmetické úpravy
Skrytí originálního kursoru bylo nutné, protože svým hloupým
blikáním dost znervózňoval. Kursor byl odklizen přerušením 10h ve
fci. hscur.
Barvy můžete změnit přenastavením maker TC, CC na začátku.
A nakonec k nejčastějším chybám. Prohazuju souřadnice. x značí
sloupec, y řádek, takže když čtete z pole musíte číst takto
chebo[y][x]. Další error byl, když jsem měl pole vyplněno nulama.
Program sice fungoval, ale jen někdy, protože číslo 0 značí první
pole vlevo nahoře (dělalo to nádherný věci)
Poznámky: Omlouvám se, že neumim moc vysvětlovat, ale ono to neni tak
jednoduchý. V jedné knize to přirovnávali tak, že to je jako
popisovat symfonickou báseň slovy. Takže vy, co nechápete moje
vysvětlení, se laskavě koukněte do not (zdrojáku) a musí vám to být
jasný.
Nechápete-li princip zavolejte program(tímle ho vyexportujete)
s jakýmkoli parametrem a on vám bude ukazovat co dělá (Vypíše obsah pole
chebow).
HIPP
(Naskytnou-li se problémy nebo budete-li mít dotazy čí poznámky pište
a ptejte se)
výheň