Informatyka UJ forum

ostojek · Gość

jak implementujecie to zadanie? zwyklym drzewem binarnym? bo nam Zenczykowski powiedzial ze zwykle binarne nie moze byc bo jest za latwe. i powinnismy zaimplementowac drzewo ktore moze miec wiecej lisci niz 2. a jak jest w innych grupach? tez macie taki zakaz czy moze to tylko u nas taki errorek sie pojawia malutki? :)

Rogal · Wysłany: Wto 8:27, 14 Mar 2006 Temat postu:

Ja to zrobiłem zwykłym binarnym. Zobaczymy co na to Rosek :twisted:

hansu · Wysłany: Wto 12:30, 14 Mar 2006 Temat postu:

A ja zrobilem z ogole bez uzycia drzew to zadanie... Heh, szczerze mowiac nie bardzo wyobrazam sobie robienie tego na drzewach... Przeciez to bedzie makabrycznie wolne... Ale skoro mowicie ze przechodzi to niepotrzebnie sie balem o to moje cz TLE nie dostanie :) Gwoli wyjasnienia robie na dynamicznych listach charow, do ktorych wskazniki trzymam na stosie.

ostojek · Gość

nie no hansu, jak mogles? przeciez sponsorem tego tygodnia sa drzewa :D

Madras · Wysłany: Wto 22:57, 14 Mar 2006 Temat postu:

Fidel · Wysłany: Wto 23:05, 14 Mar 2006 Temat postu:

Jesli nie ma w tresci nakazanego ze ma byc drzewem to albo zapomnieli napisac albo nie zapomnieli - w kazdym razie w obu przypadkach jest dowolnosc 8)

gorzej jak jest odgorny nakaz od cwiczeniowca nie wiem jak u nas bo "niedoslyszalem" :P

ostojek · Gość

nie no to jest dyskryminacja :)

Fidel · Wysłany: Wto 23:54, 14 Mar 2006 Temat postu:

to jeszcze zalezy czy cwiczeniowiec w ogole oglada te programy od strony kodu :P

na pewno dr. Rosek tak bo dzisiaj musialem sie tlumaczyc dlaczego nie zrobilem recordu stos tylko zrobilem zwykle tablice a "implementacje stosu w nich ukrylem" :P

Fen · Wysłany: Pią 1:21, 17 Mar 2006 Temat postu:

ja zaimplementowałem to prostym drzewem binarnym... uważam, że działa mi to dobrze, ale niestety sprawdzarka chce mi wmówić inaczej :)

dla takich danych:
5
15
abc++d*e*fgh++*
5
abc++
9
ab+cde***
1
x
9
ab*c*ab+*

otrzymuję wynik:
(a+b+c)*d*e*(f+g+h)
a+b+c
(a+b)*c*d*e
x
a*b*c*(a+b)

macie może jeszcze inne zestawy na których można by to lepiej przetestować i wychwycić kruczki tego problemu?

Fen · Wysłany: Sob 1:34, 18 Mar 2006 Temat postu:

albo juz testy sa nie potrzebne... zadanko R6 jednak mi przeszło :)

Robson · Wysłany: Sob 17:43, 18 Mar 2006 Temat postu:

Muszę przyznać ze rozwiazanie na liscie jednokierunkowej z głową jest najładniejszym programem jaki ostatnio napisałem - proste, logiczne i działa :)
Nie wyobrażam sobie po co robic to na tych wszystkich drzewach :)
Dobrze ze nasz ćwiczeniowiec powiedział że takie rozwiązanie tez moze byc :)

Skrobocik · Wysłany: Pon 12:54, 20 Mar 2006 Temat postu:

Ja jednek chciałbym to zrobić na drzewach. Czy ktoś może mi przybliżyć chociaż ogólny zarys tego algorytmu :?: Wiem, że jeśli mamy gotowy napis, to można ładne drzewko zrobić zczytując od końca, ale słyszałem, że da się skonstruować drzewo idąc od początku, czyli mniej pamięci by żarło, bo nie musiałbym jeszcze tablicy wczytywanych charów robić. Do wypisywania też mam już pomysł, a raczej Lembas nam na ćwiczeniach zapodał. Chodzi mi głównie o zapisanie struktury drzewa idąc od początku, albo informację, że komuś przeszło jak szedł od tyłu :D . Dzięki, jak ktoś odpisze :wink:

Robson · Wysłany: Pon 15:45, 20 Mar 2006 Temat postu:

trzeba sobie wtedy zrobić stos wskażników do struktury drzewa. Teraz jak czytasz dane to jak
a) wczytujesz literke to tworzysz nowy liść (czyli cos co ma info=literka, a left=right=NIL; i wrzucasz na stos (wskaźnik do tego)
b) czytasz operator to tworzysz nowy wierzcholek, do left podpinasz to co jest na stosie-1, do right to co jest na wierzcholku stosu, a wskaznik do tego wpisujesz do stos-1; wskazik na wierzcholek stos zmniejszasz o jeden.

teraz rekurencyjnie zamieniasz to drzewo tak żeby zrobić drzewo, które ma dowolną ilość synów dla wierzcholka (było na wykładzie jak symulować cos takiego drzewem binarnym). Powinno byc tak że dopuki jakas scieszka składa sie z samych + to ją łączysz razem, tak samo z *.

Teraz rekurencyjnie wypisujesz drzewo. Tzn chyba trzeba zrobic tak że jak wchodzisz do wierzcholka to sprawdzasz jaki jest znak w lewym poddzrewie i jesli sie roznia to piszesz '(' wypisujesz lewe poddrzewo ')' z wierzcholka operator i pozniej prewe poddzrewo analogicznie.

To tylko taki szkic, trzeba to lepiej zaplanować i przemysleć, ale chyba powinno działać. Martwi mnie tylko ta rekurencja...

Skrobocik · Wysłany: Pon 18:28, 20 Mar 2006 Temat postu:

Dzięki Robek :D
Nawias trzeba tylko jak schodzi się z mnożenia do dodawania :wink:

szymku · Wysłany: Wto 1:33, 21 Mar 2006 Temat postu:

Wrzucam zapis w ONP na drzewo binarne i potem wypisuje INORDER ze sprawdzaniem dzieci czy nie mają różnych działań, testy wyglądają ok a jest still ANS ;/

Fen: cużeś zrobił wygląda na to że podobnie to robisz?

szymku · Wysłany: Wto 1:41, 21 Mar 2006 Temat postu:

o chyba kurde wiem jak zrobię to powiem.

Skrobocik · Wysłany: Wto 22:08, 21 Mar 2006 Temat postu:

Heh, poszło i to za pierwszym razem :D
Jeszcze raz dzięki Robson za objaśnienie :wink:

Robson · Wysłany: Wto 22:21, 21 Mar 2006 Temat postu:

No no skrobocik gratulations :)

Makros · Wysłany: Wto 22:37, 21 Mar 2006 Temat postu:

Też by mi poszlo za pierwszym razem gdyby nie to ze mialem tablice na 100 a nie na 100 000 char'ow... ](*,)

Ewka · Wysłany: Wto 22:38, 21 Mar 2006 Temat postu:

Hej !
Mogłby ktoś jakieś złośliwe testy do tego zadanka zamieścić :)
Wciąż mam ANS a nie mogę znaleźć błędu

Makros · Wysłany: Wto 22:46, 21 Mar 2006 Temat postu:

Skorzystaj z Gronostaja... tam są testy do R6...
[link widoczny dla zalogowanych]

Po wyslaniu zadania logujemy sie jak na elfa... :)

Ewka · Wysłany: Wto 22:53, 21 Mar 2006 Temat postu:

Dzięki Makros :)

Ewka · Wysłany: Wto 23:27, 21 Mar 2006 Temat postu:

na wykladzie był algorytm do przeglądania drzewa INORDER
i próbuje tam wcisnąć te warunki wypisywania nawiasów,
dla pewnych przypadków mi nie działa
i nie wiem czy uda mi się to poprawić bo jak przechodze do prawego podrzewa sciągam operator ze stosu a później go potrzebuje do wstawienia tych nawiasów,
czy jest na to jakiś inny sprytny sposób??

Makros · Wysłany: Wto 23:59, 21 Mar 2006 Temat postu:

hmm... ja wogoole zrezygnowalem ze stosu :) każdy węzeł dostał dodatkowy wskaznik 'up' prowadzacy pietro wyzej... Z wykładu wywnioskowałem, ze tak można... Wtedy InOrder robi się nieco prostszy... A co do nawiasów do wywoływałem sprawdzenie czy trzeba go dać (a jeśli tak to który '(' ')' )dla każdego węzła...

Ewka · Wysłany: Śro 0:18, 22 Mar 2006 Temat postu:

no u nas Grażynka powiedziała, że żadnych wskaźników do parenta :(