KYAN PASCAL¢¢ ②e&en) logick`ch problem+ - ZEBRA.¢ ╱V.LI③KA - Pardubice$¢¢¢ Na na&em ATARI XL/XE lze snadno @e&it logick[ probl[my uve@ejovan[ pravideln% nap@. v t`den)ku KV❎TY.¢¢ P@ekop)rujme si nejd@)ve soubory ZEBRAINI.O, ZEBRA.O a D1 na disketu s KYAN PASCALem ╱na n)( je alespo 270 sektor+ voln`ch a disketa obsahuje z*kladn) pascalskou knihovnu,t.j. soubor LIB$.¢ Z p@)kazov[ho @*dku KYAN PASCALu ╱zapnout po')ta' se stla'en`m OPTION!$ spust)me nejd@)ve prvn) soubor ¢ >D:ZEBRAINI.O¢a m+(eme ze slovn)ho zad*n) logick[ho probl[mu sestavit datov` soubor se zvolen`m jm[nem, nap@."D" nebo "D99" ╱min.1 znak a max.3 znaky, p@i 'em( je pot@eba, aby 1.znakem bylo velk[ D$.¢¢Pozn*mka: Pro za'*tek se vyhn%me ')slu D1, proto(e v tomto direktor*@i je soubor D1 uveden jako ilustra'n) p@)klad.¢¢Pot[ se automaticky ╱programov`m p@)kazem CHAIN .... $ odstartuje vlastn) pascalsk` program ╱ZEBRA.O$, kter` probl[m vy@e&) b%hem jedn[ desetiny minuty a( n%kolika minut.¢¢ Data lze zad*vat i z pascalsk[ho modu Editoru a b%(n% je ulo(it na disketu. Pak na kyanpascalsk` p@)kazov` @*dek nap)&eme:¢ $D:ZEBRA.O¢a t)m odstartujeme @e&en).¢¢ Jak se zad*vaj) data?¢¢ P@edem je nutno si uv%domit jakou strukturu m* ]loha. Logick` probl[m se zpravidla t`k* osob/jedinc+. Po'et jedinc+ ╱3 a( max.6$ odpov)d* po'tu sloupc+ v generovan[ tabulce jmen. Ka(d` jedinec/jm[no je ur'en po'tem ]rovn)/@*dk+ tabulky ╱op%t 3 a( max.6$. Jako p@)klad lze uv[st ur'en) 3 osob t@emi ]rovn%mi: rodn`m jm[nem, p@)jmen)m a bydli&t%m. Nutno tedy do 1. @*dku datov[ho souboru zadat 3 3 ╱po'et sloupc+ a po'et @*dk+/]rovn)$.¢ Logick[ ]lohy se skl*daj) z negativn)ch a positivn)ch konstatov*n). Tak nap@. v%tu: Jan se nejmenuje URBAN zad*me takto: 1Jan-2URBAN,¢ a v%tu ZRZEK bydl) v Brn% jako:¢ 2ZRZEK⇩3Brno.¢⇨)slice t%sn% p@ed jm[nem ur'uje po')ta'i ]rove jm[na, kter[ n*sleduje. Po')ta' nem+(e toti( v%d%t jestli kup@. Petr je rodn[ jm[no nebo p@)jmen).¢ Zadan* konstatov*n) po')ta' zpracov*v* do kd+ ╱110- a 021⇩$ a postupn% vypluje @*dky tabulky ╱3x3$:¢ Jan ....... .......¢ URBAN ZRZEK .......¢ Brno ....... .......¢V kdov[m ')sle @)d)c) znaky ⇩ a - jsou jasn[; po'et cifer odpov)d* po'tu @*dk+, maxim*ln) ')slice mus) odpov)dat po'tu osob/sloupc+.¢¢ Dal&) p@)klad pro kdov*n):¢Po'et sloupc+ - 4, po'et @*dk+ - 4; p@i'em(: 1-jm[no klubu, 2-st@ih vlas+ hr*'+, 3-barva vlas+,4-po@ad) klub+ v sout%(i. Jednoduchou v%tu: "za TATRAN hr*l rezav` hr*'" zakdujeme snadno:¢ 1TATRAN⇩3rezav[.¢Ze slo(it%j&) v%ty: "..kudrnat` hr*' se naklonil k blon⇦*kovi a @ekl mu, aby se pod)val, jak ten z DUKLY hlad) po ple&i hr*'e z dru(stva, kter[ bylo 'tvrt[.."¢vypl`vaj) tato konstatov*n):¢2kudrnat[-3blond ╱Kudrnat` nen) blond$¢2kudrnat[-1DUKLA ╱a nen) z DUKLY,$¢3blond-1DUKLA ╱stejn% jako blon⇦*k.$¢2ple&⇩44. ╱Ple&at` hr*' je 4.dru(stva;$¢1DUKLA-44. ╱pak tedy ani DUKLA,$¢2kudrnat[-44. ╱ani kudrnat`,$¢3blond-44. ╱ani blon⇦*k nebyli 'tvrt)$.¢p@)padn% i¢2ple&-3blond ╱to je ale u( konstatov*n) nadbyte'n[$.¢ Z uveden[ho p@)kladu se lze pou'it,¢jak serv)rovat po')ta'i nejr+zn%j&) konstatov*n).¢¢ Pokud se v ]loze vyskytuje po@ad) ╱nap@. klub+ v sout%(i, nebo startovac) ')sla a pod.$, pak dbejme z*sadn%, aby tyto ]daje byly uv*d%ny v posledn) ]rovni ╱viz 4.]rove v p@edch*zej)c)m p@)kladu.¢¢ Do tabulky jmen se mus) zadat je&t% ty ]daje, kter[ nebyly obsa(en` v p@edchoz)ch konstatov*n)ch. V p@edchoz)m modelov[m p@)pad% se to provede jednodu&e, nap@.:¢ 1Oto ╱zb`vaj)c) rodn[ jm[no v 1.]rovni je Oto$, nebo¢ 442. ╱2.po@ad) se dosud nevyskytlo v ⇩ a - konstatov*n)ch$.¢Kdybychom tyto ]daje neuvedli, pak m)sto v tabulce by bylo pr*zdn[ a v`sledek by nemohl b`t spr*vn% vyti&t%n.¢Kdybychom v&ak na druhou stranu uvedli konstatov*n) s p@ebyte'n`m ]dajem, kter` by se do ozna'en[ho @*dku neve&el:¢ 2MARVAN⇩3Praha a nakonec¢ 1Petr-2Marvan,¢pak po')ta' bude hl*sit p@ebyte'n` ]daj v x-t[m @*dku a vr*t) se na za'*tek zad*v*n): Marvan nen) tot[( co MARVAN$.¢¢ M*me tedy na disket% r+zn[ datov[ soubory ╱D, D0 a( D99$.¢¢ Odstartujeme zkompilovan` soubor ZEBRA.O. Na v`zvu si zvol)me ')slo datov[ho souboru a zp+sob jeho zpracov*n). Prakticky ihned se vyp)&e ╱pro kontrolu$ datov* tabulka a v nejjednodu&&)m p@)pad% kdovan[ prvky variac), kter[ vyhovuj) zad*n) ╱nap@.: 132 213 321 $ a slovn) @e&en) ]lohy. Bude-li tabulka schematicky vypadat nap@.takto:¢ a b c¢ A B C¢ 1 2 3 ,pak v`sledek bude n*sledovn`:¢ c B 1 ╱321$¢ a C 2 ╱132$¢ b A 3 ╱213$¢po')ta' v`sledek automaticky vzestupn% se@adil ╱proto(e v posledn)m @*dku vstupn) tabulky je po@ad) - t.j.')sla$.¢¢¢ Chceme-li poznat detailn%ji pr*ci po')ta'e ╱anebo sami budeme konstruovat Zebry$, nech*me si vypsat i kdy a prvky variac).¢ Kdy u( zn*me ╱kup@.: 1010- nebo 0403⇩$; vyp)&) se kdy v&ech zadan`ch konstatov*n) a jejich po'et.¢ K variac)m je nutn[ podat bli(&) vysv%tlen): Prvky variac) Q-osob U-t[ t@)dy s opakov*n)m ╱kde Q je po'et sloupc+ a U je po'et ]rovn), nap@. Q=4 a U=3$ jsou tyto:¢111 112 113 114 121 122 123 124¢131 . . . . . . 144¢¢211 . . . . . . .¢ . . . . . . . 244¢¢¢ .......... 444¢¢¢Celkov` po'et prvk+ t%chto variac) ╱s opakov*n)m ka(d[ ')slice$ je Q na U; co( v na&em p@)pad% je 64.¢Po')ta' generuje jeden prvek za druh`m a zji&④uje jestli neodporuje jednotliv`m konstatov*n)m. K tomu ilustraci:je-li jeden z kd+ konstatov*n) nap@. 201- pak se vy&krtaj) tyto prvky: 211,221,231,241;¢nebo kd 034- nep@ipust) existenci prvk+: 134,234,334.¢U pozitivn)ch konstatov*n) je tomu naopak: kd 110⇩ vy&krt*v* 12X,13X,14X, ale nejen to, je&t% dal&) prvky mus) b`t &krtnuty, a to 21X,31X a 41X, kde X nahra(uje v&echny cifry, 1 a( 4.¢Ty prvky, kter[ po "&krt*n)" zbydou se vyp)&).¢V konkr[tn)m p@)pad%:¢Q=3, U=4¢1001⇩ 2100- 0210- 0302⇩ 0023- 0130⇩¢Po'et kd+ 6¢1131 1221 2312 2322 3133 3312 3322¢Po'et prvk+ 7.¢S t%mito prvky prov*d) po')ta' kombinace:¢Vezme 1.prvek 1131 a p@ejde na skupinu prvk+ za')naj)c)ch 2...¢Vezme op%t 1.prvek na r*n%, 2312 a testuje jestli v koresponduj)c)ch pozic)ch nejsou stejn[ ')slice:¢1131¢2312. Je to v po@*dku, tak(e si vyt*hne dal&) kod ze skupiny 3... . Te⇦ mus) ov&em testovat odli&nost cifer v p@)slu&n`ch pozic)ch v&ech t@) prvk+:¢1131¢2312¢3133. Tady ale posledn) kd nevyhovuje ve 2. a 3.pozici, proto mus) ')st a testovat dal&) prvek, 3312 ╱ten nevyhovuje ve t@ech pozic)ch, stejn% jako n*sledn` prvek 3322$.¢Proto, (e u( dal&) prvek 3.skupiny neexistuje, vrac) se do skupiny 2 a tam zvol) dal&)ho 'lena, 2322. Jeliko( se tento prvek sn*&) s 1.prvkem ╱1131$, p@ech*z) do t@et) skupiny prvk]. Prvn) prvek t[to skupiny ╱3133$ nevyhovuje, ale ani dal&) ╱3312$ a stejn% tak se ned* pou()t ani posledn) prvek ╱3322$. Proto mus) b`t opu&t%n p@edchoz) prvek ╱2322$; jeliko( v&ak nic jin[ho ve skupin% 2... nen), mus) se opustit i dosud platn` prvek ve vy&&) skupin%, tedy prvek 1131 a nahradit dal&)m:1221.¢ A te⇦ to u( pob%():¢ 1221 2312 a 3133. ¢Tento kdov` v`sledek se vyp)&e slovn% podle tabulky jmen.¢ Je&t% v&ak pr*ce po')ta'e nen) u konce. Mus) toti( zjistit, jestli na&el jednozna'n` vysledek, nebo, je-li mo(n`ch v`sledk+ v)ce. To se stane tehdy, kdy( ]loha nen) zad*na perfektn%, nebo kdy( autor Zebry zad*n) zkomplikoval jinak. Z v)ce v`sledk+ si tedy bu⇦ mus)me vybrat sami, nebo tuto pr*ci sv%@it op%t po')ta'i, kter[mu mus)me ov&em zadat dal&) data. ②ada ]loh pou()v* v jedn[ ]rovni ')seln[ po@ad) osob. Autor ]lohy pak zad* vhodnou relaci, tedy ur'), kter* ze dvou osob m* men&) nebo v%t&) ')slo po@ad). My p@i zad*v*n) dat budeme dodr(ovat pravidlo, (e ')sla po@ad) budou v(dy v posledn)m @*dku/]rovni.¢Tak nap@. takov[to zad*n):¢...mu( z Brna ╱3.]rove$ startoval p @ e d chemikem ╱2.]rove$ ... zakdujeme t)mto relativn)m konstatov*n)m:¢ 3Brno╱2chemik.¢Nebo jin` p@)klad:¢...b)l` ╱3.]rove$ domek stoj) v e d l e zelen[ho domku... kdovan%:¢ 3b)l`o/o3zelen` ╱skupina "o/o" m* b`t znak pro procento$.¢¢ Po')ta' pou()v* relativn) konstatov*n), kter* rozpozn* podle uveden`ch @)d)c)ch znak+ ╱lev* z*vorka a procento$, p@i posuzov*n) prvkov`ch kombinac) v prvn) a( posledn) t@)d%. Vylou') - v prvn)m p@)pad% - v&echny kombinace kde by startuj)c), kter` bydl) v Brn%, m%l m)t na startu vy&&) ')slo ne( chemik. Ve druh[m p@)pad% pak v kombinaci v`sledn`ch kod+ kdy b)l` domek bude m)t ')slo nap@. 3 pak nep@ipust), aby zelen` domek m%l jin[ ')slo ne( 2 nebo 4 ╱ t.j. 3 plus minus 1$; tedy bud kombinaci prvk+ ponech* a vyp)&e, nebo mus) hledat dal&) mo(nosti.¢¢ Do programu Zebra lze zabudovat i dal&) typy relativn)ch konstatov*n), jako je t@eba toto: vedle sebe jsou m)sta lich*, naproti sud*, tak ,jak je tomu ve vlakov[m kup[, a p. Takov[to ]lohy v&ak nejsou p@)li& 'etn[ a program by se n*m moc rozrostl, a dokonce by neve&el do opera'n) pam%ti po')ta'e A 800 XL.¢¢ Z*v%rem porovn*me rychlosti v`po'tu t%chto logick`ch ]loh na r+zn`ch b%(n`ch po')ta')ch. Pro srovn*n) byla vybr*na klasick* ]loha, podle n)( byly tyto logick[ probl[my nazv*ny: Kdo pije vodu a kdo vlastn) zebru?:¢ ⑤loha m* 5 sloupc+ a 6 ]rovn), je zad*na pomoc) 15 konstatov*n) a 5 relativn)ch konstatov*n). Jej)m @e&en)m je 99 prvk+ variace, z nich( lze vykombinovat 452 mo(nost). Spr*vn* je ov&em jenom jedna, a to 33.mo(nost.¢Tuto 33.mo(nost vyp)&e KYAN PASCAL na obrazovku za 5 minut ╱dal&)ch p%t minut trv* ne( ov%@) zb`vaj)c)ch 420 mo(nost)$;¢u &koln)ho po')ta'e IQ 151 s AMOS PASCALEM jsou uveden[ doby dvakr*t v%t&) ╱10 a 20 min$;¢TURBOPASCAL V 4.0 u &estn*ctibitov[ho TNS /AT vy@e&) probl[m za 11 a 21 sekund ! ╱ s jinou pracovn) frekvenc) pak se bl)() prvn) hodnota k 5 sekund*m$.¢V BASICU @e&it Zebru by bylo trestuhodn`m mrh*n)m strojov[ho 'asu; jedin% snad by to &lo kombinac) BASICU se stroj*kem ╱pak ale PASCAL je jednodu&&)$.¢Objektivn% je v&ak nutno konstatovat, (e pro @e&en) takov`chto a podobn`ch logick`ch probl[m+ bude z@ejm% nejvhodn%j&) jazyk PROLOG, jen( na minipo')ta'i ADT 4100 vytiskne tuto ]lohu na pap)r za 16,5 s.¢¢ Na z*v%r si zkusme zakdovat toto slovn) zad*n) ╱uve@ejn%n[ p@ed 'asem v t`den)ku KV❎TY pod n*zvem Odjezdy autobus+$:¢ M*te ur'it po@ad), v n%m( odjely t@i autobusy , a p@ipojit jm[no @idi'e, c)lovou stanici a ')slo n*stupi&t%.¢ Rodn* jm[na: Old@ich ╱8.
