home *** CD-ROM | disk | FTP | other *** search
/ PC World 2002 December / PCWorld_2002-12_cd.bin / Software / Komercni / Baltik / katB.exe / katB / BACKTRAQ / BACKTRAQ.SGP < prev    next >
Text File  |  2002-09-28  |  16KB  |  290 lines
  1. SGPC   5.05 032#000001154 20.08.2002 12:54:57                                    StructNo 2   2
  2. # include <sgpbalt.h>
  3. # include "backtraq.glb"
  4. # include "backtraq.mod\moduly.inc"
  5.  
  6. // Globální makra
  7. -o1-Globals
  8. -c1-Globals
  9. ===Globals
  10. /*-hf(*/
  11. /*-hf-*/
  12. void Backtrack( void )
  13. /*-hf-*/;
  14. void VolbaModulu( void )
  15. /*-hf-*/;
  16. void main( void )
  17. /*-hf)*/;
  18. ;-h---------------------------------------------------------------------------
  19. void Backtrack( void )
  20. -s--Backtrack                                                                   ■   2  -2  -9   3
  21.                                   Backtrack
  22.                                       #1
  23.                              _____Opakování______
  24.                       ___Vyhovuje?____     Hledat~dál?
  25.                       /1             /      /3      /
  26.                      Ano             Ne     Ne     Ano
  27.             _Dalτí~nebo~nalezeno?          e!
  28.             /2                  /
  29.  _________Dalτí_________     Nalezeno
  30. P²ed     Backtrack     Po      d!
  31. a!          b!        c!
  32. -o1----------------------SEZNAM OPERAC╓------------TENTO ⁿ╡DEK NEM╖NIT!-------
  33. a AktivníModul->Dalτí¼lánek_P²ed();
  34. b Backtrack();
  35. c AktivníModul->Dalτí¼lánek_Po();
  36. d AktivníModul->Nalezeno();
  37. e return;
  38. -c1----------------------SEZNAM PODM╓NEK-----------TENTO ⁿ╡DEK NEM╖NIT!-------
  39. #1 // AM->OpakováníInicializace(); AM->OpakováníTest(); AM->OpakováníIterace()
  40.    AktivníModul->OpakováníInicializace(); AktivníModul->OpakováníTest(); AktivníModul->OpakováníIterace()
  41. /1 AktivníModul->TestVyhovuje()
  42. /2 !AktivníModul->TestNalezeno()
  43. /3 ;modul dal p²íkaz k ukonƒení hledání NEBO byla stisknuta klávesa Escape
  44.    !mod_HledatDál || (BylaStisknutaKlávesa() && ¼tiKlávesuZFronty() == KlEsc && !(mod_HledatDál = 0))
  45. =SP---------------------------------------------------------------------------
  46.  
  47. ;-h---------------------------------------------------------------------------
  48. void VolbaModulu( void )
  49. -s--VolbaModulu                                                                 ■   2  -2  -1   3
  50.        ___________________VolbaModulu____________________
  51. Lokální~prom╪nné    Získání~seznamu          V∞b╪r~modulu~ze~seznamu
  52.       0!                  a!          __________Kolik~je~na~v∞b╪r?__________
  53.                                       /a                          /b       /
  54.                      ____________Alespoσ~dva____________        Jeden    ªádn∞
  55.                   P²íprava          V∞b╪r           Pouºití     mj!       h!
  56.                   bic!                *1             jl!
  57.                          _____Zpracování~klávesy____
  58.                       Naƒtení                    Reakce
  59.                         d!      _____________Jaká~klávesa?_____________
  60.                                 /1       /2        /3        /4       /5
  61.                               Nahoru    Dolà    ¼íslice    Enter    Escape
  62.                               ei!      fi!        k!        g!       h!
  63. -o1----------------------SEZNAM OPERAC╓------------TENTO ⁿ╡DEK NEM╖NIT!-------
  64. 0 ;lokální prom╪nné
  65.   int AktuálníPoloºka = 0;
  66.   int ProvedenaVolba = 0;
  67. a InfoOModulech(); AktuálníPoloºka = 0;
  68. b ;p²íprava obrazovky
  69.   GrNastavBarvuPozadí(PalBéºová);
  70.   GrSmaºOkno();
  71.   GrKresliP²edm╪t(10,0,66,225);
  72.   GrKresliP²edm╪t(11,0,534,225);
  73. c ;p²íprava klávesnice
  74.   gKlávesa = KlNení;
  75. d ;naƒtení klávesy
  76.   ¼tiKlávesuZFrontyS¼ekáním();
  77. e ;p²esun na p²edcházející poloºku
  78.   if(--AktuálníPoloºka < 0) AktuálníPoloºka = sizeof(ModulyInfo)/sizeof(ModulyInfo[0])-1;
  79. f ;p²esun na následující poloºku
  80.   if(++AktuálníPoloºka >= sizeof(ModulyInfo)/sizeof(ModulyInfo[0])) AktuálníPoloºka = 0;
  81. g ;v∞b╪r aktuální poloºky
  82.   ProvedenaVolba = 1;
  83. h ;zruτení v∞b╪ru
  84.   AktuálníPoloºka = -1;
  85.   ProvedenaVolba = 1;
  86. i ;p²ekreslení seznamu
  87.   // vykreslení p²edcházející poloºky
  88.   if(--AktuálníPoloºka < 0) AktuálníPoloºka = sizeof(ModulyInfo)/sizeof(ModulyInfo[0])-1;
  89.   GrKresliVypln╪n∞Obdélník(144,80,144+9*39-1,80+3*29-1);
  90.   NastavJménoBankyP²edm╪tà("*\\backtraq.mod\\"+ModulyInfo[AktuálníPoloºka].KrátkéJméno);
  91.   GrKresliP²edm╪ty(1,1,144,80,9,3);
  92.   // vykreslení aktuální poloºky
  93.   if(++AktuálníPoloºka >= sizeof(ModulyInfo)/sizeof(ModulyInfo[0])) AktuálníPoloºka = 0;
  94.   NastavJménoBankyP²edm╪tà("*\\backtraq");
  95.   GrKresliP²edm╪ty(1,0,144,196,9,3);
  96.   NastavJménoBankyP²edm╪tà("*\\backtraq.mod\\"+ModulyInfo[AktuálníPoloºka].KrátkéJméno);
  97.   GrKresliP²edm╪ty(1,1,144,196,9,3);
  98.   // vykreslení následující poloºky
  99.   if(++AktuálníPoloºka >= sizeof(ModulyInfo)/sizeof(ModulyInfo[0])) AktuálníPoloºka = 0;
  100.   GrKresliVypln╪n∞Obdélník(144,312,144+9*39-1,312+3*29-1);
  101.   NastavJménoBankyP²edm╪tà("*\\backtraq.mod\\"+ModulyInfo[AktuálníPoloºka].KrátkéJméno);
  102.   GrKresliP²edm╪ty(1,1,144,312,9,3);
  103.   // návrat prom╪nné na aktuální poloºku
  104.   if(--AktuálníPoloºka < 0) AktuálníPoloºka = sizeof(ModulyInfo)/sizeof(ModulyInfo[0])-1;
  105. j ;nastavení ukazatele AktivníModul na strukturu ModulInfo vybraného modulu
  106.   if(AktuálníPoloºka == -1) AktivníModul = 0;
  107.   else AktivníModul = &ModulyInfo[AktuálníPoloºka];
  108. k ;rychlá volba pomocí ƒíslice
  109.   if((AktuálníPoloºka = gKlávesa-'0') == 0) AktuálníPoloºka = 10;
  110.   AktuálníPoloºka--;
  111.   if(AktuálníPoloºka >= sizeof(ModulyInfo)/sizeof(ModulyInfo[0])) { Tón(1000); ¼ekej(200); VypniTón(); }
  112.   else ProvedenaVolba = 1;
  113. l ;návrat obrazovky do pàvodního stavu
  114.   NastavJménoBankyP²edm╪tà("*\\backtraq");
  115.   GrSmaºOkno();
  116. m ;automatick∞ v∞b╪r jediného dostupného modulu
  117.   AktuálníPoloºka = 0;
  118.   ProvedenaVolba = 1;
  119. -c1----------------------SEZNAM PODM╓NEK-----------TENTO ⁿ╡DEK NEM╖NIT!-------
  120. *1 !ProvedenaVolba
  121. /1 gKlávesa == KlNahoru
  122. /2 gKlávesa == KlDolà
  123. /3 gKlávesa >= '0' && gKlávesa <= '9'
  124. /4 gKlávesa == KlEnter
  125. /5 gKlávesa == KlEsc
  126. /a sizeof(ModulyInfo)/sizeof(ModulyInfo[0]) >= 2
  127. /b sizeof(ModulyInfo)/sizeof(ModulyInfo[0]) == 1
  128. /c sizeof(ModulyInfo)/sizeof(ModulyInfo[0]) == 0
  129. =SP---------------------------------------------------------------------------
  130.  
  131. ;-h---------------------------------------------------------------------------
  132. void main( void )
  133. -s--Backtraq                                                                    ■   2  -2  -2   3
  134.          ______________BACKTRAQ_____________
  135.       Zaƒátek         Prost²edek         Konec
  136.       012!                *1              9!
  137.               _______Hlavní~menu_______
  138.           Zobrazení     V∞b╪r     Provedení
  139.              i!          j!           │
  140.                                       │
  141.    ________________________________Vybráno?_______________________________
  142.    /1                                   /2                               /3
  143. Nápov╪da         ________________Spustit~program_________________      Konec
  144.   g!        V∞b╪r~modulu     P²íprava     Spuτt╪ní~modulu    :Θklid:    h!
  145.                 d!            lm!                │           ko2!
  146.                                                  │
  147.                                                  │
  148.               ___________________________________│____________
  149.           Nastavení     __Vstupní~data_           ______Backtracking_____
  150.              n!       Zadání     Optimalizace   Start     Hledání     Hotovo
  151.                        e!            f!          a!         b!         c!
  152. -o1----------------------SEZNAM OPERAC╓------------TENTO ⁿ╡DEK NEM╖NIT!-------
  153. 0 ;lokální prom╪nné
  154.   int UkonƒitProgram = 0;
  155. 1 ;zaƒáteƒní nastavení programu
  156.   EscPlus();
  157. 2 ;nastavení grafického módu
  158.   GrNastavMód(GrMódVGA);
  159.   GrNaƒtiPaletu("*\\backtraq.pal");
  160.   NastavJménoBankyP²edm╪tà("*\\backtraq");
  161.   GrNastavV∞stup(GrV∞stupPlocha);
  162.   GrNastavText(GrTextBezPozadí);
  163. 9 ;záv╪reƒná nastavení programu
  164.   EscMínus();
  165. a AktivníModul->Start();
  166. b Backtrack();
  167. c AktivníModul->Hotovo();
  168. d VolbaModulu(); if(!AktivníModul) continue;
  169. e ;zadání vstupních dat modulu
  170.   AktivníModul->ZadáníVstupu();
  171. f ;optimalizace vstupních dat modulu
  172.   AktivníModul->OptimalizaceVstupu();
  173. g ;zobrazení nápov╪dy
  174.   GrNastavBarvuPozadí(Pal¼erná);
  175.   GrSmaºOkno();
  176.  
  177.   GrNastavPozici(8,10);
  178.   GrNastavBarvuPop²edí(Palªlutá);
  179.   GrPiτⁿet╪zec("Nápov╪da k programu Backtraq");
  180.   GrPiτNov∞ⁿádek();
  181.   GrNastavPozici(8,GrPoziceY()+10);
  182.   GrNastavBarvuPop²edí(PalBílá);
  183.   GrPiτⁿet╪zecWordWrap("Program Backtraq vyuºívá algoritmu zvaného \"backtracking\" (ƒesky \"zp╪tné sledování\") k ²eτení problémà z kaºdodenního ºivota i z teorie, jejichº ²eτení jin∞mi prost²edky neº pomocí poƒítaƒe by bylo velmi komplikované a "+
  184.   "ƒasov╪ nároƒné.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  185.  
  186.   GrNastavPozici(8,GrPoziceY()+10);
  187.   GrNastavBarvuPop²edí(Palªlutá);
  188.   GrPiτⁿet╪zec("Jak program ovládat");
  189.   GrPiτNov∞ⁿádek();
  190.   GrNastavPozici(8,GrPoziceY()+10);
  191.   GrNastavBarvuPop²edí(PalBílá);
  192.   GrPiτⁿet╪zecWordWrap("Po spuτt╪ní programu je zobrazeno hlavní menu (z této nápov╪dy se k n╪mu vrátíte po jejím prolistování). Pro start programu stiskn╪te p²i zobrazeném hlavním menu klávesu F2. Tak p²ejdete na v∞b╪r modulu. Kaºd∞ modul p²edstavuje "+
  193.   +"²eτení urƒité úlohy (problému). Modul vybíráte stisknutím kurzorov∞ch τipek nahoru a dolà, pop². lze pouºít rychlé volby stisknutím klávesy s po²adov∞m ƒíslem modulu (modul, kter∞ je zobrazen∞ po vstupu do v∞b╪ru modulu má ƒíslo 1, dále ƒísla "+
  194.   +"rostou sm╪rem dolà). V∞b╪r modulu potvrdíte klávesou Enter. Poté je na obrazovce zobrazen bliºτí popis ƒinnosti modulu. Nyní jeτt╪ màºete svou volbu zruτit a vrátit se do hlavního menu prost²ednictvím klávesy Escape. Stisknutím klávesy T spustíte "+
  195.   +"modul v textovém reºimu, stisknutím libovolné jiné klávesy v reºimu grafickém. Po spuτt╪ní modulu se dále ²i╘te pokyny, které se zobrazují u horního okraje obrazovky (grafick∞ reºim) resp. v ²ad╪ pod sebou na obrazovce (textov∞ reºim). Pro první "+
  196.   "seznámení se s programem doporuƒujeme pouºívat grafick∞ reºim, pro uskuteƒσování sloºit╪jτích v∞poƒtà pak textov∞ reºim, kter∞ je oproti grafickému rychlejτí.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  197.  
  198.   GrNastavPozici(8,GrPoziceY()+10);
  199.   GrNastavBarvuPop²edí(Palªlutá);
  200.   GrPiτⁿet╪zec("ⁿeτené problémy aneb O modulech");
  201.   GrPiτNov∞ⁿádek();
  202.   GrNastavPozici(8,GrPoziceY()+10);
  203.   GrNastavBarvuPop²edí(PalBílá);
  204.   GrPiτⁿet╪zecWordWrap("S programem jsou standardn╪ dodávány ƒty²i moduly, tzn. program umoºσuje ²eτit ƒty²i ràzné úlohy (problémy): Problém osmi dam, Vyt╪ºovací stanice, Problém obchodního cestujícího, Hledání nejlepτí cesty. Bliºτí popis t╪chto "+
  205.   "modulà naleznete na obrazovce s informacemi po jejich v∞b╪ru v menu pro v∞b╪r modulu. Program je otev²en∞ dalτím v∞vojá²àm, kte²í mohou naprogramovat nové moduly a ty pak do programu snadn∞m zpàsobem zaƒlenit, protoºe zdrojové kódy programu jsou "+
  206.   "voln╪ τi²itelné. Kaºd∞ modul je tvo²en dv╪ma soubory (modul.inc a modul.b00), které jsou umíst╪ny v podadresá²i backtraq.mod. Vloºením takov∞chto souborà do tohoto podadresá²e a jejich p²idáním do seznamu modulà v souboru moduly.inc v témºe "+
  207.   "podadresá²i staƒí k p²idání nov╪ vytvo²eného modulu do programu. Nov∞ modul p²itom màºe vyuºívat veτkeré v∞hody, které mu program Backtraq p²ináτí, coº je mj. jiº vy²eτená základní kostra backtrackingu, na kterou staƒí pouze navázat jednotlivé "+
  208.   "funkce, dále pak p²edp²ipravené funkce pro grafické i textové uºivatelské rozhraní a ukládání informací o ²eτeném problému do textového souboru.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  209.  
  210.   GrNastavPozici(8,GrPoziceY()+10);
  211.   GrNastavBarvuPop²edí(PalSv╪tleModrá);
  212.   GrPiτⁿet╪zec("Stiskn╪te libovolnou klávesu pro p²echod na následující stránku...");
  213.   ¼tiKlávesuS¼ekáním();
  214.   GrSmaºOkno();
  215.  
  216.   GrNastavPozici(8,GrPoziceY()+10);
  217.   GrNastavBarvuPop²edí(Palªlutá);
  218.   GrPiτⁿet╪zec("Podrobn╪ji o backtrackingu a jeho aplikaci v programu");
  219.   GrPiτNov∞ⁿádek();
  220.   GrNastavPozici(8,GrPoziceY()+10);
  221.   GrNastavBarvuPop²edí(PalBílá);
  222.   GrPiτⁿet╪zecWordWrap("Vτechny úlohy (problémy) ²eτené programem jsou zaloºené na spoleƒném algoritmu, kter∞ se naz∞vá backtracking (ƒesky \"zp╪tné sledování\"). Kaºdá úloha tento algoritmus po svém konkretizuje, základ vτak zàstává spoleƒn∞ pro "+
  223.   "vτechny. Základní princip backtrackingu spoƒívá v systematickém zkoumání vτech potenciálních ²eτení, a to takto:", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  224.   GrNastavPozici(8,GrPoziceY()+10);
  225.   GrPiτⁿet╪zecWordWrap("1. Na zaƒátku je ƒásteƒné ²eτení prázdné.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  226.   GrPiτⁿet╪zecWordWrap("2. Dosavadní ƒásteƒné ²eτení je rozτí²eno.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  227.   GrPiτⁿet╪zecWordWrap("3. Pokud je nové ƒásteƒné ²eτení kompletním ²eτením úlohy, skonƒí se.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  228.   GrPiτⁿet╪zecWordWrap("4. Pokud nové ƒásteƒné ²eτení vyhovuje podmínkám úlohy, jde se znovu na bod 2.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  229.   GrPiτⁿet╪zecWordWrap("5. Pokud nové ƒásteƒné ²eτení nevyhovuje podmínkám úlohy, je vyzkouτeno jiné.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  230.   GrPiτⁿet╪zecWordWrap("6. Pokud ºádné ƒásteƒné ²eτení nevyhovuje podmínkám úlohy, vrátíme se o úroveσ v∞τ (na poslední vyhovující ƒásteƒné ²eτení) a pokraƒujeme v prozkoumávání jeho dalτích potenciální rozτí²ení (bod 2.).", GrPoziceX(), GrPoziceY(),
  231.     631, 469, 0);
  232.   GrNastavPozici(8,GrPoziceY()+10);
  233.   GrPiτⁿet╪zecWordWrap("Dalτí nerozτi²ování ƒásteƒného ²eτení z dàvodu, ºe z n╪j nelze dosp╪t ke kompletnímu ²eτení, se naz∞vá pruning (ƒesky \"o²ezávání\", \"omezování\"). A práv╪ vyuºití pruningu ƒiní backtracking rychlejτím a v∞hodn╪jτím neº pouºití "+
  234.   "prostého vyzkouτení vτech moºností. Oproti jin∞m jeτt╪ více zjednoduτen∞m p²ístupàm k ²eτení úloh má pak backtracking tu v∞hodu, ºe zaruƒuje p²esnost v∞sledku, protoºe zkoumá vτechny moºné situace, které mohou p²i ²eτení úlohy nastat.", GrPoziceX(),
  235.     GrPoziceY(), 631, 469, 0);
  236.  
  237.   GrNastavPozici(8,GrPoziceY()+10);
  238.   GrNastavBarvuPop²edí(Palªlutá);
  239.   GrPiτⁿet╪zec("O programu Backtraq");
  240.   GrPiτNov∞ⁿádek();
  241.   GrNastavPozici(8,GrPoziceY()+10);
  242.   GrNastavBarvuPop²edí(PalBílá);
  243.   GrPiτⁿet╪zecWordWrap("Backtraq - Copyright (C) 2001-2002 Marek Blahuτ", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  244.   GrPiτⁿet╪zecWordWrap("Program je freeware a open-source. Lze jej voln╪ τí²it i se zdrojov∞m kódem.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  245.   GrPiτⁿet╪zecWordWrap("Autor programu uvítá, pokud se s ním pod╪líte o své zkuτenosti s programem.", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  246.  
  247.   GrNastavPozici(8,GrPoziceY()+10);
  248.   GrNastavBarvuPop²edí(Palªlutá);
  249.   GrPiτⁿet╪zec("Kontakt na autora");
  250.   GrPiτNov∞ⁿádek();
  251.   GrNastavPozici(8,GrPoziceY()+10);
  252.   GrNastavBarvuPop²edí(PalBílá);
  253.   GrPiτⁿet╪zecWordWrap("Marek Blahuτ", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  254.   GrPiτⁿet╪zecWordWrap("E-mail: blahus@seznam.cz", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  255.   GrPiτⁿet╪zecWordWrap("Adresa: Marek Blahuτ, Rudy Kubíƒka 1002, 686 05 Uherské Hradiτt╪ 5", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  256.   GrPiτⁿet╪zecWordWrap("Telefon: (+420) 777252487", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  257.   GrNastavPozici(8,GrPoziceY()+10);
  258.   GrPiτⁿet╪zecWordWrap("Datum a ƒas poslední zm╪ny: pátek 20.9.2002 23:28", GrPoziceX(), GrPoziceY(), 631, 469, 0);
  259.  
  260.   GrNastavPozici(8,GrPoziceY()+10);
  261.   GrNastavBarvuPop²edí(PalSv╪tleModrá);
  262.   GrPiτⁿet╪zec("Stiskn╪te libovolnou klávesu pro návrat do hlavního menu...");
  263.   ¼tiKlávesuS¼ekáním();
  264. h ;ukonƒení programu
  265.   GrNastavBarvy(Pal¼erná<<4|Palªlutá);
  266.   GrSmaºOkno();
  267.   GrNastavPozici(168, 231);
  268.   GrPiτⁿet╪zec("D╪kujeme za pouºití programu Backtraq.");
  269.   ¼tiKlávesuS¼ekáním2(2000,-1);
  270.   UkonƒitProgram = 1;
  271. i ;zobrazení hlavního menu
  272.   GrNastavBarvuPozadí(PalBéºová);
  273.   GrSmaºOkno();
  274.   GrKresliP²edm╪ty(1001,0,27,95,15,10);
  275. j ;v∞b╪r n╪které z nabídek hlavního menu
  276.   ¼tiKlávesuS¼ekáním();
  277. k AktivníModul->Θklid();
  278. l NastavJménoBankyP²edm╪tà("*\\backtraq.mod\\"+AktivníModul->KrátkéJméno);
  279. m mod_InicializujGrafiku();
  280. n if(!mod_VolbaReºimuObrazovky()) goto Θklid;
  281. o mod_Ukli╘Grafiku();
  282. -c1----------------------SEZNAM PODM╓NEK-----------TENTO ⁿ╡DEK NEM╖NIT!-------
  283. /1 gKlávesa == KlF1 || gKlávesa == '?'
  284. /2 gKlávesa == KlF2 || gKlávesa == KlEnter
  285. /3 gKlávesa == KlF3 || gKlávesa == KlEsc
  286. *1 !UkonƒitProgram
  287. =SP---------------------------------------------------------------------------
  288.  
  289. // Konec souboru
  290.