Analysieren eines Arrays

Gin

Bin noch im 1. Semester und deshalb hab' ich leider kein Plan von dem was "unique", " std::map", etc... ist.
Könntet ihr vielleicht konkrete Codestellen kommentieren, bzw. Codebeispiele
geben?

Jester

Kannst Du mal ein Feld angeben, bei dem Deine Variante nicht funktioniert?

Du hast übrigens das Problem, daß in diesem int-Array merke_a schon Zahlen drinstehen, wenn die zufällig mal mit den anderen Zahlen übereinstimmen kriegst Du falsche Ergebnisse. Mach lieber einer bool-Array markiert, die setzt Du alle auf false. Beim suchen nach doppelten setzt Du sie dann auf true.

Die hier vorgeschlagene Variante ist das Array zu sortieren und anschließend die doppelten rauszuschmeißen. Die Anzahl der Elemente danach ist genau die Anzahl der verschiedenen. Das mit dem map und unique und set bezog sich dabei auf die Container aus der Standardbibliothek.

Eine Möglichkeit sieht zum Beispiel so aus:

#include <vector>
using namespace std;

int verschieden(int feld[])
{
  vector<int> v(feld, feld+10);  // Feld kopieren
  sort(v.begin(), v.end());      // sortieren
  v.erase(v.unique(),v.end());   // doppelte Elemente nach hinten schieben+löschen
  return v.size();               // Anzahl der Elemente zurückgeben
}

Aber ob Dir diese Lösung allzuviel bringt ist fragwürdig. Für den Lerneffekt solltest Du lieber versuchen auch den andere Algorithmus noch zu Laufen zu bringen.

MfG Jester

davie

eigentlich brauchst du überhaupt kein zweites array.

(achtung schon etwas vorgedacht. wenn du alleine weiterdenken willst, bitte überlesen)
du gehst einmal alle elemente durch, und siehst nach, ob das aktuelle element schon in den bis jetzt durchgelaufenen elementen vorhanden ist.

wenn schon, den zähler nicht inkrementieren und nächstes element.
wenn nicht, zähler inkrementieren und zum nächsten element

Gin

2Jester:
Danke für das konkrete Beispiel.
Du redest aber von "doppelten" Werten. Was ist aber, wenn ein Wert z.B. drei Mal in einem Array vertreten ist?

Deine Funktion werde ich mal ausprobieren. Von "Vector.h" hab' ich übrigens noch gar nichts gehört, somit ist mir deine Variante auch nicht eingefallen.
Aber ständig lernt man was Neues...

Und hier ein Feld, wo mein Algorithmus versagt:

int feld[10]={-5,-4,-3,-2,-1,0,1,2,3,4}

2 Davie:

Bitte genauer.
Ich vergleiche das erste Element mit dem Rest, dann das zweite Element mit dem Rest, etc...? Verstehe ich das richtig?

davie

du hast zb

Element: 1 2 3 4 5 6 
Wert:    2 3 2 1 3 1

du weißt, dass sicher eine zahl vorkommt, also fangen wir mit element nr. 2 an (3); zähler also gleich 1.

schaue nach, ob es unter den bis jetzt kontrollierten elementen (das war das erste: 2) eines gibt, das gleich dem aktuellen ist.
nein, also zähler inkrementieren, nächstes elemtn (nr. 3 - wert 2):

schaue nach, ob es unter den bis jetzt kontrollierten elementen (das waren 2 3) eines gibt, das gleich dem aktuellen ist.
ja, das erste. alle anderen brauchst du jetzt nicht mehr ansehen, nächstes element (nr. 4 - wert 1):

schaue nach, ob es unter den bis jetzt kontrollierten elementen (2 3 2) eines gibt, das gleich dem aktuellen ist.
nein. zähler inkrementieren, nächstes element (nr. 5 - wert 3):

schaue nach, ob es unter den bis jetzt kontrollierten elementen (2 3 2 1) eines gibt, das gleich dem aktuellen ist.
(schaue 1. an - nein) (schaue 2. an -ja)
ja, das zweite. alle anderen brauchst du jetzt nicht mehr ansehen, nächstes element (nr .6 - wert 1):

schaue nach, ob es unter den bis jetzt kontrollierten elementen (2 3 2 1 3) eines gibt, das gleich dem aktuellen ist.
fertig.

ist dafür langsamer als ein extra array anzulegen, dafür brauchst du keines.

soll ja nur ein beispiel sein, wie man sich sowas überlegen kann:
du kannst dir zuerst selbst überlegen, wie du es als mensch machen würdest.
mit dem array geht das dann ca so:
schaue ein element an, ist es in meiner liste schon vorhanden, dann weiter
ist es nicht vorhanden, füge es ein und weiter.

probier deinen algorithmus selbst aus, in gedanken. das hilft oft!

Jester

Gin schrieb:

Du redest aber von "doppelten" Werten. Was ist aber, wenn ein Wert z.B. drei Mal in einem Array vertreten ist?

da hab ich mich wohl undeutlich ausgedrückt... ich meine mehrfach enthaltene.

Was kommt denn bei dem von Dir genannten Feld heraus?

Könnte es damit zusammenhänge, daß das merke-Feld bereits Zahlen enthält und so durch blöde Zufälle bestimmte Zahlen nicht markiert werden?

Fülle doch das merke-Feld zu Beginn mal mit lauter Zahlen, die garantiert nicht im Feld vorkommen. Verschwindet dann das Problem?`

MfG Jester

Gin

2 Davie:
Alles klar. Danke!
Aber ist dein Vorschlag mit dem 2. Array nicht genau das was ich implementiert hab'?

2Chester:
Bei meinem Feld kommt "5" raus. D.h. die negativen Zahlen werden einfach übersehen. Und zwar nicht nur bei diesem Feld.
Geprüft hab ich das auch mit dem int-Array aus 100 Elementen, der mit der Funktion f(x)=x³ gefüllt war. Dasselbe Problem.
Als Anzahl der ungleichen Elemente wurde "51" ausgegeben.

Jester

Sehr merkwürdig... bei mir funktioniert Dein Code. Auch wenn er noch nicht ganz sicher ist. Beim abprüfen auf doppelte schaust Du die letzte Zahl nicht an, und das Problem mit dem vorbelegten Feld muß Du noch lösen.

MfG Jester

Gin

Seltsam, dass der bei dir funktioniert.
Ich werde schauen, dass ich damit klarkomme.

2All:
Danke für euere Hilfe!

MfG,

Gin

CarstenJ

Kann es sein, dass die Aufage gar nicht so trivial ist?

CarstenJ

Also ich scheitere an dem Problem kläglich. Hörte sich erst nicht schwierig an. Naja, ich habs jetzt so gemacht, dass ich erste die Liste sortiert habe. Die Hinweise funktionieren (bei mir zumindest) nicht, wenn Zahlen mehr als 2 mal vorhanden sind. Aber mit scheint das zu kompliziert zu sein oder hab ich irgendwie nen Brett vorm Kopf?!?!?!