-
X-Received: by 10.157.26.120 with SMTP id u53mr285461otu.18.1462716915860; Sun, 08
May 2016 07:15:15 -0700 (PDT)
X-Received: by 10.157.26.120 with SMTP id u53mr285461otu.18.1462716915860; Sun, 08
May 2016 07:15:15 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!go
blin3!goblin.stu.neva.ru!news.ripco.com!news.glorb.com!i5no5555835ige.0!news-ou
t.google.com!uv8ni215igb.0!nntp.google.com!sq19no4024166igc.0!postnews.google.c
om!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Sun, 8 May 2016 07:15:15 -0700 (PDT)
In-Reply-To: <ngkcdb$2mt$2@node2.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=5.172.247.231;
posting-account=CvUQzQoAAABvVQmR58QmR6N4Cev1qhAS
NNTP-Posting-Host: 5.172.247.231
References: <ngk077$d49$1@node2.news.atman.pl>
<c...@g...com>
<ngkcdb$2mt$2@node2.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e...@g...com>
Subject: Re: Szukanie najdłuższego ciągu w drzewie
From: bartekltg <b...@g...com>
Injection-Date: Sun, 08 May 2016 14:15:15 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:209364
[ ukryj nagłówki ]On Saturday, May 7, 2016 at 11:27:08 AM UTC+2, Borneq wrote:
> W dniu 07.05.2016 o 08:34, M.M. pisze:
> > najkrótszy czas, to problem jest skomplikowany. Można
> > zapamiętać długość najdłuższego ciągu w każdym węźle. Niestety
> > przez to wstawianie i usuwanie będzie zajmowało nieco więcej
>
> Normalnie to bym przechodził w głąb zapisując głębokość każdego węzła i
> szukając najgłębszego. O tyle - proste.
I tak zrób...
> Jednak to drzewo jest bardzo mało rozgałęzione, ale za to bardzo
> głębokie. Nie chcę rekursji z ponad 400 tys poziomów.
To nie używaj rekursji. Przechodzenie drzewa w głąb/w szerz
bez rekursji, ale za pomocą stosu/kolejki (struktury denych choćby
z stl) to podstawowa technika. Pierwszy rozdział Algorytmy struktury
danych Diksa/rytra. W Cormenia też musi być.
O, i nawet przez aero mi przeciekło, że w wiki jest:
https://en.wikipedia.org/wiki/Depth-first_search#Pse
udocode
A non-recursive implementation of DFS:[6]
1 procedure DFS-iterative(G,v):
2 let S be a stack
3 S.push(v)
4 while S is not empty
5 v = S.pop()
6 if v is not labeled as discovered:
7 label v as discovered
8 for all edges from v to w in G.adjacentEdges(v) do
9 S.push(w)
Tylko zamiast indeksu wierzchołka "pushuj" parę indeks
<wierzchołka, głebokosc>
Złożonośc pamięciowa O(wysokość drzewa).
Pseudokod jest dla DSF dowolnego grafu, więc nawet możesz
linijkę 7 (i znaczniki w wierzchołkach) pominać
> Chcę zapisywać na stos tylko gdy jest rozgałęzienie a ono ma być rzadko
Nadal możęsz to zrobić (w 7 linijce while "jeden potomek" to
v:= syn v; glebokosc++, Po zrobieniu POP i tak odczytasz wysokość
ze stosu.) ale nadal masz pamieciowo O(wysokosć),
przykładem jest drzewo, gdzie każdy lewy syn nie ma potomków,
a każdy (poza ostatnim) prawy syn ma 2 potomków
/\
/\
/\
/\
/\
pzdr
bartekltg
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-09 Chess
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 Drukara laserowa
- 2024-05-09 Chess
- 2024-05-09 sedzia Szmydt
- 2024-05-09 Chess
- 2024-05-09 [newbie] Jaki multimetr za 2-4 stówy?
- 2024-05-09 Chcą poł. tunelem Europę z Afryką - 27km za 6GEUR
- 2024-05-09 Gorzów Wielkopolski => Konsultant/Wdrożeniowiec Comarch ERP XL <=
- 2024-05-09 Kraków => Senior PHP Developer (Symfony) <=
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 Chess
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 szafka sieciowa