Drzewo BST

Wyświetlono wypowiedzi znalezione dla frazy: Drzewo BST

Temat: drzewa binarne w Pascalu
[Sorry - przez przypadek poszło na priv...]

hmm... nie rozumiem. BST jak sie domyslam, to binary search tree. nie bede
tu wchodzil w nazewnictwo, bo nigdy tego nie rozroznialem, ale AFAIK drzewo
binarne to takie, w ktorym kazdy wierzcholek ma co najwyzej dwa nastepniki i
klucz syna lewego<klucz rozpatrywanego wierzczholka<klucz syna prawego
(jakby sie kto uprl, to moze zamienic miejscami lewy i prawy i wtedy w
nierownosci zmienia sie znaki)

To co opisałeś to jest BST - Binary Search Tree.
Drzewo binarne to po prostu drzewo w którym każdy wierzchołek ma co najwyżej
dwóch synów i na dodatek występuje rozróżnienie lewy syn-prawy syn.

Temat: Drzewa BST???
rozumiem że chodzi o zwykłe drzewa binarne? bo rysowanie w module Graph 100 drzew BST łącznie z przechowywanymi danymi jest chyba trochę niewykonalne

najpierw trochę informacji:
1) w module Graph ekran ma rozmiar 640 na 480 pikseli
2) drzewo binarne rysuje się zaczynając od pnia, który jest pierwszą gałęzią
3) kolejne gałęzie są o połowę krótsze od tej z której wychodzą
4) z każdej gałęzi mogą wychodzić max 2 gałęzie, każda pod kątem (+/-) 45 stopni do tej z której wychodzi (na kształt dużej litery Y)

a teraz do rzeczy:
1) oblicz sobie ile na ile pikseli może maksymalnie zajmować jedno drzewo żeby zmieściło się 100 drzew na ekranie
2) oblicz sobie ile na ile pikseli może minimalnie zajmować maksymalne drzewo, tak żeby było widać najmniejsze gałęzie
3) jeśli wynik 2 jest większy od wyniku 1, to zadanie jest niewykonalne
4) biorąc po uwagę wynik 1, oblicz maksymalną długość pnia drzewa, czyli pierwszej gałęzi

reszta należy do ciebie

Temat: Algorytmy.. drzewa bst i takie tam...
Czy mógłby ktoś dokładnie podać jaki program mamy napisać na algorytmy?
Z tego co jest na stronie strasznie trudno się zorientować co ma robić. A tu mały link na temat drzew BST :
http://www.owad.civ.pl/index.php?programowanie=4

Temat: Problem z algorytmem.

Witam
Mam do zrobienia las skladajacy sie z drzew BST.
Jedyny warunek to roznica wysokosci drzew ma byc 1 lub 0. (2 w nagorszym
przypadku).
Kazde drzewo przechowuje jakis przedzial kluczy liczbowych.

Dlaczego ma to być las a nie drzewo. Jakie sa kryteria wstawienia
liczby do danego drzewa. Wlasciewie "Ło co chodzi?"

Jedyny pomysl mi jaki przyszedl to drzewa trzeba zaminic na AVL, ale chyba
nie jest to najprostszy pomysl.

AVL o tej samej liczbie wierzchołkow potrafi miec wysokosc rozniaca
sie bardziej niz +-2.

Jakies propozycje wasze jak rozwiazac to roznowazenie ? Jak rozkladac
liczby
po drzewach.
Sam las BST juz zrobilem jakby co ;)

Krysztalowa kula mowi mi, ze masz ustalona licbe drzew, dostajesz
liczby a Twoim zadaniem jest wybrać drzewo, do ktorego ją wstawić,
tak, zeby wysokosc+0/1.

W takim razie dokładaj do najnizszego w grupie, sprytnie
uaktalniajac jego wysokosc;

Jakies dzrewo zrownowazone by sie przydało (nie ma koszmarnej
zlozonosci pesimistycznej), ale jeden warunek, dodanie elementu
nie moze zmiejszyć wysokości drzewa. Banachowski/Disk mowia,
ze co najwyzej sie zwieksza, ale kto by im tam wierzyl;)

pozdrawiam
bartekltg

Temat: Problem z algorytmem.
W zadaniu mam dowolnosc moga okreslic na starcie n drzew albo np okreslic ze
drzewa wypelniam tylko do k elemntow lub m wysokosci pelna dowolnosc. Jedyny
warunek jest taki ze drzewa przechowuja kolejne zbiory liczb np tak jak w
przykladzie. Problemem jest tylko rownowzenie tak by wysokosc roznila sie o
1. Reszte zalozen moge zrobic dowolnych, byle zadanie mialo sens wmiare
czyli nie n liczb n drzewach ;)

| liczby do danego drzewa. Wlasciewie "Ło co chodzi?"
| Mam jakis zbior liczb. Tworze las drzew bst i teraz np.
Dlaczego np tak?
| 1 drzewo 1,2,3,6
| 2 drzewo 7,9,10,11
| 3 drzewo 14,16,17,19
To jest wybór, tak maja być, czy jak podzielić
decydujesz w trakcie?
| Każde drzewo zawiera jakis kolejny zbior wartosci. Po stworzeniu takiego
| lasu oczywiscie musza byc wszlekie operacje dadawania odejmowania itp.
W powyzszym zdaniu czego brakuje..
Poswieć sie i opisz dobrze problem, bo jak narazie mozemy co najwyzej
zgadywać.

pozdr
bartekltg

Temat: Problem z algorytmem.

| liczby do danego drzewa. Wlasciewie "Ło co chodzi?"
Mam jakis zbior liczb. Tworze las drzew bst i teraz np.

Dlaczego np tak?

1 drzewo 1,2,3,6
2 drzewo 7,9,10,11
3 drzewo 14,16,17,19

To jest wybór, tak maja być, czy jak podzielić
decydujesz w trakcie?

Każde drzewo zawiera jakis kolejny zbior wartosci. Po stworzeniu takiego
lasu oczywiscie musza byc wszlekie operacje dadawania odejmowania itp.

W powyzszym zdaniu czegoś brakuje..

Poswieć sie i opisz dobrze problem, bo jak narazie mozemy co najwyzej
zgadywać.

pozdr
bartekltg

Temat: Problem z algorytmem.

liczby do danego drzewa. Wlasciewie "Ło co chodzi?"

Mam jakis zbior liczb. Tworze las drzew bst i teraz np.
1 drzewo 1,2,3,6
2 drzewo 7,9,10,11
3 drzewo 14,16,17,19
Każde drzewo zawiera jakis kolejny zbior wartosci. Po stworzeniu takiego
lasu oczywiscie musza byc wszlekie operacje dadawania odejmowania itp.

Temat: Problem z algorytmem.
Witam
Mam do zrobienia las skladajacy sie z drzew BST.
Jedyny warunek to roznica wysokosci drzew ma byc 1 lub 0. (2 w nagorszym
przypadku).
Kazde drzewo przechowuje jakis przedzial kluczy liczbowych.
Jedyny pomysl mi jaki przyszedl to drzewa trzeba zaminic na AVL, ale chyba
nie jest to najprostszy pomysl.
Jakies propozycje wasze jak rozwiazac to roznowazenie ? Jak rozkladac liczby
po drzewach.
Sam las BST juz zrobilem jakby co ;)
Dzieki za wzelka pomoc

Temat: BST
I to jest oczywiscie jasne jak slonce

- tylko dlaczego nic nie mowi sie o elementach ktore sa rowne
danemu wierzcholkowi?
Czy takie elementy umieszczamy wg wlasnego "widzi mi sie"

zalozmy ze kazdy wezel x drzewa ma atrybuty:
x: left(x),key(x),right(x)

w drzewach BST jest porzadek symetryczny,
czyli dla kazdego wezla x jest spelniony warunek:
jesli wezel y lezy w lewym poddrzewie x, to key(y)<=key(x);
jesli y lezy w prawym poddrzewie x, to key(x)<=key(y).
na podstawie: "algorytmow i struktur danych" Banachowskiego,
Diksa, Ryttera, s. 105

wyglada na to ze tworzac drzewo sam sobie ustalasz po ktorej
stronie dolaczasz nody rowne. tylko badz konsekwentny
i jak wybierzesz strone to sie jej trzymaj dla calego drzewa :)
_______________________________________
Grzegorz "Żuku" Żukowski
emalia: gzuk[at]o2[dot]pl
www: http://cpe1-102.dtvk.tpnet.pl/lanzuk

Temat: liczenie roznicy wierzcholkow w drzewie binarnym

Co to jest BST? Wierzchołek? Droga z lewej (prawej)? Najdłuższa droga?
Drzewo binarne? To nie są pojęcia znane bezwzględnie wszystkim
programistom. Co to jest encja i ODBC?

ehhh. co to jest encja i ODBC to wiem (jak wiekszosc na tej grupie)

wierzcholki to jego elementy, a drzewo moze wygladc np. tak:
7
/
/
2 15
/
/
1 5
cala idee moge podac na maila wedle zyczenia.

i zaprogramuję, tylko że nie znam
zadnego ze wzorów ani sposobów liczenia tego obciążenia.

jak widzisz to nie to samo co wzor...
BTW: jakby nie patrzec drzewa bst sa rzecza elementarna, tak samo jak grafy
czy metody kompresji. ucza tego na studiach informatycznych. niestety chyba
nie az tak doglebnie jak ja tego potrzebuje.

Temat: BST
Witam,

podstawowe operacje na drzewie przeszukiwan binarnych.
Niestety nie posiadam (jeszcze) zadnej ksiazki o strukturach danych
(mam jedynie "Elementy analizy algorytmow" Banachowskiego
i Kreczmara) a z kolei na google'u jest tak duzo linkow ze nie jestem
w stanie wszystkiego przejrzec (ale kilka stron przeczytalem).
Dlatego pomyslalem ze zapytam sie tutaj - mianowicie
chodzi mi definicje tego drzewa.
Wszedzie czytalem ze bst to takie drzewo ze
na lewo od danego wierzcholka sa elementy mniejsze
a na prawo wieksze. I to jest oczywiscie jasne jak slonce
- tylko dlaczego nic nie mowi sie o elementach ktore sa rowne
danemu wierzcholkowi?
Czy takie elementy umieszczamy wg wlasnego "widzi mi sie"
(czyli np. tak jak przy dzieleniu tablicy w quicksort ze mniejsze
i rowne pivotowi na lewo a wieksze na prawo) czy moze
takich elementow w ogole nie mozna umieszczac w tym drzewie
(co by mnie bardzo zaskoczylo)?
Z gory serdecznie dziekuje za odpowiedz.
Pozdrawiam,
soovack

Temat: Znalazlem niescislosc w Cormenie -- sprawdzcie mnie
Hej,

Drzewa poszukiwan binarnych -- Usuwanie, str. 292.

A dla tych, co nie moga zerknac do ksiazki -- chodzi o opis
algorytmu usuwania zadanego wezla z drzewa BST /dla przypomnienia i w
duzym uproszczeniu -- kazdy wezel BST moze miec max. dwoch synow, lewa
galaz danego wezla zawiera elementy nie wieksze niz dany wezel, a
prawa nie mniejsze; poprzednik danego wezla, to wezel o najwiekszej,
ale mniejszej niz dany wezel wartosci, a nastepnik o najmniejszej, ale
wiekszej niz dany wezel wartosci/.

Ok. Autorzy opisuja usuwanie wezla /nazwanego Z/, dla przypadku,
kiedy ma dwoch synow w ten sposob -- wycinamy nastepnik Y wezla Z, o
ktorym wiadomo, ze nie ma lewego syna.

No i wszystko sie zgadza, oprocz mozliwych przypadkow, kiedy w
prawej galezi znajda sie wezly o wartosciach takich samych, jak
usuwany wezel. Operacja wstawienia nastepnika Y w wezel Z, spowoduje
logiczna destrukcje porzadku w drzewie. Modyfikacja oczywiscie jest
trywialna, ale wtedy przepis nie bylby taki ladny /bo nie zawarlby sie
w jednym zdaniu/.

Czekam na opinie -- mam racje, czy pominalem jakis szczegol?

milego dnia zycze
hej

Temat: jezyk polski vs. indeksy

A slyszeli o drzewach BST? Czas wyszukania w takim drzewie to
bedzie pesymistycznie log(najdluzsze slowo). Jak interesuje was
cos naprawde szybkiego to polecam co najmniej drzewa AVL, a
przede wszystkim dowolna ksiazke o algorytmach i strukturach
danych.
PS. Zeby nie bylo watpliwosci, to drzewo bedzie indeksowane
prefiksami.
Uczen szkoly podstawowej.

Wiedziałem że do tego kiedyś dojdzie. Ale już wczoraj (z nieco innych
powodów) zabrałem się za Wirtha. Jak widać ukończenie studiów informatyki
na AGH niekoniecznie daje nawet podstawowe informacje :-)

Zawstydzony...

Temat: jezyk polski vs. indeksy

A slyszeli o drzewach BST? Czas wyszukania w takim drzewie to
bedzie pesymistycznie log(najdluzsze slowo). Jak interesuje was
cos naprawde szybkiego to polecam co najmniej drzewa AVL, a
przede wszystkim dowolna ksiazke o algorytmach i strukturach
danych.

PS. Zeby nie bylo watpliwosci, to drzewo bedzie indeksowane
prefiksami.

Uczen szkoly podstawowej.

| Hmm... Chcesz *przeszukiwać* te 300MB?

A co tam - szef kupi pentium XX 10 GHz, najnowsze windy
i problem z głowy!!! ;-))))

a tak powaznie z tego co sie dzisiaj dowiedzialem - glownie
(wylacznie) od
Piotra Piatkowskiego (czy temat glupi czy moze nie
interesujacy, czy tez moze tak trywialny ze nie warto pisac???)
to poprzestane na wykorzystaniu tego co mam i z tym rusze dalej.

Tomek Bogucki

-~ Wysłano ze strony -

Na stronie www.com.pl możesz łatwo i szybko ogl dać, dyskutować

Jest to pierwszy tego typu serwis po Polsku! Warto zobaczyć!

Temat: drzewa BST

pytanie odnosnie przechodzenia przez takie drzewko i operacje w trakcie:
np

widze ze robimy sortowanko BST ;) czyzby pwr??

sortowanko wygladalo byl schematycznie tak...
od razu jest jest wstawianie do tablicy i usuwanie drzewa w proc inorder
gdyby trzeba bylo pelna wersje to sluze pomoca...

PROCEDURE BSTSort( tab:array of costam{...jakies parametry....});
VAR i:Word;
k{orzen}:wsktree;
{jakies deklaracje}
procedure inorder(k:wsktree);
if k{wezel}<nil
then begin
inorder(k^.lewy);
tab[i]:=k^.wart;
Inc(i);
inorder(k^.prawy);
Dispose(k);
end;
{...}
BEGIN
{tworzenie drzewka}
i:=1
inorder(k);
{itd.}
END;

Temat: BST

jezeli bedziesz konsekwentny, to jedna z w/w nierownosci bedzie ostra.

"tylko badz konsekwentny
i jak wybierzesz strone to sie jej trzymaj dla calego drzewa "

ponizszy cytat mowi, ze moze sobie wybrac
(moze faktycznie dosc niejasno....)

| w drzewach BST jest porzadek symetryczny,
| czyli dla kazdego wezla x jest spelniony warunek:
| jesli wezel y lezy w lewym poddrzewie x, to key(y)<=key(x);
| jesli y lezy w prawym poddrzewie x, to key(x)<=key(y).

_______________________________________
Grzegorz "Żuku" Żukowski
emalia: gzuk[at]o2[dot]pl
www: http://cpe1-102.dtvk.tpnet.pl/lanzuk

Temat: BST

jezeli bedziesz konsekwentny, to jedna z w/w nierownosci bedzie ostra.

"tylko badz konsekwentny
i jak wybierzesz strone to sie jej trzymaj dla calego drzewa "

Temat: Drzewo wyrazenia
chyba tak:
1.zamieniasz na odwrotna notacje polska np a+b na ab+
2.odbijastrz lustrzanie +ab
3.zaczynasz wczytywac ciag
while(nie skonczyl sie ciag)
wstaw dodrzewa

a funkcja wstaw do drzewa to rekurencja w postaci
jesli(znak jest operatorem)
utowrz nowy wezel t
wstaw(t-left)
wstaw(t-right)

mam nadzieje ze pomoglem.... mojego probelmu nikt nie rozwiazal - topic
"wyswietlanie drzewa bst":(

Temat: Wstawianie elementu do drzewa BST
Chodzi o funkcję, która wstawia element o zadanym kluczu do stworzonego już drzewa.

Funkcja sypie się (nie zawsze, ale tak średnio w 80% przypadków) w miejscu oznaczonym w kodzie (piszę w DevCpp, więc kompilator GCC).

Używając debuggera, udało mi się tylko tyle dowiedzieć, że wskaźnik curr przybiera dość w chwili błędu dziwną wartość 0xfeeefeee. Z tego co udało mi się wygooglować, może to oznaczać jakiś błąd pamięci na stosie. Próbowałem zwiększyć rozmiar stosu, bo z tego co wiem, w Windowsie wynosi on chyba 2 MB (doradzono mi, aby w ustawieniach linkera dodać zwiększyć rozmiar stosu, próbowałem zarówno komendą --stack, jak i --heap, zwiększyłem do kilkudziesięciu MB i nic...). Już sam nie wiem, co z tym robić. Kod wydaje się być poprawny, nie rozumiem, dlaczego się sypie. Czy ktoś mógłby na to zerknąć i pomóc? Bardzo mi na tym zależy.

c:

Temat: [c++] Porównanie ciągu znaków

strcmp Mało prawdopodobne żebyś pisząc ręcznie zrobił coś szybszego. No chyba że masz na myśli stosowanie jakiś sztuczek algorytmicznych. Wtedy to nie wiem

Algorytm oparty na drzewach AVL ( rownowazenie drzew BST) dokladniej.

wiec strcmp przydac sie moze jedynie w wyszukiwaniu. mi raczej chodzi zeby sortowac wg alfabetu.
fcje mam takia:

enum TypRel {MNIEJSZE,ROWNE,WIEKSZE};
typedef int TypKlucza;
....
TypRel Relacja(TypKlucza a,TypKlucza b)
{ return a<b ? MNIEJSZE : (a==b ? ROWNE : WIEKSZE); }
czy bendzie dzialac poprawnie(tzn robic to co ja chce) jesli TypKlucza bendzie typu string?[/i]

Temat: 2 pliki tekstowe

| 4. przegladasz plik2 do konca i szukasz, czy ono wystapi (fcja Pos)
pos jest srednio skuteczne, poniewaz wyszukuje tylko w stringach, a nie w
plikach.

po za tym ciagle odczytwanie pliku2 jeden jest rownie nieskuteczne. jezeli
tylko mozemy sobie na to pozwolic to wczytujemy slowa z pliku2 do pamieci

i

jezeli plik2 jest duzy, to po prostu wcztaj jego kawalek (im wiekszy, tym
lepszy) i doczytuj po kawalku do konca

porownujemy je kazdy z kazdym (zlozonosc O(n^2) czyli nie jest to
efektywne). mozna wiec zastosowac jakis slownik - najprostrze sa drzewa
BST,
co znacznie przyspiesza algorytm.

jesli natomiast pliki moga byc duze to najefektywniejszy sa B-drzewa

sadzac po pytaniu, gosc chce raczej prostszego sposobu

Temat: 2 pliki tekstowe

4. przegladasz plik2 do konca i szukasz, czy ono wystapi (fcja Pos)

pos jest srednio skuteczne, poniewaz wyszukuje tylko w stringach, a nie w
plikach.

po za tym ciagle odczytwanie pliku2 jeden jest rownie nieskuteczne. jezeli
tylko mozemy sobie na to pozwolic to wczytujemy slowa z pliku2 do pamieci i
porownujemy je kazdy z kazdym (zlozonosc O(n^2) czyli nie jest to
efektywne). mozna wiec zastosowac jakis slownik - najprostrze sa drzewa BST,
co znacznie przyspiesza algorytm.

jesli natomiast pliki moga byc duze to najefektywniejszy sa B-drzewa

wszystki te madre struktury sa opisane w Cormenie, albo
algorytmach+struktury danych=programy

Temat: drzewa BST
pytanie odnosnie przechodzenia przez takie drzewko i operacje w trakcie:
np

procedure inorder(k:wsktree);
if k{wezel}<nil
then begin
inorder(k^.lewy);
write(k^.wartosc);
inorder(k^.prawy);
end;

i chodzi mi o to, zeby zamiast
write(k^.wartosc)
procedura kolejne wartosci wezla zapisywala do tablicy, czyli cus w ten
desen:
A^[i]:=k^.wartosc;
inc(i);
tyle ze z taka postacia sobie nie radzi rekurencja. Jak taki problem
rozwiazac?

Aha, i jeszcze jedno: jak zwolnic pamiec po tym drzewie?

z gory dziekuje za pomoc
pozdrawiam
win4er

Temat: Znalazlem niescislosc w Cormenie -- sprawdzcie mnie

| Wedlug opisu w Cormenie najpierw usuwasz ta dolna 5'tke (bo jest ona
| nastepnikiem,

Druga piatka nie jest nastepnikiem. Nastepnikiem jest wezel o wartosci
klucza WIEKSZEJ. Vide Cormen.

ej, cos sciemniasz..
dam ci cytat. str. 289:
"..nastepnika danego wezla w drzewie BST., tj. nastepnego wezla odwiedzanego
w czasie
przechodzenia drzewa w porzadku inorder. Jesli wszystkie klucze sa rozne,
to
nastepnikiem wezla x jest wezel o najmniejszym kluczu wiekszym niz key[x].."

pozdr.
Demiurge

Temat: POSZUKUJE!!!

tylko chdzlo mi o to ze nie lubię wyśmiewania się z czyjejś niewiedzy i
nawet wybitny programista kiedyś tak zaczynał i ktoś mu pomógł więc uważa
jak ktoś prosi o jakąś pomoc czy wskazówka to nalezy ją udzielić albo jak
sie nie wie lub nie chce udzielić trzeba siedzić cicho i swoje głupie
komentarze zachować dla siebie !

Ja sie z nikogo nie nasmiewam i nie uwazam sie za niesamowitego programiste
ale na twoje pytanie znalazlem odpowiedz po 2 minutach.

www.onet.pl =wyszukiwarka

+BST +drzewo +algorytm

nie wspominajac o kazdej ksiazce w stylu algorytmy i struktury danych.

momencie pisania programu utkneles bo pytania w stylu "napiszcie mi' albo
"szukam gotowca" na kazdej grupie sa ignorowane.

Temat: Lista dwukierunkowa

A podrzucisz jakimś linkiem w jaki sposób zrealizować wyszukiwanie
inroder iteracyjnie, a nie rekurencyjnie?

Nie znam żadnych linków na ten temat.

Ale w sumie to nietrudno wymyślić, jeśli już wiesz jak przejść do
kolejnego elementu w porządku rosnącym. Bo porządek "inorder" w
drzewie BST to nic innego jak przejście po elementach w kolejności
rosnącej.

Temat: Obsługa wielu plików [pilne]

książka to jeden plik z jej opisem.
Proszę o przesłanie procedury do zapisu ok. 5000 plików z wykorzystaniem
tablic.
Bardzo pilne.

P.S. Najlepiej ślijcie pliki *.PAS na priva.

Rozumiem, ze chcesz sobie zbudowac mala baze i to zapewnie na wlasne potrzeby. Jednak sposob w jaki zamierzasz sie zabrac do tego zagadnienia jest co najmniej zadziwiajacy. Czy nie lepiej stworzyc program, gdzie wpisuje sie potrzebne dane, czesc odpowiedzialna za wyszukiwanie wedlug roznych kluczy - tytul, autor etc. Klucze moga byc przechowywane np. w strukturze drzewa BST itd. Opisy mozna przechowywac w pliku i w razie potrzeby wyszukac w nim potrzebne dane.
Pozdrawiam.

--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

Temat: Obsługa wielu plików [pilne]

Rozumiem, ze chcesz sobie zbudowac mala baze i to zapewnie na wlasne

potrzeby. Jednak sposob w jaki zamierzasz sie zabrac do tego zagadnienia
jest co najmniej zadziwiajacy. Czy nie lepiej stworzyc program, gdzie
wpisuje sie potrzebne dane, czesc odpowiedzialna za wyszukiwanie wedlug
roznych kluczy - tytul, autor etc. Klucze moga byc przechowywane np. w
strukturze drzewa BST itd. Opisy mozna przechowywac w pliku i w razie
potrzeby wyszukac w nim potrzebne dane.

Pozdrawiam.

Plik z danymi może nawet mieć czytelny format tekstowy, np:

numer=574
tytul=Tan Padeusz
autor=Micki Adamowicz

numer=575
tytul=Śruby Panieńskie
autor=Mokele Mbebe

itp.

Temat: POSZUKUJE!!!
A co ciebie to obchodzi i skąd wiesz czy to dla mnie czy też dla kogoś
innego ja zadałem chyba banalne pytanie którego ty nawet nie potrafisz
zrozumieć!!!
Więc SIO!

| Poszukuje osoby bądź strony gdzie taki programik można znaleźć do

| prostego programiku w C !!!!!!
| Program ten to:
| Prosta baza na drzewie BST z możliwością dodania , usunięcia,
znalezienia,ed
| ycji danych
| Ma to być np. baza filmów!!!!!!
| Dane te mają być wpisywane do pliku!!!!
| Za pomoc jestem w stanie się odpłacić!!!!
Zalosne, podstawowe "akademickie" algorytmy.
Po co wybrales taka szkole? nie lepiej byc marketingowcem?

--
Marcin Kurpiewski

Temat: POSZUKUJE!!!
jak nie chesz pomóc to nic nie pisz a nie tu z jakimiś głupimi tekstami
wyjeżdżasz. A jak jesteś taki cwaniak i chcesz coś pisać do prześlij ten
algorytm

| Poszukuje osoby bądź strony gdzie taki programik można znaleźć do

| prostego programiku w C !!!!!!
| Program ten to:
| Prosta baza na drzewie BST z możliwością dodania , usunięcia,
znalezienia,ed
| ycji danych
| Ma to być np. baza filmów!!!!!!
| Dane te mają być wpisywane do pliku!!!!
| Za pomoc jestem w stanie się odpłacić!!!!
Zalosne, podstawowe "akademickie" algorytmy.
Po co wybrales taka szkole? nie lepiej byc marketingowcem?

--
Marcin Kurpiewski

Temat: Odśmiecacz w C++ -- nowa wersja (Smieciuch++ 0.6.3)
Witam!

Wypuściłęm nową wersję Śmieciucha++, jest na stronie

http://sf.net/projects/smieciuch

Poprawiona jest zgodność ze standardem C++ (kompiluje się na większej ilości
kompilatorów), zminimalizowane zostało zużycie stosu systemowego podczas
odśmiecania (dotychczas mogło to czasem stanowić problem)

Przy okazji zrobiłem mały tescik, porównując wydajność Śmieciucha z
boost::shared_ptr (i shared_array), no i na testowym kawałku kodu
(tworzenie sporego drzewa BST, tworzenie i manipulowanie kilkoma
śrenio-dużymi tablicami) wyszło 5% szybciej od boosta z jego zliczaczem
referencji i niecałe 2% wolniej od działania na zwykłych wskaźnikach ze
zwalnianiem explicite (delete).

Śmieciuch nadal nie obsluguje wątków (tak jak i samo standardowe C++ ;) ),
może w wersji 0.7 będzie...

pzdr

Temat: POSZUKUJE!!!
ale jeżeli kogoś czas goni i nie może pozwolić sobie na kombinowanie i
zwraca się o pomoc do ludzi którzy mogą mieć taki gotowy kod to napewno
troche czasu można poświęcić i wysłać coś jeżeli miało by to komuś tyłek
uratować oki koniec tematu i Dziekujemy za pomoc programistów :)

| tylko chdzlo mi o to ze nie lubię wyśmiewania się z czyjejś niewiedzy i
| nawet wybitny programista kiedyś tak zaczynał i ktoś mu pomógł więc
uważa
| jak ktoś prosi o jakąś pomoc czy wskazówka to nalezy ją udzielić albo
jak
| sie nie wie lub nie chce udzielić trzeba siedzić cicho i swoje głupie
| komentarze zachować dla siebie !
Ja sie z nikogo nie nasmiewam i nie uwazam sie za niesamowitego
programiste
ale na twoje pytanie znalazlem odpowiedz po 2 minutach.
www.onet.pl =wyszukiwarka
+BST +drzewo +algorytm
nie wspominajac o kazdej ksiazce w stylu algorytmy i struktury danych.

momencie pisania programu utkneles bo pytania w stylu "napiszcie mi' albo
"szukam gotowca" na kazdej grupie sa ignorowane.

--
Marcin Kurpiewski

Temat: W jakim jezyku rozpoczac programowanie?
Dobrze, zeby nie wszczynac niepotrzebnych klotni - jeszcze raz odpowiem:
- C ma skladie w miare prosta. Sam jezyk tez jest prosty, ale napisac w nim cos wiekszego to juz jest sztuka (u mnie na roku, ludzie po pol roku nauki C maja problemy z np drzewami BST)
- C++ ma trudna skladnie. To tak jakby do C dorzucic jeszcze 3x tyle roznych konstrukcji. Do tego kompatybilnosc z C wymusza czasami dziwne konstrukcje. Tyle moge powiedziec o C++ bo nie znam go jeszcze wystarczajaco dobrze. Jednak w moim mniemaniu nie jest to jezyk dla poczatkujacego.
- Python - to pierwszy jezyk jaki opanowalem. Uczylem sie sam, mialem troche problemow, ale dokumentacja w sieci jest bardzo dobra. Do tego szybkie wykonywanie kodu, shell i bardzo pomocne errory.
- Ruby - tez moze byc niezly dla poczatkujacego z tych samych powodow co python. Troche bardziej obiektowy, miejscami magiczny, ale przyjemny.

Reszty nie znam wiec sie nie wypowiadam. To sa moje prywatne oceny i przemyslenia wiec darujmy sobie komentarze w stylu "nieprawda bo...".

A tak OT to zastanawia mnie ile z tych osob co polecaja na poczatek C++ zna inne jezyki i napisalo w C++ jakis wiekszy projekt.

Temat: "Kurs C++" na forum
Bardzo chętnie pomogę w rozwijaniu wszelkiego wolnego oprogramowania ;).

Mam 17 lat i programowania uczę się od 2-3 lat. W tym czasie poznałem Pascala, C i C++ na średnim poziomie. W tej chwili powoli poznaję też Pythona.

Nigdy wcześniej nie pracowałem nad żadnym grupowym projektem - do tej pory pisałem jedynie pojedyncze małe programy przedstawiające np. sposób działania drzew BST itp.

Temat: [2006Z] Egzamin
no tak... okazało się, że nie potrafię wstawiać liczb do drzewa bst

rzeczywiście jeśli elem. jest większy od tego w korzeniu to idzie w prawo i już nie wraca... a element 363 jest gdzieś właśnie tam na lewo ;))) funkcja szukaj tak samo niespostrzegawcza jak ja ;)

edit: kurcze, jednak dalej coś mi się tu nie podoba:

podpunkt (d)

Temat: Jestem NOWY

| Z programowania obiektowego miałem 2 zadania zaliczeniowe z C++ i ze SM.
| To z C++ zrobiłem z ciągu tygodnia, dokładnie wiedziałem co gdzie jak
| działa
| natomias to w SM męczę od dłuższego czasu, nie wiem dlaczego działa tak
| a nie
| Jako wspolodpowiedzialny chcialbym uzupelnic. Zadanie z C++ bylo krotka
| wprawka, do rozwiazania w kilka godzin, natomiast to w Smalltalku to
| glowne zadanie przewidziane do realizacji w ciagu jednego semestru.

Zadanie ze smalltalka było równie nieskomplikowane merytorycznie,
tyle że jeszcze trzeba było zrobić interfejs, który niby miał się w
WindowBuilder praktycznie sam genereować.

Aby nie bylo watpliwosci wyjasnienie:

zadanie z C++: zaimplementowac przy pomocy drzewa BST slownik z operacjami
wstawiania i pobierania elementu zwiazanego z danym kluczem (ok. 200
wierszy kodu)

zadanie ze Smalltalka: zrealizowac prosty arkusz kalkulacyjny

Porownanie stopnia trudnosci pozostawiam Panstwu.

Artur Zaroda

Temat: POSZUKUJE!!!

prostego programiku w C !!!!!!
Program ten to:
Prosta baza na drzewie BST z możliwością dodania , usunięcia, znalezienia,ed
ycji danych
Ma to być np. baza filmów!!!!!!
Dane te mają być wpisywane do pliku!!!!
Za pomoc jestem w stanie się odpłacić!!!!
Dzięki!!

Temat: Sieci neuronowe

Siedze sobie wlasnie na bardzo "ciekawej" lekcji
tzw. informatyki i slucham bezsensownego piep...nia
belfra na rozne glupie tematy. No bo po co mi
znajomosc jakichs 5 algorytmow sortujacych albo
drzew BST, AVL lub co gorsza beznadziejnych
triangulacji, Hufmannow itd... A ja jestem przeciez
normalnym czlowiekiem (o sorry - uczniem), ktoremu
na nic to sie nie przyda. Wszystko byloby cacy,

A czego twoim zdaniem powinni uczyc? Bardzo jestem ciekaw odpowiedzi.

Raz zdarzylo sie, ze uslyszalem cos o sieciach neuronowych.

Byl cykl artykulow R. Tadeusiewicza w ENTER'ze. Chyba rozpoczal sie
od nr 1/95. Czytalem go z przyjemnoscia (choc chyba nigdy SN nie bede
sie zajmowal).

Powodzenia przy zaliczaniu.

Temat: prośba o pomoc z TP 7.0
Witam, bardzo proszę o pomoc z następującym problemem:
czy pod Turbo Pascalem 7.0 da się poszerzyć rozmiar Heap , tak żeby nie było
ERROR 203 (Heap overflow). Pytam ponieważ mam program z listą i drzewem Bst w
pamięci i nie chce on działać dla 30000 słów, natomiast pod Free Pascalem
działa. Czy tu może chodzi o Tryb Chroniony? Bardzo dziękuję za pomoc i
pozdrawiam - Tomek

Temat: Zaliczenie z C
Mój kolega z uczelni miał częściowo rację.Chodzi o pomysł z drzewem.
Tylko zamiast anagramów do drzewa trzeba wstawiać tablice int o rozmiarze
[ilość liter w alfabecie]. Teraz wczytując słowo zwiększamy odpowiednią
komórkę w tablicy odpowiadającą danej literze alfabetu -dla abba w tablicy
na miejscu 0 - mamy-2, na miejscu 1-mamy- 2, a dalej zera. Dla każdego
wyrazu otrzymujemy taka tablicę i nie ważne wtedy czy jest to "abba" czy
"bbaa".
wułala :)

Mike.

| Na drzewo! (Nie ty tylko anagramy).
| Tak poważniej: BST z tym, że oprócz wartości przechowujesz ilość
| wystąpień. przeszukujesz: jak znajdziesz to zwiększasz ilość, jak nie to
| dodajesz do drzewa.
A jak ty to sobie wyobrazasz? Drzewko permutacji czy co?
Przecierz w tym zadaniu ab i ba to to samo, a na drzewie wcale nie....

--
Milo

ICQ: 14939954
For-pay Internet distributed processing.
http://www.ProcessTree.com/?sponsor=32452

Temat: drzewo binarne

Otoz czytam własnie w Cormenie o drzewach binarnych i mam pewną
wątpliwość: jak majac podany ciag liczb tworzy sie z nich drzewo
binarne? Czy moglby mi ktos opisac sposob tworzenia takic drzew? Na
przyklad niech ciagiem (wlasnie - to jest ciag czy zbior, kolejnosc
mozna zmieniac, czy nie ?)wjsciowym bedzie:
7, 9, 5, 16, 22, 17, 9, 7, 10, 12

znaczy chodzi o BST?

wrzucasz 7 jako korzeń, pózniej wrzucasz 9 jako prawego potomka 7,
(bo 97) 5 jako lewego potomka 7(bo 5<9), 16 jako prawy potomek 9
(bo... wiadomo :P)no i tak dalej.

[fixed-font-required]
{pomine powtarzające sie klucze}
7
5 9
16
10 22
12 17
{ chyba ok :] }
[/fixed-font-required]
w każdym razie chodzi o to że w stosunku do danego węzła lewe
poddrzewo zawiera elementy o kluczu niewiększym od klucza tego węzła a
prawe podrzewo odwrotnie(niemniejszym). czyli - porównujesz klucz z kluczem
wezła
jak mniejszy wrzucasz w lewo, jak większy wrzucasz w prawo(w zależności
czy prawo/lewo istnieje albo tworzysz albo powtarzasz ten zabieg - przy
czym tą rekurencje można rozwinąć w iteracje :]).

p.s. mam nadzieje że w miare zrozumiale ;).

Temat: Szybkosc algorytmow
Czesc

| Owszem. Ale glupota w rownym stopniu jest stosowanie iteracji przy
| operacjach na drzewach/grafach...

Nieprawda, przy operacjach na drzewach mozna poradzic sobie
bez rekurencji. [..]

Jakie operacje?
Jakie drzewa (jaka implementacja)?

Coś mało konkretnie (jak na programistę) formułujesz swoje myśli.

Np. przejście drzewa binarnego BST (iterowanie kolejnych elementów)
zdefiniowanego mniej więcej tak:

NODE
{
KEY key;
NODE * left;
NODE * right;

};

wymaga raczej stosu, prawda?

I w przypadku np. tego algorytmu ciężko będzie wymyślić iteracyjny odpowiednik
tego algorytmu (o podobnej wydajności jak implementacja przy pomocy rekurencji
(hadwareowego stosu)).

Pozdrawiam
Adam Woźniak

Temat: liczenie roznicy wierzcholkow w drzewie binarnym

ehhh. co to jest encja i ODBC to wiem (jak wiekszosc na tej grupie)

wierzcholki to jego elementy, a drzewo moze wygladc np. tak:
7
/
/
2 15
/
/
1 5
cala idee moge podac na maila wedle zyczenia.

probem polega na algorytmie, ktorego nie kaze nikomu wymyslec, bo takowy
juz
istnieje. niemniej jednak jest on dosyc trudno dostepny. na googlach nie
znalazlem, w literaturze ktora posiadam tez tego nie ma. pisze na grope
poniewaz, moze ktos juz "walczyl" z czyms takim

Ja chyba z innego google korzystam, bo na hasło "wierzchołki BST" dostałem
24 odpowiedzi.
Przeglądając pobieżnie, znalazłem coś takiego:
http://www.republika.pl/alikw/mgr/drzewo/find.htm
Jest wyjaśnione, jak znaleźć konkretną wartość w drzewie. Można rozbudować
tą procedurkę o zapamiętanie długości drogi, w jakiej znaleziono szukaną
wartość. Jest również przykład, jak wyszukać element o najmniejszym i
największym kluczu.
Definicja / Implementacja / Wyszukiwanie / Wstawianie / Usuwanie /
Złożoność / Podsumowanie

Martini

Temat: liczenie roznicy wierzcholkow w drzewie binarnym

witam

mam problem z policzeniem roznicy wierzchowlkow w BST. Jesli ma ktos
pomysl
na algorytm bardzo chetnie wyslucham ;)
po "ludzku" liczy sie to tak: roznica wierzcholkow := najdluzsza droga z
lewej strony - najdluzsza droga z prawej strony.

a poźniej:

niedowiary. tylu tu programistow i nikt nie umie tego zrobic? ;)
moze jednak znajdzie sie ktos, kto moze pomoc...... bo google nie mogly
;(

Progowe obciążenie belki na 3 podporach zwężonej do 23% wysokości
początkowej w 3/4 długości bez problemu Ci zaprogramuję, tylko że nie znam
żadnego ze wzorów ani sposobów liczenia tego obciążenia. Jak mi je podasz,
będziesz miał program.

Co to jest BST? Wierzchołek? Droga z lewej (prawej)? Najdłuższa droga?
Drzewo binarne? To nie są pojęcia znane bezwzględnie wszystkim
programistom. Co to jest encja i ODBC?

pozdrawiam
Martini

Temat: Drzewo binarne - problem

Innym problemem jest, że gdy zaczniesz przeglądać od tego elementu w
porządku INORDER, to zdołasz jedynie przejrzeć poddrzewo związane z tym
wierzchołkiem. Jeśli chcesz pójść jeszcze dalej, musisz zapamiętać całą
ścieżkę.

Tak chodzi o BST, chodzi o to ze potrzebuje wszystkie rekordy, ktore
alfabetycznie nastepuja po tym ktory mnie interesuje.
Przy przegladaniu INORDER calego drzewa moglbym zignorowac wszsytkie
wczesniejsze , ale nie o to chodzi. Chce uniknac
ciaglego przegladania drzewa od poczatku..

Temat: Odśmiecacz w C++ -- nowa wersja (Smieciuch++ 0.6.3)

| reprezentacja liści BST z domyślnie skonstruowaną wartością.

???

Puste BST ma pole val z domyślnie skonstruowaną wartością.

Moim zdaniem takie BST (o imperatywnym interfejsie) powinno mieć
nagłówek, żeby można było je zmienić w miejscu, a w samym drzewie
liście powinny być pustymi wskaźnikami. Bez pola empty.

A jak wygląda ten kod, możesz pokazać?

http://qrnik.knm.org.pl/~qrczak/tmp/smieciuch/

| Zmieniłem -O0 na -O2, żeby było sprawiedliwie.

???
Co i jak budowałeś? Np. w Smieciuch wazne jest ustawienie przy kompilacji
-DNDEBUG, bez tego gc_ptr zawiera dodatkowe pola (sanity checking) i robi
się cieższy i wolniejszy.

Teraz widzę, że niepotrzebnie to zrobiłem. Zrobiłem make
i uruchamiałem gcpp, czyli wersję, która jest kompilowana
z -O6, a -O0 tego nie dotyczy.

Temat: Co to są drzewa AVL

gdzie moge znaleac informacje o tych drzewach

coś jak BST, tylko dbasz o to, by dwa poddrzewa nie różniły się zbytnio
wysokością, dzięki czemu wszystkie gałązki są podobnej długości i nie ma takiej
sytuacji że jedna jest długa na kilometr i poszukiwanie w drzewie trwa
pół roku
a poczytać o nich możesz w każdej dobrej książce o algorytmach i strukturach
danych (nie tylko u Wirtha)

Temat: Drzewo binarne - problem

Tak chodzi o BST, chodzi o to ze potrzebuje wszystkie rekordy, ktore
alfabetycznie nastepuja po tym ktory mnie interesuje.
Przy przegladaniu INORDER calego drzewa moglbym zignorowac wszsytkie
wczesniejsze , ale nie o to chodzi. Chce uniknac
ciaglego przegladania drzewa od poczatku..

Wystarczy, ze zmodyfikujesz troche przegladanie INORDER. W pseudokodzie
bedzie to wygladac jakos tak:

INORDER(node, searchKey):
IF (node IS NOT NULL)
BEGIN
IF (node.key = searchKey) THEN
BEGIN
INORDER(node.left, searchKey)
PROCESS
END
INORDER(node.right, searchKey)
END

Pozdrawiam,
Tomek

Temat: Zaliczenie z C

Na drzewo! (Nie ty tylko anagramy).
Tak poważniej: BST z tym, że oprócz wartości przechowujesz ilość
wystąpień. przeszukujesz: jak znajdziesz to zwiększasz ilość, jak nie to
dodajesz do drzewa.

A jak ty to sobie wyobrazasz? Drzewko permutacji czy co?
Przecierz w tym zadaniu ab i ba to to samo, a na drzewie wcale nie....

Temat: Znalazlem niescislosc w Cormenie -- sprawdzcie mnie

Drzewa poszukiwan binarnych -- Usuwanie, str. 292.

Pozwolisz, że będę się opierał na oryginale?

[...]

A
/
/
B A
/
/
C

C<=A bo jest lewym dzieckiem, ale C=A, bo jest w prawym poddrzewie. Czyli
A=C. Co jest źle?

Modyfikacja oczywiscie jest
trywialna, ale wtedy przepis nie bylby taki ladny /bo nie zawarlby sie
w jednym zdaniu/.

Czekam na opinie -- mam racje, czy pominalem jakis szczegol?

Pominąłeś jeden dosyć istotny, stanowiący podstawę BST. Znaczy definicję.
Mówi ona, że klucze _wszystkich_ węzłów w lewym poddrzewie są mniejsze równe
a w prawym większs równe. Nie tylko dzieci!

milego dnia zycze

I wzajemnie :-)

Boczi

Temat: BSP

| Czy ktos wie gdzie znalezc na sieci jakies objasnienia
| (po polsku) na temat drzew bsp ?

BST, a nie bsp koledzy!

??????

Jak nie Binary Space Partitioning to ja już nie wiem co ...

P.S. Kolega chyba nie w temacie...

Temat: pomocy gdze nakierować antene Przełazy EDGE iPlus
Średniawo bo teraz już zamontowałem antene na stałe, ale nie mogłem znaleść najleprzego zasięgu teraz mam 3/7.Musze jeszcze sie pobawić z anteną żeby osiągnąć max zasięg.

Drugi post scalony:
troszke zapóżno ,bo już troszke poradziłem sobie .Mieszkam w Przełazach woj.Lubuskie ,ukształtowanie terenu kilka drzew{ w kierunku Niesulic kierunek bst{ w strone Świebodzina ,toporów i inne troszke zasłania las bo mam troszke wysoko antene najb. nadajnik jest ok.8km

[ Dodano: 2008-01-13, 16:32 ]

Temat: Quicksort w helpie pascala?

chodzi o to ze do niektorych algorytmow pisze tylko, ze optymalna zlozonosc
osiagniemy stosujac drzewo AVL albo kopiec fib itd. i wez tego uzyj na
jakis
zawodach kiedy jestes ograniczony czasem ;)))))

Tez dlatego mowie, ze nikt Cie nie zmusza.
Przy Dijkstrze wiesz czy masz graf zadki czy gesty, wiec albo stosujesz stog
albo wybierasz liniowo. AVL nigdy nie jest potrzebne a jednie jakiesz
sztczki z BST.

Na3 OI daja takie problemy ktore da sie zrobic. Nie liczac "Lodowiska",

hehehehehe w piec godzin na pewno nie ;))

A w ogole? Bo mi sie nie chce :)

NOWIESZ

Temat: Quicksort w helpie pascala?

| chodzi o to ze do niektorych algorytmow pisze tylko, ze optymalna
zlozonosc
| osiagniemy stosujac drzewo AVL albo kopiec fib itd. i wez tego uzyj na
jakis
| zawodach kiedy jestes ograniczony czasem ;)))))

Tez dlatego mowie, ze nikt Cie nie zmusza.
Przy Dijkstrze wiesz czy masz graf zadki czy gesty, wiec albo stosujesz
stog
albo wybierasz liniowo. AVL nigdy nie jest potrzebne a jednie jakiesz
sztczki z BST.

Na3 OI daja takie problemy ktore da sie zrobic. Nie liczac "Lodowiska",

lodowisko? pamietam to zadanko - nie wydaje sie az tak trudne......

czemu zawsze piszecie o 5h? przeciez na zadanko jest tylko 2.5....

Temat: kolejki, stosy itp itd

czy znacie moze strony gdzie bylyby opisane struktury dynamiczne:
* KOLEJKI I STOSY (FIFO, LIFO)
* LISTY DYNAMICZNE ( z wartownikiem, z dowiazaniami jedno i
dwukierunkowymi )
* DRZEWA ( binarne, bst ...)

Stron nie znam, ale zajrzyj do ksiazki:
N. Wirth - "Algorytm + struktura danych = program"

Czy jakos tak.

Temat: kolejki, stosy itp itd
Hej,
czy znacie moze strony gdzie bylyby opisane struktury dynamiczne:
* KOLEJKI I STOSY (FIFO, LIFO)
* LISTY DYNAMICZNE ( z wartownikiem, z dowiazaniami jedno i dwukierunkowymi )
* DRZEWA ( binarne, bst ...)

Z gory BIG dzieki

Pozdrawiam
Adam Sokołowski
-----------------------------
http://www.aqq.cjb.net
-----------------------------

Temat: liczenie roznicy wierzcholkow w drzewie binarnym
witam
mam problem z policzeniem roznicy wierzchowlkow w BST. Jesli ma ktos pomysl
na algorytm bardzo chetnie wyslucham ;)
po "ludzku" liczy sie to tak: roznica wierzcholkow := najdluzsza droga z
lewej strony - najdluzsza droga z prawej strony.

pozdrawiam
Jaqb

gg: 2214184

Temat: Logarytmiczne znajdywanie liczby elementow mniejszych od danego

ooops, sorrki za gafe :), gdybym dobrze zbudował BST, to nie bylo by tego
problemu :), ale i tak mozesz opisac mniej wiecej metody dzialania :)

Szukanie jest całkiem proste. Taka gimnastyka w sam raz na dobranoc.

Jako podpowiedź: element może być strukturą taką:
struct korzen {
int wartosc;
int ile_mniejszych;
struct korzen *lewy, *prawy;

}

Przy wstawianiu/usuwaniu rzeczywiście musisz aktualizować całą ścieżkę
wiodącą do wstawianego/usuwanego elementu.

Zwykłe drzewo da Ci koszt pesymistyczny O(n) dla wszystkich operacji. Za
zrównoważenie dostaniesz O(log n).

Temat: kolejki, stosy itp itd

Hej,

Hej

Pozdrowionka
Grzegorz

Temat: binarySearch w kolekacjach

a drzewa binarne? :)
zaleznie od typu drzewa, drzewa sa bardzo wydajne do przeszukiwania czy
innych operacji...

Taak. Pytanie tylko, czy wyszukiwanie w drzewie (nawet BST) też nazywa
się wyszukiwaniem połówkowym. :]

Temat: drzewa bst
Ej no sorry... ale trzeba było uważać na wykładach. A jeżeli już nie uważałeś to chociaż poczytać sobie o drzewach BST na Wikipedii...

Temat: Drzewa BST???
Proszę o pomoc, bo już nie mam głowy do tego zadania:

Narysuj las losowy: liczba drzew 10-100, liczba gałęzi drzewa 1-10, drzewa rozmieszczone losowo ale całkowicie mieszczą się na ekranie.

Bardzo byłbym wdzięczny.

Temat: Implementacja BST - problem
Przepraszam, miałem ponad miesiąc przerwy z programowaniem, niby nie dużo ale zrobiło swoje...chcę zrobić funkcje wstawiającą elementy do drzewa BST

Temat: Nowy podział forum.
Ja jestem za drzewem BST i sortowaniem przez kopcowanie

Temat: Dobre narzędzie graficzne - rysunek techniczny (drzewka itp)
Witam, poszukuje dobrego narzedzia do wykonywania roznego rodzaju rysunkow technicznych, takich jak drzewa BST oraz bardziej skomplikowane drzewka, grafy itp.
Bede bardzo dzwieczny za wszelaka informacje lub linki. Dzieki.

Temat: BSP

Czy ktos wie gdzie znalezc na sieci jakies objasnienia
(po polsku) na temat drzew bsp ?

BST, a nie bsp koledzy!

Temat: Śmieszne photo
nie, chyba nie fartem ;] chyba po prostu napisalam o drzewie binarnym majac na mysli BST, bo tak u nas to bylo rozumiane w domysle ;]

dwie butelki inca koli poprosze

Temat: słownik, drzewa, kopiec
Może ktoś wie jak zrobić słownik na drzwie BST, AVL , kopcu ?
Proszę o algorytmy, programy itp.

Dzięki DAX

Temat: Odśmiecacz w C++ -- nowa wersja (Smieciuch++ 0.6.3)

na testowym kawałku kodu (tworzenie sporego drzewa BST, tworzenie
i manipulowanie kilkoma śrenio-dużymi tablicami) wyszło 5% szybciej
od boosta z jego zliczaczem referencji i niecałe 2% wolniej od
działania na zwykłych wskaźnikach ze zwalnianiem explicite (delete).

W Kogucie wyszło mi o 10% szybciej (samo tree(2), 10 razy większe,
z pominięciem flush po każdej liczbie).

Po usunięciu wypisywania danych na ekran z obu programów wersja
w Kogucie jest 2 razy szybsza.

Dodatkowo po dwukrotnym zmniejszeniu zakresu, z którego losujemy
liczby (oryginalnie przyjąłem taki jak w glibc, 2**31, co powoduje
u mnie wejście w bignumy dla górnej połowy zakresu) wersja w Kogucie
jest 3.5 razy szybsza.

reprezentacja liści BST z domyślnie skonstruowaną wartością.
Ale starałem się go wiernie naśladować.

Po uproszczeniu tworzenia drzewa w obu językach (zamiast tworzyć puste
drzewo i tam dodawać, tworzę jednoelementowe) wersja w Kogucie jest 4
razy szybsza.

Zmieniłem -O0 na -O2, żeby było sprawiedliwie.

Generatory liczb losowych są różne (u mnie Mersenne Twister), ale
różne kształty drzewa wynikłe z różnych generatorów nie mają znaczenia,
bo przy wielokrotnym losowaniu z różnym ziarnem czasy są prawie takie
same.

Mój kompilator ma dużo powodów, dla których powinien być wolniejszy:
nie robi praktycznie żadnej statycznej analizy typów i np. wyrażenie
w rodzaju tree.left oznacza skok do funkcji i znalezienie pola po nazwie
zamiast sięgnięcia pod stałe przesunięcie w pamięci. Przy operatorze <
dynamicznie rozpoznaje, jakie typy sprawdza. Reprezentacja zmiennych
pól obiektów ma dodatkowy poziom wskaźników (zmienna jest doczepionym
obiektem), czyli węzeł BST to naprawdę 5 obiektów; optymalizacja tego
jest w planach.

Temat: jak to zrobic?
Za kilka dni mam poprawke z algorytmow i struktur danych, a moj problem
polega na tym, ze nie rozumiem dwoch zadan, ktore na bank beda :(
W sieci znalazlem teorie, ale nigdzie nie ma przykladow, ktore pomogly by mi
to zrozumiec. Mam do was wielka prosbe o pomoc w ich rozwiazaniu!
Z gory dzieki!!!

Zad1. Wypisac elementy drzewa zakladajac, ze przegladamy drzewo metoda:
a) preorder
b) inorder
c) postorder
9
/
2 4
/
6 3 5

Zad2. Do drzewa BST dostawic nastepujace elementy: 2,10,5(w podanej
kolejnosci).
5
/
2 8
/
2 4 15

Temat: [BC3.1] Jak zaalokować wiecej niż 640 K RAM
Od razu zaznaczam, ze nie jestem wyga od C++ a jak mi cos nie wychodzi, winy
szukam najpierw u siebie ale teraz zrobillo sie tak dziwnie, ze zaczynam
miec watpliwosci czy dalsze sprawdzanie kodu cos da. Rzecz wyglada tak:

--program:
Realizuje jakis algorytm, mniejsza z tym jaki (bo problem nie dotyczy
algorytmu).Troche wywoluje new i delete (np. w drzewie BST). Nie otwieram
plikow, wszystko jest w jednym procesie/watku (nic nie dzieje sie
rownolegle), poza glutem z openGL czysty C++. Dziala to na win XP.

--problem:
od czasu do czasu wyskakuje mi komunikat:

"Unhandled exception at 0x7c901230 in nazwaprogramu.exe: User breakpoint."

i w oknie debugera wyskakuja windowsowe pliki: dbgheap.c, fputs.c, free.c,
maloc.c, write.c -- w zaleznosci chyba od temperatury za oknem.

--Co jest dziwne:
Na win XP z VC++7 w trybie debug mam ten problem. Build w trybie Release
daje mi execa ktory liczy co powinien bez wywalania sie. Na tym samym
komputerze sprawdzam w trybie debug na VC++5 i jest OK !!! Wywalanie
wystepuje w dosc roznych okolicznosciach. Na przyklad w trybie krokowym
wchodze do linii:

cout << "fragment:" << w-p();

majac pewnosc (dobra, niczego juz nie jestem pewny), ze w nie wzial sie z
kosmosu. Debugger wchodzi do metody obiektu w:

int& p(void) {
assert ( this !=NULL );
return this-fragmentINDX-p;

};

I widze w okienku podgladu zmiennych, ze wszystko wyglada tak jak to z
algorytmu wynika (a nie jakies krzaczory)

metoda sie konczy, wychodze z niej. A przy probie przerobienia nastepnej
linii... BUM. Unhandled exception...Do tej pory, jak takie rzeczy jak mi
wyskakiwaly to po krotkim czasie wiedzialem, ze np. cos pokiepscilem ze
wskaznikami. W tym akurat przypadku pojawia sie plik windowsowy write.c i
zielona strzaleczka pokazujaca:

if ( WriteFile( (HANDLE)_osfhnd(fh),
lfbuf,
(int)(q - lfbuf),
(LPDWORD)&written,
NULL) )

Nie oczekuje rozwiazania problemu. Nie przychodzi mi do glowy wklejac
dlugasne listingi bo i tak nikt tego nie bedzie analizowal. Tylko czy to
jest normalna sytuacja? Czy mozna jakos tak zryc pamiec, ze blad wyskoczy
pozniej i w dziwnym miejscu? Czy moze byc blad w srodowisku
programistycznym(w co watpie)?

Temat: Sieci neuronowe

Siedze sobie wlasnie na bardzo "ciekawej" lekcji
tzw. informatyki i slucham bezsensownego piep...nia
belfra na rozne glupie tematy. No bo po co mi
znajomosc jakichs 5 algorytmow sortujacych albo
drzew BST, AVL lub co gorsza beznadziejnych
triangulacji, Hufmannow itd... A ja jestem przeciez
normalnym czlowiekiem (o sorry - uczniem), ktoremu
na nic to sie nie przyda. Wszystko byloby cacy,
gdyby nie koniecznosc pisania na ocene w/w algorytmow
i to w dodatku w dzialajacej wersji. To jeszcze moge
przezyc (jak nie zrobie sam to "zerzne" (czyni tak 80%
klasy)), ale szantazowanie mnie klasowka typu "jaki
blad zawiera (piecio stronicowy) program" to juz troche
za duzo.
Raz zdarzylo sie, ze uslyszalem cos o sieciach neuronowych.
Zapewne nie sluchalbym tych "bzdur", gdyby nie fakt, ze
gdzies juz o tym slyszalem. Postanowilem posluchac sora,
lecz mowil nieciekawie i niezrozumiale (jak zwykle zreszta).
Dlatego mam prosbe: czy ktos moglby mi w przystepny sposob
wyjasnic jej dzialanie? Za odpowiedz z gory dziekuje!

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
_/ _/
_/ Andrzej Siewruk _/
_/ _/

_/ _/
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

Temat: SZYBKO!!! drzewa wywazone

witam
(to moj debiut na grupach dyskusyjnych :))
drzewa wywazone sa nazywane drzewami AVL. w takim drzewie dla kazdego wezla
roznica wysokosci jego poddrzew wynosi co najwyzej 1.
waga okresla w ktora strone drzewo jest przechylone (np. -1 w lewo, 0 -
rownowaga,
1 prawo)
wywazanie drzewa AVL (BST) jest wykonywane poprzez rotacje wezlow:

1)
1

2 2
- /
3 1 3

2)
3
/
2 - 2
/ /
1 1 3

3)
1 1

3 - 2 - dalej jak w 1)
/
2 3

4)
3 3
/ /
1 - 2 - dalej jak w 2)
/
2 1

(mam nadzieje ze to jakos widac)

istnieja rowniez drzewa dokladnie wywazone. tu dla kazdego wezla roznica
liczby wezlow lewego poddrzewa i liczby wezlow prawego poddrzewa
wynosi co najwyzej o 1

przykladu nie podaje gdyz c dopiero sie ucze i nie wiem ile czasu zajeloby

*********************************
pozdrowienia
Grzegorz "Zuku" Zukowski

Temat: liczenie roznicy wierzcholkow w drzewie binarnym

| Co to jest BST? Wierzchołek? Droga z lewej (prawej)? Najdłuższa droga?
| Drzewo binarne? To nie są pojęcia znane bezwzględnie wszystkim
| programistom. Co to jest encja i ODBC?
ehhh. co to jest encja i ODBC to wiem (jak wiekszosc na tej grupie)

wierzcholki to jego elementy, a drzewo moze wygladc np. tak:
7
/
/
2 15
/
/
1 5
cala idee moge podac na maila wedle zyczenia.

1. Załóżmy, że węzły tego drzewa to obiekty albo pointery
2. Ma Pan dane p1 i p2, trzeba obliczyć pomiędzy nimi różnicę
3. Trzeba obliczyć osobno poziom zagłębienia p1 i p2 i potem od siebie
odjąć, poziom zagłębienia można policzyć mniej więcej tak :

a. wariant prosty, kiedy węzły mają atrybut parent wskazujący na rodzica

p:=p1;
iLevel:=0;
while p<pRoot do
begin
p:=p.Parent; // czy p^.Parent jesli to Pointer
Inc(iLevel);
end;

b. wariant mniej wygodny, jesli nie ma atrybutu Parent - trzeba
przetrwaersować drzewo, pewnie najwygodniej rekurencyjnie, i w ten
sposób odnotowywać poziom zagłębienia, zatrzymując się w momencie
odkrycia że bieżący wierzchołek to p1/p2, można dla obydwu zrobić to w
jednym trawersie drzewa

Temat: Krytyka Olimpiady

Subject: Subtelna krytyka

Czy aby na pewno? Zdecydowanie lepiej pasuje tu wyraz bezczelna,
chamska, prostacka itp.

Wedlug mnie i mojego kolegi wasze zadania informatyczne nie daj?
optymalnych rezultatów nauki tego przedmiotu.

Wy oczywiscie wszystkie rozumy pozjadaliscie.

[ciach]

Z kumplem nie bedziemy rozwiazywac waszych popieprzonych zadan z
infy. Te zadania sa chore. Jakies powalone ciagi i inne rzeczy zwi?zane z
matematyka. TO MA BYC OLIMPIADA Z INFY A NIE Z MATY.

I jest to olimpiada z informy. Wiesz jakie przedmioty kroluja na
pierwszym roku informy na polibudzie w poznaniu (zdaniem niektorych
najlepsza informa w Polsce)? Po pierwsze matematyka w czystej postaci.
Po drugie polaczenie matmy i komputerow. Po trzecie przedmioty typowo
informatyczne. A wsrod nich w drugim semestrze najwazniejszy - algorytmy
i struktury danych. Sortowanie, grafy, drzewa bst, listy dynamiczne,
programowanie dynamiczne, algorytmy SPT, programowanie zachlanne.

Wg mnie ten cały fun

polega na tym ze zamiast pisac jakies rownania w zeszycie pisze sie je w
jezyku programowania.

Bo tak jest latwiej i to jest wlasnie informatyka. Klasyczny przedmiot
ktory to ukazuje to elementy metod numerycznych. Robilismy np rozne
bzdury na macierzach. Wzory byly podobne jak na matmie, ale trudniejsze.
Po co? Ano po to, ze jakbys mial obliczac wyznacznik macierzy 30x30 to
bys sie zaje***

Taka sztuka dla sztuki. 0 (zero) pozytku z takich

zawodow.

Cwiczy umysl - naprawde polceam.

Zadania powinny byc zupelnie zmienione np. napisz mozliwie

najlepszego playera audio w DELPHI lub innym jezyku wizualnym.

A to jaki ma cel? Bedziesz sie meczyl kilka tygodni i otrzymasz cos co
dziala 1000 razy gorzej niz winamp.

Bezsensem
jest pisanie w archaicznym pascalu czy C.

Pascal jest archaiczny. Jego odmiana obiektowa jest natomiast doskonala
do nauki programowania. Ale nie wygaduj bzdur ze archaiczne jest C, gdyz
jest to jezyk nadal uzywany i to bardzo szeroko. Jest to czesc C++,
ktory jest notabene najlepszym i najwazniejszym jezykiem programowania.

[ciach]

Piszecie w powalonych WORDACH i innych
OFFICACH

No tak, a dobry informatyk to w czym powinien pisac? Pewnie powinien
wlaczyc jakiegos RADa i samemu sobie zrobic pakiet biurowy. Zajmie mu to
kilka miesiecy i bedzie dzialalo 1000 razy gorzej niz Office, ale bedzie
informatykiem, prawda?

zapewne pirackich bo jaką szkołe stac na orginal.

Za to sie idzie do wiezienia. Zadna szkola nie moze sobie na to pozwolic.

[ciach]

Nie mam pojecia czy jakikolwiek
informatyk posiada wiedze wieksza ode mnie.

To ja ci powiem: kazdy.

Moja
nauczycielka z infy nie znal nawet HTML i kumpel musial ją nauczyc.

To mnie wku**** 10 lat temu, gdy komputery nie byly zbyt powszechne, jak
ktos przy kompie siedzial, gral dniami i nocami, to niektorzy na takiego
mawiali komputerowiec, informatyk. Teraz informatyka urosla w ich
oczach. Trzeba znac HTMLa zeby byc informatykiem... Zalosne... Jest to
najbardziej niepotrzebny z jezykow skryptowych jakiego sie uczylem na
studiach. Jest tyle kursow w necie, ze nie ma potrzeby uczyc sie znacnzikow.

Lekcje
infy to kompletna parodia ,same nudy. Nic tylko word i word i pisanie na
klawiaturze.

Ty za to jestes genialny i lepiej bys prowadzil. Tak zeby zaciekawic i
ulatwic zycie rowniez tym, ktorym ta informa do niczego nie bedzie
potrzebna.

PS3.Sorki za orty i niekiedy brak kodowania --ASCII rulez

Nie przepraszaj tylko sie wstydz za siebie durniu!!
Moze mi jeszcze powiesz ze taki wlasnie list wyslales do organizatorow?
Bo jesli tak to nie obrazajac Ciebie jestes debilem. Ciebie nie powinni
uczyc HTMLa tylko kultury osobistej gdy piszesz list oficjalny,
zwlaszcza do kogos kto jest od Ciebie starszy i madrzejszy.

Informa to nie jest robienie kodekow itp. Informa to przede wszystkim
dzial matematyki. Jeden z moich wykladowcow, swoja droga najlepszy
informatyk w Polsce, chyba nawet w swoim gabinecie nie ma komputera.
Uprawia ta bardzo matematyczna czesc informatyki.
Masz poglady zdespeorwanego dziecka, ktory mial wielkei ambicje, a tu
sie okazalo, ze nie jest takim dobrym informatykiem jak myslal...

Temat: C/C++
Potrzebuję, któregoś z tych programów napisanych w c/c++, jakbyście mieli gdzieś gotowe to bym był bardzo wdzięczny.

1. Problem konika szachowego.
Znaleźć taką drogę aby poruszając się ruchem konika szachowego, odwiedzić wszystkie pola na szachownicy. W każdym polu
konik może stanąć tylko raz. Program należy napisać używając stosu (bez rekurencji).
Rozwiązanie problemu należy przedstawić graficznie. (może być tryb tekstowy)

2. Wieże Hanoi
Rozwiązanie problemu wież Hanoi z wiazualizacją. (może być tryb tekstowy)
Program należy napisać używając stosu (bez rekurencji).

3. Drzewo binarne BST
Wyświetlanie drzewa binarnego. Jeżeli drzewo nie mieści się na ekranie trzeba umożliwić użytkownikowi wyświetlenie
niewidocznej części. Aktualny węzeł powinien być wyróżniony. Poruszanie się między węzłami realizujemy za pomocą strzałek
(<- - przejście do lewego syna, -> przejście do prawego syna, ^ - przejście do ojca).
Możliwość dodawania elementów do drzewa. Zapis i odczyt drzewa z pliku.

4. Przeglądarka plików tekstowych z podświetlaniem słów kluczowych (np. słów kluczowych języka C).
Program powinien umożliwiać:
- przeglądanie plików bez ograniczenia co do rozmiaru pliku,
- przewijanie zawartości (strzałkami - o jedną linię w górę , w dół lub na boki, PageUp i PageDown o całą stronę)
- edycję, dodawanie i usuwanie słów kluczowych

5. Gra Snake
Aktualna liczba punktów powinna być wyświetlona na ekranie. Na wyższych poziomach powinna zwiększać się prędkość gry, oraz
ilość przeszkód. Rejestrowanie najlepszych wyników.
(Program może być zrealizowany w trybie tekstowym.)

6. Norton Commander
Program w stylu Norton Commander, realizujący następujące opcje:
- kopiowanie, usuwanie, przenoszenie plików oraz katalogów (wraz z zawartością)
- operacje wieloplikowe (np. użytkownik może zaznaczyć kilka plików i wszystkie je skasować)
- zaznaczanie plików według podanej przez użytkownika maski (np. "*.c", "pr*.*")

7. Prosty edytor tekstowy
Zapis edytowanego tekstu do pliku. Odczyt tekstu z pliku. Możliwość zaznaczania fragmentu tekstu - zaznaczony tekst można
usunąć, przekopiować lub przenieść w inne miejsce. Przewijanie edytowanego tekstu (strzałkami - o jedną linię w górę , w
dół lub na boki, PageUp i PageDown o całą stronę)

8. Gra w statki
Użytkownik gra z komputerem, możliwość ustalania wielkości planszy, ilości i wielkości statków.

9. Kalkulator
Kalkulator wykonujący podstawowe działania (+ - * / ^(potęga np. 2^3=>23), sqrt - pierwiastek). Do wykonywania
obliczeń należy wykorzystać stos i odwrotną notację polską (ewentualnie prefiksową).

Teoria do kalkulatora

10. Kalkulator macierzy
Program ma umożliwiać dodawanie, odejmowanie, mnożenie oraz obliczanie wyznacznika macierzy. Macierze, na których będą
wykonywane działania mają być wczytywane z klawiatury lub też z pliku (ze sprawdzaniem poprawności danych). Możliwość
zapisania wyniku do pliku. Wykorzystać dynamiczne struktury danych.

11. Baza danych
Należy wykorzystać dynamiczne struktury danych. Informacje zawarte w bazie powinny być przechowywane w plikach.
Baza powinna realizować następujące zadania:
-zapis do i odczyt z pliku (lub plików)
-dodawanie, kasowanie, edycja elementu
-sortowanie (użytkownik powinien mieć do wyboru w/g jakiego klucza chce bazę -sortować klucza)
-wyszukiwanie elementów w/g zadanych przez użytkownika kryteriów (np. lata pomiędzy 1990 - 2003) (program ma wyświetlać
wszystkie elementy bazy spełniające dane kryteria)