Údajové štruktúry a algoritmy

[freshmakerik]

to pooler:
tvoj post velmi dobre vidno, ale asi kazdy z nas je taky debil, ze nan nevie odpovedat

[luky]

čo vypíše funkcia dfsst() ak :
1. existuje spojenie medzi : 0-1, 0-2, 2-3
2. existuje spojenie medzi : 0-1, 1-3, 2-4

pre prvý prípad len že je hrana 2-3 a
pre druhý prípad že je hrana len 0-1

[sulo]

čo vypíše funkcia dfsst() ak :
1. existuje spojenie medzi : 0-1, 0-2, 2-3
2. existuje spojenie medzi : 0-1, 1-3, 2-4

1.)
Edge: (0,1)
Edge: (0, 2)
Edge: (2, 3)

2.)
Edge: (0,1)
Edge: (1, 3)
Edge: (2, 4)

pre prvý prípad len že je hrana 2-3 a
pre druhý prípad že je hrana len 0-1

Myslím, že to nie, lebo: "V prípade, že zadaný graf nie je súvislý, vypíšte všetky kostry (jeho súvislých komponentov) získané prehľadávaním do hĺbky (spanning forest)."

[pooler]

čo vypíše funkcia dfsst() ak :
1. existuje spojenie medzi : 0-1, 0-2, 2-3
2. existuje spojenie medzi : 0-1, 1-3, 2-4

1.)
Edge: (0,1)
Edge: (0, 2)
Edge: (2, 3)

2.)
Edge: (0,1)
Edge: (1, 3)
Edge: (2, 4)

pre prvý prípad len že je hrana 2-3 a
pre druhý prípad že je hrana len 0-1

Myslím, že to nie, lebo: "V prípade, že zadaný graf nie je súvislý, vypíšte všetky kostry (jeho súvislých komponentov) získané prehľadávaním do hĺbky (spanning forest)."

z tých obrázkov na moodli nebolo jasne ako má ta funkcia fungovať:
1. edge added vypíše len vtedy ak je celý graf súvislý
2. edge added vypíše vtedy ak spojenie medzi uzlami neorientovane
3. edge added vypíše len vtedy ak existuje spojenie aspon troch uzlov


napísal som email Slodičakovi, a ten mi za 4 dni nestihol odpísať (na cviku mi to "ospravedlnoval" tým že on má veľa roboty, že vraj robí nejaký výskum a že dostáva kvantum emailov na ktoré nestíha odpisovať)

a taktiež mi povedal, že tá úloha ma viacero riešení - voľný priebeh

takže to máš dobre aj ty Sulo ...

mám to dobre aj ja, mne program vypisuje:
1.
Edge Added: (0,1)
Edge Added: (2,3)

2.
Edge Added: (0,1)
Edge Added: (1,3)
Edge: (2,4)


taktiež nechápem Slovičakov prísip na cviku, kde polovica študentov musí program presne vysvetliť, pýta sa ich otázky, a ďalšia polovica (stihne odovzdať behom posledných 15 minut) nekecne ani slovo k úlohe, ani sa ich nič nepýta, rovno im dá plný počet bodov za úlohy --> je to neférové

[tommy-sv]

AHA! A teraz si so mna vsetci robte prdel, ze toto povazujem za vtip: http://u.cwls.info/uploads/Screen%20shot%202010-10-11%20at%2016.25.55.png

Tak teraz to dava zmysel.

Kamarat, velmi dobre si to napisal. Je to kentusacky kentus ten kod.

Zrejme to cele pochadza odtialto http://users.cis.fiu.edu/~weiss/dsaa_c2e/files.html

[Jerrynko]

hej cisto poolover. sa nic nepyta. este stale nemam obhajene tie zadanaia iba 1 a 2 mam. mnikdy nestiha bo sa musi pytat kazdeho vsetke detaily.

[sandusky]

A to nielen on, to aj druhi. Ale ked mate pokupene zadania, musi vas nejako odhalit 

[ursus]

aky je vlastne rozdiel medzi divide and conquer a dynamickym programovanim ?

[totaluser]

vie mie niekto povedat, ci toto je korektny pseudokod na InsertionSort?
lebo ked si to prepisem do C tak mi to nezotriedi posledny prvok v poli

ak urobim ten hlavny for cyklud nie od 1 po N-1 ale od 2 po N tak to samozrejme funguje krasne, ale to uz zial nie je podla pseudokodu

Code: [Select]

insertionSort(array A)
    for i = 1 to length[A]-1 do
        value = A[i]
        j = i-1
        while j >= 0 and A[j] > value do
            A[j + 1] = A[j]
            j = j-1
        A[j+1] = value
Som ja daco prehliadol, alebo to ma Simonak zle(okopirovane odniekial )?

[neucilasom]

Caute este by som sa vratil k 4 ke cviku ako tam mate vyriesene PrintQueue? lebo toto vraj nie je spravne
void PrintQueue( Queue Q )
        {
                   
                   Q->Actual = Q->Front;
                    while (Q->Array[Q->Actual] < Q->Capacity )
                    {
                          printf("%d ",Q->Array[Q->Actual]);
                          Q->Actual = Q->Actual+1;                         
                          }
                   
        }

[luky]

Caute este by som sa vratil k 4 ke cviku ako tam mate vyriesene PrintQueue? lebo toto vraj nie je spravne
void PrintQueue( Queue Q )
        {
                   
                   Q->Actual = Q->Front;
                    while (Q->Array[Q->Actual] < Q->Capacity )
                    {
                          printf("%d ",Q->Array[Q->Actual]);
                          Q->Actual = Q->Actual+1;                         
                          }
                   
        }

malo by sa to robyť tak že do pomocnej premennej si uložíš Front skontroluješ či nie je rovný Rear, vypišeš obsah bunky a posunieš front ale cez pomocnú premennú aby si nemodifikoval front ale ho len vypísal.

len vymeň Capacity za Rear a to Q->Actual za nejaku premennu typu TElement a využi Succ()

[sulo]

vie mie niekto povedat, ci toto je korektny pseudokod na InsertionSort?
lebo ked si to prepisem do C tak mi to nezotriedi posledny prvok v poli

ak urobim ten hlavny for cyklud nie od 1 po N-1 ale od 2 po N tak to samozrejme funguje krasne, ale to uz zial nie je podla pseudokodu

Algoritmus je správny, ale v test.c je: #define N 16, pričom počet prvkov v tom testovacom poli je 17 - asi je to myslené ako "maximálny index poľa" a nie ako počet prvkov poľa. Takže buď zavolaj tú funkciu s parametrom N+1 alebo v cykle for použi i <= n.

[neucilasom]

Caute este by som sa vratil k 4 ke cviku ako tam mate vyriesene PrintQueue? lebo toto vraj nie je spravne
void PrintQueue( Queue Q )
        {
                   
                   Q->Actual = Q->Front;
                    while (Q->Array[Q->Actual] < Q->Capacity )
                    {
                          printf("%d ",Q->Array[Q->Actual]);
                          Q->Actual = Q->Actual+1;                         
                          }
                   
        }

malo by sa to robyť tak že do pomocnej premennej si uložíš Front skontroluješ či nie je rovný Rear, vypišeš obsah bunky a posunieš front ale cez pomocnú premennú aby si nemodifikoval front ale ho len vypísal.

len vymeň Capacity za Rear a to Q->Actual za nejaku premennu typu TElement a využi Succ()

Diky pekne za pomoc uz to fici

[sulo]

Inak ten program na výpočet Fibonacciho čísla je nejaký divný. Vypisuje, že napr. Fib(3)=3, ale tretie Fibonacciho číslo je 2. Asi to bude tým, že je tam naprogramované Fib(0)=1, ale v skutočnosti Fib(0)=0.

[Shwollo]

Ludia... Len tak btw z coho sa ideme ucit na skusku? Ked nam nedava prednasky na net...

[totaluser]

vedel by niekto poradit s tym MergeSort?
https://moodle.fei.tuke.sk/file.php/54/cv08/index.html

v prilohe je zdrojak, no dajako mi to nefacha a uz som v koncoch z toho

rozdelit az na trivialne listy o jednom prvku a nasledne tieto spojit dokopy v uz spravnom poradi
ale ta funkcia merge mi dajako nefunguje

vdaka za vas cas

[j.ferko]

Inak ten program na výpočet Fibonacciho čísla je nejaký divný. Vypisuje, že napr. Fib(3)=3, ale tretie Fibonacciho číslo je 2. Asi to bude tým, že je tam naprogramované Fib(0)=1, ale v skutočnosti Fib(0)=0.

Ano, za Fib(0) sa v skutocnosti povazuje prva 1.

[totaluser]

vedel by niekto poradit s tym MergeSort?
https://moodle.fei.tuke.sk/file.php/54/cv08/index.html

v prilohe je zdrojak, no dajako mi to nefacha a uz som v koncoch z toho

rozdelit az na trivialne listy o jednom prvku a nasledne tieto spojit dokopy v uz spravnom poradi
ale ta funkcia merge mi dajako nefunguje

vdaka za vas cas

ok, vedel by sa na to niekto pozriet, ze co tam je blbo?
pripadne rozbehal to niekto?
ak ano, tak vdaka za napady a opravy

zdrojak v prilohe

[expllclt]

Code: [Select]

List merge(List L1, List L2)
{
     List X =  MakeEmpty(NULL);

     Position Px = Header(X);
     Position P1 = First(L1);
     Position P2 = First(L2);
     TElement E1, E2;
     PrintList(L1); PrintList(L2);
     while (! IsEmpty(L1) && ! IsEmpty(L2))
     {
P1 = First(L1);     // Treba nahrat novy prvy prvok
P2 = First(L2);     // Treba nahrat novy prvy prvok
          E1 = Retrieve(P1) ;
          E2 = Retrieve(P2) ;
          if (E1 < E2)
          {
             Delete(E1, L1);
             Insert (E1, X, Px);
          }
          else
          {
              Delete(E2, L2);
              Insert (E2, X, Px);
          }
          PrintList(L1); PrintList(L2);
          Px = Advance(Px);
     }
     if (! IsEmpty(L1))
     {
        X = Cat(X, L1);
        return  X;

     }
     if (! IsEmpty(L2))
     {
        X = Cat(X, L2);
        return  X;
     }

        return  X;
}

a funguje 

inac co si myslite treba striktne dodrziavat jeho pseudokody? bo ja som spravil merge sort iba z alokovanych poli a mam to o dost lahsie a kratsie

[totaluser]

ludia co mate cvicenie so Slodicakom v pondelok

chcel by som sa opytat, kedy vam vravel ze bude ta pisomka za 20b a na ktorom cviceni si budete opakovat pred pisomkou, vdaka

[cenki]

V 10tom cviku, v hash table... ako riešiť delete? Nájdem daný reťazec napr. "vbn" a za ním sú ďalšie: vbn ccc zzz, tak tie ďalšie posuniem dopredu - namiesto vbn dám ccc a namiesto ccc dám zzz, takže mi ostane: ccc zzz zzz. Dáka idea ako odstrániť to posledné zzz?

[black_stone]

co presne znamena v liste toto ? tmp->next=tmp->next->next;

[cenki]

Posunieš pointer na ďalší prvok.

[Jerrynko]

v ie niekto 11 ?

[scorpi]

a ta 11 to je vlastne co? ved malo byt len 10 cviceni, spolu 20 bodov