zap 21.9.

zap 21.9.

Příspěvekod Andreas » 22. 9. 2006 12:02

Tak tentokrat(a letos naposled) bylo zadani dost husty...aspon podle statistik, ktery mam od kamose(ja tam nebyl az do konce) z 19 lidi to dali dva(jeden po 3hodinach, ktery na to byly puvodne dany a jeden asi o hodinu dyl) a to i pres to, ze nekteri to zkouseli i cca 10 hodin, ano slovy deset hodin!:evil: No posudte sami, tady je zadani:

    Program pro formatovani binarnich stromu slov
    =============================================

    Program se bude spoustet z prikazove radky nasledujicim zpusobem:

    tree x.tree

    a vypise strom na standardni vystup. Vstupni soubor x.tree ma nasledujici
    format:

    1. radek obsahuje jmeno souboru se seznamem slov (napr. x.abc), ktery se
    nachazi ve stejnem adresari jako x.tree a pro jednoduchost berte ze je vse v
    current working directory.

    2. radek obsahuje pocet slov ve slovniku x.abc (znacim by A), za nimz
    (mezerou oddeleny) nasleduje pocet vnitrnich vrcholu (vcetne korene)
    binarniho stromu. Znacim C.

    Vyznam je takovy ze slova ve slovniku se cisluji od 1 do A (vcetne) a za
    nimi nasleduji cisla vnitrnich vrcholu stromu (od A+1 do A+C vcetne).

    Dale nasleduje presne C radku, na kazdem z nich jsou 2 cisla oddelena
    mezerou, prvni je index leveho podstromu, druhy index praveho podstromu.
    Takze kdyz tato cisla budou >A tak to znamena ze strom dale pokracuje
    vnitrnim uzlem, kdyz budou <=A tak jsme v listu a podle souboru s abecedou
    muzeme urcit ktery ASCII retezec reprezentuje danne slovo.

    Koren slovu je na poslednim radku souboru *.tree a navic je tento soubor
    usporadany v tom smyslu, ze pri pruchodu libovolnou vetvi od korene k listu
    postupujeme v souboru vzdy jen nahoru.

    Soubor *.abc obsahuje slovnik. Obsahuje A radku a na kazdem z nich je slovo.
    Slovo na prvnim radku ma index 1, slovo na poslednim ma index A v cislovani
    ve kterem se na slovnik odkazuje soubor *.tree. Pritom ve slove se muzou
    vyskytnout libovolne znaky, krome '
    '.

    Nyni co ten program ma delat:
    -----------------------------

    Precte soubor *.tree a prislusny *.abc (kdyz nenalezne tak nejak
    civilizovane zkonci). A potom vytiskne na standardni vystup ASCII-art
    reprezentaci toho stromu. Nejprve to ukazu na priklade. Dejme tomu ze x.abc
    obsahuje

    slovo
    veliceprevelicedlouhereklbychazpredlouheslovo
    nejakedalsislovo
    nepouziteslovo

    a x.tree obsahuje

    x.abc
    4 2
    2 1
    5 3

    Tak vysledek bude:

    veliceprevelicedlouhereklbychazpredlouheslovo ++
    slovo ----------------------------------------/|
    nejakedalsislovo ------------------------------/


    Bystrejsi z vas jiz pochytili ze jde o to vypsat leve vrcholy stromu vys a
    prave niz a pospojovat je pri tom pomoci znaku - | / +
    Pritom vetveni stromu se deje znakem + a objevuje se vzdy na leve (tedy
    horni vetvi), takze se pise napr:

    c ++ nebo pro jiny strom toto: c -+
    a /| (1) a +/ (2)
    b -/ b /

    Tim padem mame vlastnost ze kdyz vyberu ze stromu nejaky uplny podstrom
    ktery zacina na radku x a konci na radku y tak jeho koren bude vzdy na radku
    x.

    Dalsi vlastnost kterou nakresleni musi mit je, ze neplytva znaky `-', coz
    znamena ze kdyz spojuju 2 jinak siroke podstromy tak doplnim jen nezbytny
    pocet znaku `-' k uzsimu z nich (plati to i pro jednotliva slova). Krom toho
    znak '/' se smi pouzivat jen kdyz se vetev zalamuje k nejakemu slovu. Neni
    tedy dovoleno delat krive vetve ve stylu:

    u -+--+
    c ++ |
    a /| / (3)
    b -/ |
    x ---/


    Kontrola spravnosti bude probihat binarnim porovnanim souboru se vzorovymi
    resenimi. To znamena ze zalezi i na mezerach a newlinech. Proto zduraznuji
    ze za slovem nasleduje presne 1 mezera, pak je ten strom, ktery musi byt
    zaplnen na celou sirku mezerami (viz priklad (2) kde nejnizsi list musi mit
    mezeru na konci posledniho radku aby znaky zabiraly sloupec konstantni
    sirky) a pak konci znakem '
    ' (M$-DOSovy '\r' tam tedy neni).


    Napoveda:
    ---------
    Da se to elegantne vyresit rekurzivnim pruchodem toho stromu, jen je potreba
    ho delat 2* pri prvnim si spocitam jak budou ty veci velike abych pri druhem
    vedel kolik mam kam psat minusu.



a tady sou vzorovy soubory:
http://peklo.unas.cz/shakespeare.abc
http://peklo.unas.cz/shakespeare_small.out
http://peklo.unas.cz/shakespeare_small.tree
New systems generate new problems:)
Uživatelský avatar
Andreas
Matfyz(ák|ačka) level I
 
Příspěvky: 26
Registrován: 18. 1. 2006 16:47

Příspěvekod zehyo » 22. 9. 2006 19:22

Zdar.
Ja byl taky na tom zapoctu...byl jsem ten druhy, ktery to odevzdal, a dostal to. Muzu rict, ze se mi ta uloha nejdrive zdala jednoducha, ale kdyz rekl, ze ten strom jak presne musi byt pospojovany, tak jsem se trochu lekl.

Nicmene se musi rict, ze byl ochotny pomoci kazdemu, komu neco neslo (nevedel jak nato, neco se mu zacyklilo, nejaky pointer se ztratil, atd.)
A jak kolega rikal, o case to nebylo...myslim, ze 10 hodim by mohlo stacit.

Ta uspesnost byla asi proto takova, ze slo o treti kolo, a sli tam ty mene nadany...
Asi po hodine se napriklad zaclo resit, ze nekdko neumel kopirovat string (tj. nepouzil strcpy/strdup, ale hodil string1=string2, a divil se, ze se mu to prepisovalo najednou..)
Taky byly problemy u nekoho s rekurzi, ze jak ji napsat.

Jo, a jinak toto nebyl posledni termin. Bude jeste jeden tusim 26. 09.

Tady je moje reseni...jak jsem upraoval ten vypis, tak se to tak trochu sprasilo....
Kód: Vybrat vše
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct uzel
{
   struct uzel *left;
   struct uzel *right;
   char *slovo;
};

char konecek[128];
int delka_konecku = 0;

void vypis(struct uzel *koren, int konec,int dalsi)
{
   char *konecek2;
   int a,b,c,d;
   int nestaci = 1;
   if (koren->slovo==NULL)
   {
      a=pocti(koren)-1;
      konecek[a]='|';
      vypis(koren->left,2,dalsi);
      konecek[dalsi]=' ';
      konecek[a]='/';
      vypis(koren->right,1,a);
      konecek[a]=' ';
   }
   else
   {
      printf("%s ",koren->slovo);
      konecek2=strdup(konecek);
      d=0;
      while (nestaci)
      {
         nestaci=0;
         while (konecek2[d]!='/' && konecek2[d]!='|')
         {
            if (konecek2[d]==' ')
               konecek2[d]='-';
            d++;
         }
         if (konecek2[d]=='|')
         {
            konecek2[d]='+';
            nestaci=1;
         }
      }
      konecek2[delka_konecku]='\0';
      printf("%s
",konecek2+strlen(koren->slovo)+1);
      free(konecek2);
   }
};
int pocti(struct uzel *aktuzel)
{
   int vysledek = 0;
   int vysledek2 = 0;
   if (aktuzel->slovo==NULL)
   {
      vysledek=pocti(aktuzel->left)+1;
      vysledek2=pocti(aktuzel->right)+1;
      if (vysledek2>vysledek)
         vysledek=vysledek2;
   }
   else
      vysledek=strlen(aktuzel->slovo)+1;
   return(vysledek);
}

main(int argc, char **argv)
{
   FILE *strom;
   FILE *slova;
   char soubor_slov[128];
   int pocet_slov = 0;
   int pocet_uzlu = 0;
   int i,a,b;
   struct uzel *koren = NULL;
   struct uzel *aktual = NULL;
   struct uzel **uzly = NULL;
   char buffer[256];


   if (argc==1)
   {
      printf("malo arg.
");
      return(1);
   }
   if (!(strom = fopen (argv[1],"rb")))
   {
      printf("<<%s>> Soubor neex.
",argv[1]);
      return(1);
   }
   fscanf(strom,"%s",&soubor_slov);
   if (!(slova=fopen(soubor_slov,"rb")))
   {
      printf("<<%s>> Soubor neex.
",soubor_slov);
      return(1);
   }
   fscanf(strom,"%d %d
",&pocet_slov,&pocet_uzlu);

   uzly=(struct uzel **)malloc(sizeof(struct uzel *)*(pocet_slov+pocet_uzlu));
   
   for(i=0;i<pocet_slov;i++)
   {
      aktual=uzly[i];
      aktual=(struct uzel *)malloc(sizeof(struct uzel));
      (aktual->slovo)=(char *)malloc(sizeof(char)*256);
      fscanf(slova,"%s",&buffer[0]);
      strcpy((aktual->slovo),&buffer[0]);
      aktual->left=NULL;
      aktual->right=NULL;
      uzly[i]=aktual;
   }
   fclose(slova);

   for(i=0;i<pocet_uzlu;i++)
   {
      fscanf(strom,"%d %d
",&a,&b);
      uzly[pocet_slov+i]=(struct uzel *)malloc(sizeof(struct uzel));
      uzly[pocet_slov+i]->left=uzly[a-1];
      uzly[pocet_slov+i]->right=uzly[b-1];
      uzly[pocet_slov+i]->slovo=NULL;
   }
   koren=uzly[pocet_slov+i-1];

   //-----vypis-----//
   for (i=0;i<127;i++)
      konecek[i]=' ';
   konecek[127]='\0';
   delka_konecku=pocti(koren);
   konecek[delka_konecku]='/';
   konecek[delka_konecku+1]='\0';
   vypis(koren,2,pocti(koren));
   printf("
");
}
zehyo
Matfyz(ák|ačka) level I
 
Příspěvky: 29
Registrován: 20. 1. 2006 20:41

Taky jsem tam byl...

Příspěvekod Fairfax » 23. 9. 2006 09:20

Když jsem psal zápočet z Céčka,
bylo mi úplně jasné,
že moje šance uspět,
s každou hodinou hasne.

Vstup se načíst dal,
nebyla to věda.
Co však dělat dál?
běda ! Běda !! BĚDA !!!
Nechtěl jsem to vzdát,
tak jsem začal psát.

Přestával jsem tápat,
začínal jsem chápat.
Už vím, oč tu kráčí !
Teď to napsat stačí.
Přidám jednu funkci,
rekurze to jistí,
že se tisknout bude,
to stromové listí.

Teď už jenom hlavní věc:
Co tam tisknout nakonec?
plus, mínus a lomítko,
mezera a svislítko.

Není to tak snadné,
jak jsem myslel zprva.
Tenhleten můj kód,
pěkná chlévská mrva.

Když to odladím,
bude hotovo.
Snad si poradím ...
S chutí do toho !
Nechtěl jsem čas ztratit
rychle začal ladit.

Ten, kdo ztratil naději,
dávno vzdal to raději.
Cvičící to nevzdával,
další čas nám nechával.
Nechtěl jsem to vzdát,
tak jsem musel psát.

Po osmi hodinách psaní,
končí programování.
Mozek už nic nestvoří,
Fakta takto hovoří.

Tak jsem to vzdal,
nechal to být.
Aby měl cvičící
konečně klid.
Času nám poskytl
víc než měl v úmyslu
abychom stvořili
hromadu nesmyslů.

Odcházím poučen
ze svého nezdaru:
Snažší než program
je naladit kytaru.
Uživatelský avatar
Fairfax
Matfyz(ák|ačka) level I
 
Příspěvky: 28
Registrován: 17. 1. 2006 19:05
Typ studia: Matematika Mgr.
Login do SIS: vodrj5am

Příspěvekod lavor » 23. 9. 2006 09:44

:D , tak niekoho to cecko riadne poznacilo, 8 hodin :shock: to by som vzdal asi uz 4 krat
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
Uživatelský avatar
lavor
Matfyz(ák|ačka) level III
 
Příspěvky: 121
Registrován: 1. 2. 2005 20:39
Bydliště: kolej 17.11., A1105
Typ studia: Informatika Bc.
Login do SIS: moskj4am

Reseni na jeden pruchod

Příspěvekod Fairfax » 23. 9. 2006 11:10

Moje reseni neni zdaleka tak elegantni, jako uvadi kolega vyse, ale
kdyz uz se mi to konecne povedlo napsat proc ho sem nedat?
Tiskne to vsechno na jeden pruchod.(v jednom miste by se dalo optimalizovat... no posudte sami)
Přílohy
Shakespeare.rar
(103.62 KiB) 91 krát
Uživatelský avatar
Fairfax
Matfyz(ák|ačka) level I
 
Příspěvky: 28
Registrován: 17. 1. 2006 19:05
Typ studia: Matematika Mgr.
Login do SIS: vodrj5am


Zpět na 2005

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník