Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
21.10.2005, 11:54 Uhr
mischa
Fragender

hi
ich versuch da einen algoritmus zu schreiben der nach prüfft ob irgend ein element in einem int arrey mehrmals vorkommt und dan false ausgibt wenn das der fall ist aber irgend wie klapts net und da wollte ich fragen ob da was in der STL gibt
--
Latein Unterricht ist die spätere Rache der Römer an den Germanen.

Profil || Private Message || Suche

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

001
21.10.2005, 12:28 Uhr
virtual
Sexiest Bit alive
(Operator)

Nein, in dieser allg. Frm gibt es nichts fertiges. Wenn das Array bereits sortiert ist, dann ist die Aufgabe ja recht trivial lösbar, ich denke du gehst daher von dem Fall aus, daß das Array nicht sortiert ist.

In diesem Fall mußt Du die Entscheidung treffen, ob du eine Lösung suchst, welche Speicherplatzoptimal oder Laufzeitoptimal ist.

Laufzeitoptimal ist folgende Vorgehensweise: Baue ein Set auf, welches alle Elemente enthält. Da ein set keine Duplicate erlaubt, muß, wenn alle Elemente verschieden sein sollen, das Set dann die gleiche Größe haben wie das Array. Also:

C++:

#include <iterator>
#include <set>

template<typename I>
bool is_unique(I begin, I end) {
std::set<typename std::iterator_traits<I>::value_type> s(begin, end);
return end-begin == s.size();
}

Dies hat den Speicherbedarf O(N) und die Laufzeit O(N*log N), mit N = Anzahl der Elemente. Für Dinge, einen Komplexen Construktor haben geht hier allerdings auch die Performance etwas in die Knie, weil du die Elemente ja kopierst.

Speichplatzneutral wäre diese Lösung:

C++:

#include <algorithm>

template<typename I>
bool is_unique(I begin, I end) {
    while (begin!=end) {
        I current = begin++;
        if (std::find(begin, end, *current)!=end) {
            return false;
        }
    }
    return true;
}

Diese Lösung hat einen Speicherbedarf von 0 und eine Laufzeit von O(N*N). Für Einfache ints ist sie damit also - grade wenn es viele Elemente sind - deutlich langsamer.

Anwenden kann man beide Algorithmen gleich:

C++:

int a[] = { 1, 2, .... }

bool alle_verschieden = is_unique(a, a+sizeof(a)/sizeof(*a));

bzw.

C++:

std::vector<int> a;

bool alle_verschieden = is_unique(a.begin(), a.end());

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

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

002
21.10.2005, 13:20 Uhr
mischa
Fragender

danke (ist ungefähr 4 mal so kurz wie maine lösung

)
kann man das auch auf matrizen ausweiten
--
Latein Unterricht ist die spätere Rache der Römer an den Germanen.

Profil || Private Message || Suche

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

003
21.10.2005, 13:44 Uhr
virtual
Sexiest Bit alive
(Operator)

Das hängt ziemlcih stark von Deiner Matrixdefinition ab.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

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

004
21.10.2005, 19:22 Uhr
mischa
Fragender

ich habe das jetzt ausprobiert und es funktioniert perfekt
danke für die hilfe
--
Latein Unterricht ist die spätere Rache der Römer an den Germanen.

Profil || Private Message || Suche

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

005
21.10.2005, 19:31 Uhr
J-jayz-Z
Perl Crack ala Carte
(Operator)

Das mit der Matrix? Könntest du das Ergebniss vielleicht posten? Würd mich auch interessieren..
--
perl -Mstrict -Mwarnings -e 'package blub; sub new { bless {} } sub bar {my $self=shift; $self->{bla}="66756e2d736f66742e6465"; return $self->{bla};} my $foo=blub->new();print "Hallo ";print pack("H*",$foo->bar()); print "\n"'

Profil || Private Message || Suche

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

006
22.10.2005, 12:16 Uhr
mischa
Fragender

also das ist so
in der schule mussten wir einen zwei demensionalen arrey(9x9) mit ganzen zahlen zwischen 1-9 auffüllen
regeln
in einer zeile darf eine zahl nur einmal vorkommen und in einer spalte darf eine zahl nur einmal vorkommen
ich habe versucht den code von virtual auf einen zwei demensionalen vector anzuwenden aber ging irgend wie net deshalb habe ich es einfach mit ein paar schleifen erledigt(zu erst alle spalten dann alle zeilen nachprüffen)
--
Latein Unterricht ist die spätere Rache der Römer an den Germanen.

Profil || Private Message || Suche

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

007
22.10.2005, 14:20 Uhr
imhotep
followed the white rabbit

Die einfachste Methode ist doch jede Zeile um eins zuverschieben

Code:

1,2,3,4,5,6,7,8,9
9,1,2,3,4,5,6,7,8
8,9,1,2,3,4,5,6,7
7,8,9,1,2,3,4,5,6
6,7,8,9,1,2,3,4,5
5,6,7,8,9,1,2,3,4
4,5,6,7,8,9,1,2,3
3,4,5,6,7,8,9,1,2
2,3,4,5,6,7,8,9,1

Aber ich denke, das ist nicht Sinn der Sachen

Du kannst ja bei 1 anfangen und die erst mal in deine Matrix "reinstreuen", so dass sie sich nicht in die Quere (bereits eine 1 in der Zeile/Spalte) kommen, dann die 2 und so weiter. Hab jetzt keinen mathematischen Beweis geführt, aber denke so kannst du deine Matrix füllen

Profil || Private Message || Suche

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

008
22.10.2005, 19:31 Uhr
mischa
Fragender

das auffüllen ist nicht das problem wir müssen nachprüffen ob es richtig ist
--
Latein Unterricht ist die spätere Rache der Römer an den Germanen.

Profil || Private Message || Suche

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

009
22.10.2005, 20:38 Uhr
imhotep
followed the white rabbit

Was ist mit der Zeilen- und Spaltensumme?
Du addierst die Zahlen jeder Zeile und jeder Spalte und es muss immer 45 rauskommen.

Kannst ja vielleicht mal ein paar Beispiele generieren lassen und testen, ob wenn überall 45 rauskommt trotzdem noch es möglich ist, dass 1 Zahl doppelt vorkommt.

Oder so:
Du legst dir ein 9 Felder-Array an und setz alle auf 0, dann fängst du in der ersten Zeile an.
Wenn du eine Zahl findest, erhöhst du den Wert, an der Stelle in deinem Kontrollarray um ein, dessen Position der Zahl entspricht (du findest 2, also array[1] ++). Wenn du feststellst, dass die Zeilennummer kleiner als der Wert an der Stelle ist, dann ist diese Zahl zuoft dagewesen.

Bsp.:
Kontrollarray: 0,0,0,0,0,0,0,0,0
1. Zeile: 1,2,3,4,5,6,7,8,9
Kontrollarray: 1,1,1,1,1,1,1,1,1
2. Zeile: 2,3,4,5,6,7,8,9,2
Kontrollarray: 1,3,2,2,2,2,2,2,2 <- 3 darf nicht sein, darum Fehler

Und zur kontrolle das ganze auch mit den Spalten.

Profil || Private Message || Suche

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

Seiten: > 1 < [ 2 ] [ 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: