Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
02.01.2004, 15:41 Uhr
BoNeSpiRit

Also ich bin grad dabei das Partial Digest Problem (PDP) zu coden und hab folgendes Problem:
Gibt es in C++ eine einfache Möglichkeit zu prüfen ob a in b enthalten is, wobei a und b sortierte Listen von zahlen sind?
Welche Datenstruktur ich für die beiden Listen nehme is relativ egal.
Axo... a und b sind Listen von Zahlen.
Kann mir da irgendjemand helfen? Oder nen tip geben welche datenstruktur am sinnvollsten is?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
02.01.2004, 15:46 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

Willst du einzelne Items aus a in b schnellstmöglich suchen oder ob komplett a in komplett b vorhanden ist?

Ich würde mal sagen man könnte es so machen:

ErstesItem von a in b suchen
wenn wert von b > als a (da ja sortierte Listen) kann abgebrochen werden
wenn gefunden, dann 2tes Item (das ja größer ist) ab der selben stelle suchen lassen, usw.
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
02.01.2004, 15:50 Uhr
Pablo
Supertux
(Operator)

Ich würde sagen, ja. Es gibt verschiedene Möglichkieten sowas zu prüfen. Aber wie man sie macht, hängen von den Datenstrukturen ab, die man benutzt.
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
02.01.2004, 16:06 Uhr
BoNeSpiRit

Ich will schon komplett a in b enthalten, des is die erste "richtige" Abfrage beim PDP.
@4c6f2e: So hab ich mir das auch schon vorgestellt.
Die Laufzeit des PDP is ja ziemlich fürn A****, aber dachte, vielleicht gibs ja doch ne elegantere Lsg...

@Pablo: Sicha, aber im Grunde is das von FloSoft am Effektifsten, oder?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
02.01.2004, 17:11 Uhr
BoNeSpiRit

Zitat:

BoNeSpiRit postete
@4c6f2e

was da scho wieda im speicher gewesen? ich meinte natürlich
@FloSoft...

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
02.01.2004, 17:18 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

hab mich schon gewundert

--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
02.01.2004, 17:23 Uhr
0xdeadbeef
Gott
(Operator)

Es gibt eine Template-Funktion std::includes für sowas. Zum Beispiel:

C++:

#include <list>
#include <algorithm>

//...
std::list<int> a, b;
//... Listen füllen und sortieren
if(std::includes(b.begin(), b.end(), a.begin(), a.end())) {
//...b enthält a
}

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
03.01.2004, 14:35 Uhr
BoNeSpiRit

Klasse !!!
Werd ich gleich ma ausprobiern

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: