Arrays vergleichen

[überlebender]

Ich möchte folgende Methode schreiben:

Modifikatoren: public und static
Rückgabetyp: boolean
Methodenname: compareArrays
Übergabeparameter: int-Array a, int-Array b

Die Methode compareArrays gibt genau dann den Wert true zurück, wenn die Werte, die in a und in b enthalten sind, gleich sind und gleich oft vorkommen und in der gleichen Reihenfolge in den jeweiligen Arrays enthalten sind.


Beispiel: Es sei a={1,2,3}, b = {1,2,4}, c={1,3,2}, d={1,2} und e={1,2,3}. Dann ist der Rückgabewert von compareArrays false, mit Ausnahme von compareArrays(a,e) bzw. compareArrays(e,a) bzw. Aufrufen, in denen das gleiche Array zweimal als Übergabeparameter eingegeben wird.

Mein Versuch:

Ich habe Stift und Papier genommen, meine Ideen aufgeschrieben und versucht, diese in einen Code umzuwandeln. Ich bin blutiger Anfänger am Anfang des Informatik Studiums, also seid bitte gnädig.

package a4;

public class A4_main {

    public static boolean compareArrays(int [] a, int [] b) {
      
        for (int i=0; i < a.length && i < b.length; i++) {
          
            if (a[i] != b[i]) && (if a.length[i] != b.length[i]);
          
            return false;
            }
            return true;
            }
}

Hab hier nur geschafft, die Kriterien "gleich" und "gleich oft" zu schreiben.
Bei "gleiche Reihenfolge" habe ich keine Idee.

 

[Oneixee5]

Zuerst würde ich prüfen ob die Arrays auch die gleiche Länge haben. Ist das nicht der Fall ist der Test schon zu Ende. Danach kann man in einer Schleife die Elemente vergleichen.

 

[KonradN]

if (a[i] != b[i]) && (if a.length[i] != b.length[i]); Das ";" am Ende ist sowas wie ein leeres Statement. Die if Anweisung ist da also komplett zu Ende. Damit wird immer ein return false ausgeführt!

Wenn Du das Semikolon weg löschst, dann dürfte es schon (fast) funktionieren. Der Hinweis von @Oneixee5 ist aber wichtig bezüglich der Größe der Arrays. Bei den Beispielen wird der Code - so du ihn wie vorgeschlagen korrigierst - wohl funktionieren. Aber teste einmal die Vergleiche mit einem der Array mit einem leeren Array! Was passiert dann? Weil das leere Array keine Elemente hat geht er nicht in die Schleife und somit kommt er nie zu dem Check der Längen und es wird dann true zurück gegeben.

 

[KonradN]

Den Punkt hatte ich noch übersehen, da ich mich auf den Code konzentriert habe:

Hab hier nur geschafft, die Kriterien "gleich" und "gleich oft" zu schreiben.
Bei "gleiche Reihenfolge" habe ich keine Idee.

Was bedeutet denn gleiche Reihenfolge der Werte im Array?

1, 2, 3 und 3, 2, 1 hätten jeweils die gleichen Werte aber nicht die gleiche Reihenfolge.

Unter dem Strich bedeutet das doch, dass die Werte an einer Position i bei beiden Array den gleichen Wert haben müssen. Und das prüfst Du ja in deiner Bedingung ab: Wenn an Position i die Werte von Array a und Array b ungleich sind, dann sind die Array nicht gleich.

 

[überlebender]

Den Punkt hatte ich noch übersehen, da ich mich auf den Code konzentriert habe:

Was bedeutet denn gleiche Reihenfolge der Werte im Array?

1, 2, 3 und 3, 2, 1 hätten jeweils die gleichen Werte aber nicht die gleiche Reihenfolge.

Unter dem Strich bedeutet das doch, dass die Werte an einer Position i bei beiden Array den gleichen Wert haben müssen. Und das prüfst Du ja in deiner Bedingung ab: Wenn an Position i die Werte von Array a und Array b ungleich sind, dann sind die Array nicht gleich.

So hab da jetzt einen Lösungsansatz gefunden, weiß aber nicht ob das so klappt.

package a4;

public class A4_main {

    public static boolean compareArrays(int [] a, int [] b) {
      
        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }
      
        for (int i=0; i < a.length; i++) {
          
            if (a[i] != b[i]) {           // gleiche Werte
          
            return false; }
      
        for (int x=0; x < a.length || x < b.length; x++) {
          
            if (a[0] != b[0]);           // gleiche Reihenfolge (hier bin ich mir nicht sicher ob das klappt)
            return false;
        }
          
          
            }
            return true;
            }
  
public stativ void main (String [] args) {
    System.print.out()   //?
}

*In Zeile 19 möchte ich prüfen, ob beide Arrays die gleiche Reihenfolge haben.
Meine Idee war, dass wenn array a Index 0,1,2,3 den gleichen Wert hat wie array b Index 0,1,2,3 usw., dann soll true rauskommen, andernfalls false

 

[mihe7]

if (a[i] != b[i]) && (if a.length[i] != b.length[i]);

Den Punkt bzgl. des Semikolons hat @KonradN ja schon angesprochen, wenn wir das mal etwas anders formatieren, sieht es so aus:

if (a[i] != b[i]) && (if a.length[i] != b.length[i])
    ;

Dabei ist aber noch wichtig, dass die if-Anweisung in der Form syntaktisch falsch ist. Die Syntax lautet

if ( Ausdruck )

Im Ausdruck selbst kommt kein if vor und der Ausdruck muss geklammert werden, das ist bei Dir nicht der Fall.

Wenn wir das if im Ausdruck entfernen, lautet er (a[i] != b[i]) && (a.length[i] != b.length[i]). Im if-Statement sieht das also so aus:

if ( (a[i] != b[i]) && (a.length[i] != b.length[i]) )

Natürlich sind auch a.length[i] und b.length[i] noch falsch. a und b sind Arrays und die haben eine Länge: a.length != b.length. Damit ist auch klar, dass sich die Länge nicht auf ein einzelnes Element bezieht, so dass die Prüfung hier nicht besonders sinnvoll ist.

 

[mihe7]

So hab da jetzt einen Lösungsansatz gefunden, weiß aber nicht ob das so klappt.

Fast, wenn Du den Code richtig formatierst, ein paar Fehler rausmachst und die überflüssige Schleife in 17 - 20:

    public static boolean compareArrays(int [] a, int [] b) {
        
        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }
        
        for (int i=0; i < a.length; i++) {            
            if (a[i] != b[i]) {           // gleiche Werte UND gleiche Reihenfolge!
                return false;
            }
        }

        // kommt man während der Ausführung bis zu diesem Punkt,
        // haben alle Elemente den gleichen Wert und zwar in der gleichen Reihenfolge.

        return true;
    }
    
    public static void main (String [] args) {
        int[] a = {1,2,3,4,5};
        int[] b = {1,2,3,4,6};
        System.out.println(compareArrays(a, a));
        System.out.println(compareArrays(a, b));
    }

 

[überlebender]

Den Punkt bzgl. des Semikolons hat @KonradN ja schon angesprochen, wenn wir das mal etwas anders formatieren, sieht es so aus:

if (a[i] != b[i]) && (if a.length[i] != b.length[i])
    ;

Dabei ist aber noch wichtig, dass die if-Anweisung in der Form syntaktisch falsch ist. Die Syntax lautet

if ( Ausdruck )

Im Ausdruck selbst kommt kein if vor und der Ausdruck muss geklammert werden, das ist bei Dir nicht der Fall.

Wenn wir das if im Ausdruck entfernen, lautet er (a[i] != b[i]) && (a.length[i] != b.length[i]). Im if-Statement sieht das also so aus:

if ( (a[i] != b[i]) && (a.length[i] != b.length[i]) )

Natürlich sind auch a.length[i] und b.length[i] noch falsch. a und b sind Arrays und die haben eine Länge: a.length != b.length. Damit ist auch klar, dass sich die Länge nicht auf ein einzelnes Element bezieht, so dass die Prüfung hier nicht besonders sinnvoll ist.

 

[mihe7]

Danke für die Antwort. Ich habe tatsächlich die Fehler schon ausgebessert und einen neuen Code geschrieben und oben gepostet.

Ja, habe ich gesehen - und oben auch schon beantwortet

 

[überlebender]

for (int i=0; i < a.length; i++) {
if (a != b) { // gleiche Werte UND gleiche Reihenfolge!
return false;
}
}

// kommt man während der Ausführung bis zu diesem Punkt,
// haben alle Elemente den gleichen Wert und zwar in der gleichen Reihenfolge.

[/code]

Achso, hab nicht gesehen, dass hier beide Kriterien erfüllt werden, danke

 

[überlebender]

Ja, habe ich gesehen - und oben auch schon beantwortet

Jup, danke👍

 

[überlebender]

Fast, wenn Du den Code richtig formatierst, ein paar Fehler rausmachst und die überflüssige Schleife in 17 - 20:

    public static boolean compareArrays(int [] a, int [] b) {
     
        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }
     
        for (int i=0; i < a.length; i++) {         
          if a[i] != b[i] {           // gleiche Werte UND gleiche Reihenfolge!
                return false;
            }
        }

        // kommt man während der Ausführung bis zu diesem Punkt,
        // haben alle Elemente den gleichen Wert und zwar in der gleichen Reihenfolge.

        return true;
    }
 
    public static void main (String [] args) {
        int[] a = {1,2,3,4,5};
        int[] b = {1,2,3,4,6};
        System.out.println(compareArrays(a, a));
        System.out.println(compareArrays(a, b));
    }

Was ist wenn die Reihenfolge egal wäre, aber die Werte trotzdem gleich oft vorkommen und gleich sein sollen?

Könnte ich die for-Schleife weglassen und nur die Bedingung

  if a[i] != b[i]

in die erste if-Anweisung einfügen, also:

 if (a.length != b.length && a[i] != b[i]) {    // gleiche Anzahl an Werten und gleiche Werte

            return false;               

        }

 

[mihe7]

in die erste if-Anweisung einfügen, also:

Da Du an der Stelle den Index i nicht zur Verfügung hast, funktioniert das nicht.

Was ist wenn die Reihenfolge egal wäre, aber die Werte trotzdem gleich oft vorkommen und gleich sein sollen?

Dann brauchst Du eine andere Strategie. Kannst Du Dir ja mal überlegen (Zettel!)

 

[überlebender]

Da Du an der Stelle den Index i nicht zur Verfügung hast, funktioniert das nicht.


Dann brauchst Du eine andere Strategie. Kannst Du Dir ja mal überlegen (Zettel!)

Ja das ist einleuchtend.

Nach so einigen Überlegungen bin ich auf die Idee gekommen, dass wenn die Werte identisch sind, dann ist doch automatisch auch die Anzahl der Werte identisch.

Es scheint irgendwie zu einfach um wahr zu sein, geht auch nicht.
Wenn array a kleiner ist als b, dann kommt trotzdem true raus

 

[Marinek]

dass wenn die Werte identisch sind, dann ist doch automatisch auch die Anzahl der Werte identisch.

Wenn du zwei Arrays hast: a= {1,2,3} und b={1,2,3,4}, dann sind die Werte identisch, aber die Arrays haben unterschiedliche Länge.

Du iterierst über Länge von a, dann wirst du keinen "Fehler" feststellen.

 

[KonradN]

Wenn array a kleiner ist als b, dann kommt trotzdem true raus

Wenn Du in #7 schaust, dann siehst Du doch den Check, der dafür mit im Code ist:

        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }

Diesen Check brauchst Du natürlich und den darfst Du nicht weglassen.

 

[überlebender]

Wenn du zwei Arrays hast: a= {1,2,3} und b={1,2,3,4}, dann sind die Werte identisch, aber die Arrays haben unterschiedliche Länge.

Du iterierst über Länge von a, dann wirst du keinen "Fehler" feststellen.

Ja, so ist es.
Wenn a größer als b ist, kommt eine Fehlermeldung, weil b nicht genug Zeichen hat um es mit a zu vergleichen

 

[mihe7]

Es scheint irgendwie zu einfach um wahr zu sein, geht auch nicht.

Hier kommt wieder der Zettel ins Spiel: schreib Dir zwei beliebige "Arrays" auf und versuch das Problem auf dem Zettel zu lösen. Als Hinweis kann ich Dir noch mitgeben, dass sich dieses Problem nicht ganz so einfach lösen lässt, wie das vorherige.

 

[überlebender]

Wenn Du in #7 schaust, dann siehst Du doch den Check, der dafür mit im Code ist:

        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }

Diesen Check brauchst Du natürlich und den darfst Du nicht weglassen.

if (a[i] != b[i]) {

Dieser Check prüft, ob beide arrays gleiche Reihenfolge und gleiche Werte haben.

Wenn die Reihenfolge egal sein soll, dann muss bei
a = {1,2,3,4} und
b = {2,1,4,3}
auch true rauskommen, weil gleiche Länge und gleiche Werte

 

[überlebender]

Hier kommt wieder der Zettel ins Spiel: schreib Dir zwei beliebige "Arrays" auf und versuch das Problem auf dem Zettel zu lösen. Als Hinweis kann ich Dir noch mitgeben, dass sich dieses Problem nicht ganz so einfach lösen lässt, wie das vorherige.

Ja das habe ich schon verstanden. Sonst wäre es keine einzelne Aufgabe...

 

[KonradN]

Bei so Aufgaben immer überlegen: Wie machst Du es? Wenn du zwei Zahlenreihen bekommst und feststellen sollst, ob die Zahlen prinzipiell gleich sind und nur die Reihenfolge unterschiedlich ist?

Das ist generell der Ansatz, der immer gegangen wird. Daher: Wie gehst Du vor?
Du wirst doch bestimmt irgendwelche Ideen haben, wie Du sowas heraus finden kannst...

 

[überlebender]

Bei so Aufgaben immer überlegen: Wie machst Du es? Wenn du zwei Zahlenreihen bekommst und feststellen sollst, ob die Zahlen prinzipiell gleich sind und nur die Reihenfolge unterschiedlich ist?

Das ist generell der Ansatz, der immer gegangen wird. Daher: Wie gehst Du vor?
Du wirst doch bestimmt irgendwelche Ideen haben, wie Du sowas heraus finden kannst...

Ja ich habe tatsächlich eine Idee:

z.B.
1. Kartesisches Produkt bilden
2. vergleichen welche paare identisch sind

also int [] a x int [] b
if Wertepaar 1 (a[0] = b[0])
return true

Vom Grundgedanken her muss man ja alle Indexe von array a mit allen indexen von array b vergleichen.
Das Programm muss auf dem Weg einen identischen Wert finden.
d.h. wir vergleichen zuerst a[0] mit b [0-b.length], danach a[1] mit b[0- b.length] usw.

 

[KonradN]

Ja ich habe tatsächlich eine Idee:

z.B.
1. Kartesisches Produkt bilden
2. vergleichen welche paare identisch sind

also int [] a x int [] b
if Wertepaar 1 (a[0] = b[0])
return true

Vom Grundgedanken her muss man ja alle Indexe von array a mit allen indexen von array b vergleichen.
Das Programm muss auf dem Weg einen identischen Wert finden.
d.h. wir vergleichen zuerst a[0] mit b [0-b.length], danach a[1] mit b[0- b.length] usw.

Da sehe ich aber erst einmal nicht, wie Du da zu einem Ergebnis kommst, das Du haben willst.

Daher noch einmal: Was machst Du, wenn ich Dich bitte, die Listen 1, 1, 2, 2 und 2, 2, 1, 1 bezüglich der Anzahl der Elemente zu vergleichen?

Bildest Du da wirklich das Kartesische Produkt? Also
1, 2
1, 2
1, 1
1, 1
1, 2
1, 2
1, 1
1, 1
2, 2
2, 2
2, 1
2, 1
2, 2
2, 2
2, 1
2, 1

Und da kommt dann raus: 8 gleiche Paare... Wie hilft Dir das?

1, 1, 1, 2 und 2, 1, 1, 1 könnte man ja auch mal nehmen ... ich schreibe es jetzt nicht auf, aber da gibt es dann 10 gleiche Paare...

 

[überlebender]

Hier kommt wieder der Zettel ins Spiel: schreib Dir zwei beliebige "Arrays" auf und versuch das Problem auf dem Zettel zu lösen. Als Hinweis kann ich Dir noch mitgeben, dass sich dieses Problem nicht ganz so einfach lösen lässt, wie das vorherige.

Eigentlich muss es recht simpel sein, denn im 1.Semester habe ich noch nicht genug Wissen um so richtig komplexe sachen zu basteln.

Außer arrays, schleifen, if, else-if und Methoden und die 8 primitiven Datentypen haben wir noch nicht viel gemacht.

 

[KonradN]

Also noch einmal ganz deutlich: Vergiss die Software Entwicklung. Es gibt ein fachliches Problem und das sollst Du in Gedanken lösen. Da geht es um ein Verfahren!

Evtl. um es etwas bildlicher zu machen:

Du bekommst zwei Stapel Geldscheine. Und nun ist die Frage: Sind in beiden Stapeln genau die gleichen Geldscheine?

Kriegst Du das irgendwie hin? Wenn ja: Wie gehst Du dazu vor?

 

[überlebender]

Da sehe ich aber erst einmal nicht, wie Du da zu einem Ergebnis kommst, das Du haben willst.

Daher noch einmal: Was machst Du, wenn ich Dich bitte, die Listen 1, 1, 2, 2 und 2, 2, 1, 1 bezüglich der Anzahl der Elemente zu vergleichen?

Bildest Du da wirklich das Kartesische Produkt? Also
1, 2
1, 2
1, 1
1, 1
1, 2
1, 2
1, 1
1, 1
2, 2
2, 2
2, 1
2, 1
2, 2
2, 2
2, 1
2, 1

Und da kommt dann raus: 8 gleiche Paare... Wie hilft Dir das?

1, 1, 1, 2 und 2, 1, 1, 1 könnte man ja auch mal nehmen ... ich schreibe es jetzt nicht auf, aber da gibt es dann 10 gleiche Paare...

Mein Gedanke wäre jetzt, wenn alle Zahlen in beiden Arrays n-mal vorkommen -> true
Wenn eine Zahl in einem array k-mal vorkommt und im anderen x-mal -> false

Also in etwa: if a = n && b= n -> true
Ich weiß nicht wie ich diesen Grundgedanken in Code ausdrücke.


Brauche ich dann 4 for-Schleifen?
jeweils für beide n's
und dann noch 2 für beide arrays?

 

[mihe7]

Ich weiß nicht wie ich diesen Grundgedanken in Code ausdrücke.

Erstmal gar nicht. Löse das Geldscheinproblem.

 

[überlebender]

Also noch einmal ganz deutlich: Vergiss die Software Entwicklung. Es gibt ein fachliches Problem und das sollst Du in Gedanken lösen. Da geht es um ein Verfahren!

Evtl. um es etwas bildlicher zu machen:

Du bekommst zwei Stapel Geldscheine. Und nun ist die Frage: Sind in beiden Stapeln genau die gleichen Geldscheine?

Kriegst Du das irgendwie hin? Wenn ja: Wie gehst Du dazu vor?

Ich zähle erst die Anzahl der 5€-Scheine, dann die Anzahl der 10€-Scheine usw.
Wenn die Anzahl aller verschiedenen Scheine gleich ist, dann sind in beiden Stapeln die gleichen Scheine.

 

[überlebender]

Erstmal gar nicht. Löse das Geldscheinproblem

Wir nehmen an:

1.Stapel......................2. Stapel
-1x 10€...................... -4x20€
-2x 50€.......................-2x50€
-4x20€........................-1x10€

Ich nehme den ersten Stapel, zähle alles durch und schreibe die Anzahl der 10, 20 und 50€ Scheine raus.
Danach nehme ich den zweiten Stapel, zähle alles durch und schreibe mir die Anzahl der 10, 20, 50€ Scheine raus.

Danach vergleiche ich beide Notizen. Selbe Anzahl, gleicher Schein? -> Ja
Falls im 1. Stapel zusätzlich noch ein 100€ Schein ist. Selbe Anzahl, gleicher Schein? -> Nein

 

[mihe7]

Ich zähle erst die Anzahl der 5€-Scheine, dann die Anzahl der 10€-Scheine usw.

Ja, das wäre eine Möglichkeit. Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst (was hier nicht der Fall ist). Ansonsten müsstest Du 4,2 Mrd. verschiedene Werte (32 Bit) durchzählen - da ist der Ansatz "etwas" aufwendig. Bekommst Du es ein klein wenig anders hin?

 

[KonradN]

Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst

Das ist nicht zwingend notwendig. Wenn ich einen Stapel Geldscheine bekomme, dann zähle ich keine 5er, wenn es keine 5er gibt.

Da könnte man also überlegen, was für Zahlen man zählt.

Aber evtl. überlegt man einfach, wie man die Geldscheine zählt. Gehst du den Stapel mit allen Geldscheinen durch, um z.B. die 10er zu zählen?

 

[überlebender]

Ja, das wäre eine Möglichkeit. Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst (was hier nicht der Fall ist). Ansonsten müsstest Du 4,2 Mrd. verschiedene Werte (32 Bit) durchzählen - da ist der Ansatz "etwas" aufwendig. Bekommst Du es ein klein wenig anders hin?

Vielleicht bilde ich die Summe?
Ich mein irgendwie muss das Programm doch durch die Werte gehen. Und wenn es 5 Milliarden sind, dann schafft das Programm das bestimmt auch nach längerer Zeit. Im Code implementiert man halt die Anweisung, es soll so lange durchgehen, wie das Array lang ist.

 

[überlebender]

Du kannst eine Abkürzung nehmen. Nimm einfach jeden Schein in geordneter Reihenfolge heraus, und sobald du einen Unterschied feststellst, kann das Gesamtergebnis net mehr true werden...

Also erst array. sort und danach vergleichen

 

[überlebender]

Das ist nicht zwingend notwendig. Wenn ich einen Stapel Geldscheine bekomme, dann zähle ich keine 5er, wenn es keine 5er gibt.

Da könnte man also überlegen, was für Zahlen man zählt.

Aber evtl. überlegt man einfach, wie man die Geldscheine zählt. Gehst du den Stapel mit allen Geldscheinen durch, um z.B. die 10er zu zählen?

Ich sortiere erst die Stapel und vergleiche danach.

 

[KonradN]

Also erst array. sort und danach vergleichen

Ja, das ist eine Lösung auf die wir hinaus wollten. Die Geldscheine sortiert man in der Regel (bildet Stapel gleicher Scheine) und zählt diese dann.

 

[überlebender]

Ja, das wäre eine Möglichkeit. Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst (was hier nicht der Fall ist). Ansonsten müsstest Du 4,2 Mrd. verschiedene Werte (32 Bit) durchzählen - da ist der Ansatz "etwas" aufwendig. Bekommst Du es ein klein wenig anders hin?

Ich glaub ich habs jetzt endlich. Ich glaub es kaum.
Also wenn man das Array zuerst sortiert, dann flieg ich vom Hocker.

 

[KonradN]

Alternative könnte sein:
Ich gehe das erste Array Zahl für Zahl durch und zähle dann die Anzahl der Vorkommen.

Da zähle ich eine Zahl aber mehrfach - bei jedem Vorkommen.

Bei Deiner Beschreibung hattest Du etwas geschrieben, das ich so verstanden hatte, dass Du Ergebnisse aufschreibst. Das wäre dann also einfach, dass Du gezählte Zahlen merkst und vor jedem Zählen prüfst, ob Du diese noch zählen musst.

Beide Vorgehen sind gleichwertig. Ich will Dich da jetzt nicht überrennen mit Dingen die im Studium noch kommen werden, aber man kann Laufzeit und Speicherverbrauch betrachten ….

 

[überlebender]

Ja, das ist eine Lösung auf die wir hinaus wollten. Die Geldscheine sortiert man in der Regel (bildet Stapel gleicher Scheine) und zählt diese dann.

Ich hab es schon geahnt, nachdem janeja mir den Hinweis gegeben hat. Schade nur, dass mein Prof mir nicht erzält, dass man arrays auch sortieren kann.

Die Vorlesungsfolie von letzter Woche hat 600 Seiten, aber die Infos die man zum lösen der Aufgaben braucht sind nicht drin.
Die 600 Seiten sind kein Witz

 

[überlebender]

Alternative könnte sein:
Ich gehe das erste Array Zahl für Zahl durch und zähle dann die Anzahl der Vorkommen.

Da zähle ich eine Zahl aber mehrfach - bei jedem Vorkommen.

Bei Deiner Beschreibung hattest Du etwas geschrieben, das ich so verstanden hatte, dass Du Ergebnisse aufschreibst. Das wäre dann also einfach, dass Du gezählte Zahlen merkst und vor jedem Zählen prüfst, ob Du diese noch zählen musst.

Beide Vorgehen sind gleichwertig. Ich will Dich da jetzt nicht überrennen mit Dingen die im Studium noch kommen werden, aber man kann Laufzeit und Speicherverbrauch betrachten ….

Ja das mit dem Zählen der Anzahl jeden Scheins war anfangs meine Idee, dauert halt recht lange bei längeren Zahlen oder wie im Bsp. Scheinen.
Wenn man die Arrays erst sortiert dann kommt man logischerweise früher auf die Ungleichheit, wenn es denn eine gibt, oder verstehe ich das falsch?

 

[KonradN]

Ach je … aber statt zu sortieren könntest du zur Not einfach jede Zahl zählen.

Also für jede Zahl aus Array1 ermittelst du die Anzahl in Array1 und Array2 und vergleichst diese.

Das ginge auch ohne jede weitere Verbesserung aber für jede Zahl gehst du alle Elemente beider Arrays durch. Also wenn die Arrays in Ihrer Länge sich verdoppeln, dann vervierfacht sich der Aufwand! Das ist also nicht so gut wenn man ggf mit großen Arrays umgehen muss.

 

[KonradN]

Ja das mit dem Zählen der Anzahl jeden Scheins war anfangs meine Idee, dauert halt recht lange bei längeren Zahlen oder wie im Bsp. Scheinen.
Wenn man die Arrays erst sortiert dann kommt man logischerweise früher auf die Ungleichheit, wenn es denn eine gibt, oder verstehe ich das falsch?

Jetzt greife ich mal etwas vor. Bezüglich Laufzeit gibt es Laufzeitklassen. Da wird oft von der O Notation gesprochen (@mihe7 verbessere mich, falls ich Fachbegriffe falsch habe).

Die üblichen Sortieralgorithmen haben eine Laufzeit von O(n * log(n)) was besser ist als diese Quadratische Laufzeit der Vergleiche. Da bist du bei O(n*n) was schlechter ist.
Diese Sortierung musst du auf jeden Fall machen - damit hast du diesen Batzen immer. Der Check geht das Array einmal durch und hat daher O(n) und nur da kannst du früher abbrechen.

Das, was also die Hauptkosten verursacht, musst du voll durchziehen.

 

[überlebender]

Ach je … aber statt zu sortieren könntest du zur Not einfach jede Zahl zählen.

Also für jede Zahl aus Array1 ermittelst du die Anzahl in Array1 und Array2 und vergleichst diese.

Das ginge auch ohne jede weitere Verbesserung aber für jede Zahl gehst du alle Elemente beider Arrays durch. Also wenn die Arrays in Ihrer Länge sich verdoppeln, dann vervierfacht sich der Aufwand! Das ist also nicht so gut wenn man ggf mit großen Arrays umgehen muss.

Ja das wird mir jetzt klar.

Also zuerst sortiere ich die Arrays.
Danach sage ich dem Compiler:
Wenn a[] != b[] -> false (grob)

Der Compiler geht jetzt auch jede Zahl durch, aber nur bis ein Unterschied auftaucht.

Also
11
1 2
---- Hier stoppt das Programm und Ausgabe -> false
11
12
11
12
21
22
21
22
2

 

[KonradN]

Glaube, das heißt Counting sort.

CountingSort geht nur, wenn die Anzahl der möglichen Elemente nicht zu groß ist. Bei 32bit Integer Werten dürfte das problematisch werden.

 

[überlebender]

Jetzt greife ich mal etwas vor. Bezüglich Laufzeit gibt es Laufzeitklassen. Da wird oft von der O Notation gesprochen (@mihe7 verbessere mich, falls ich Fachbegriffe falsch habe).

Die üblichen Sortieralgorithmen haben eine Laufzeit von O(n * log(n)) was besser ist als diese Quadratische Laufzeit der Vergleiche. Da bist du bei O(n*n) was schlechter ist.
Diese Sortierung musst du auf jeden Fall machen - damit hast du diesen Batzen immer. Der Check geht das Array einmal durch und hat daher O(n) und nur da kannst du früher abbrechen.

Das, was also die Hauptkosten verursacht, musst du voll durchziehen.

Ja gut ich versuche mir erstmal darüber Gedanken zu machen, wie ich das alles als Code schreibe.
Das Prinzip habe ich ja jetzt endlich verstanden. Danke allen für die Hilfe!

 

[KonradN]

@überlebender bezüglich des CountingSort: das ist, was du bei den Geldscheinen schon hattest: du machst einfach n Stapel. Oder eine Strichliste. Bei Geldscheinen einfach - du hast nur sehr wenig. Da gehst du dann genau einmal die Scheine durch und gut ist es.

Aber wenn du 2 hoch 32 Möglichkeiten hast, dann wird die Strichliste sehr lang und das ist problematisch.

Wir brauchen nur das Zählen aber CountingSort würde dann am Ende nach dem Zählen die Strichliste durchgehen und die jeweilige Anzahl des Elements bereit stellen.

Das einfach, um diesen Begriff kurz zu erläutern.

 

[MarvinsDepression]

Also zuerst sortiere ich die Arrays.
Danach sage ich dem Compiler:
Wenn a[] != b[] -> false (grob)

aber erst Kopien der Arrays erstellen und mit denen weiterarbeiten. Sonst veränderts du irreversibel die Originale, ein ggf. unerwünschter Seiteneffekt.

 

[überlebender]

@überlebender bezüglich des CountingSort: das ist, was du bei den Geldscheinen schon hattest: du machst einfach n Stapel. Oder eine Strichliste. Bei Geldscheinen einfach - du hast nur sehr wenig. Da gehst du dann genau einmal die Scheine durch und gut ist es.

Aber wenn du 2 hoch 32 Möglichkeiten hast, dann wird die Strichliste sehr lang und das ist problematisch.

Wir brauchen nur das Zählen aber CountingSort würde dann am Ende nach dem Zählen die Strichliste durchgehen und die jeweilige Anzahl des Elements bereit stellen.

Das einfach, um diesen Begriff kurz zu erläutern.

Danke für die Erklärung. 👍

 

[überlebender]

aber erst Kopien der Arrays erstellen und mit denen weiterarbeiten. Sonst veränderts du irreversibel die Originale, ein ggf. unerwünschter Seiteneffekt.

Beim kopieren wird doch das originale Arrays auch verändert, oder irre ich mich da?
Ist es dann nicht clonen, wenn man ein zweites, vom ersten unabhängiges array, haben möchte?

 

[mihe7]

Wenn ich einen Stapel Geldscheine bekomme, dann zähle ich keine 5er, wenn es keine 5er gibt.

Ja, allerdings war sein Ansatz genau das: 5er, 10er etc. zu zählen, auch wenn 0 als Ergebnis herauskommt (so hatte ich es zumindest verstanden). Das kann ich machen, wenn ich weiß, welche Werte es gibt (und die einigermaßen begrenzt sind), also z. B. mit echten Geld"werten": 500 €, 200 €, 100 €, 50 €, 20 €, 10 €, 5 €. Das sind 7 verschiedene Werte. Kenne ich die Werte im Vorfeld nicht, und will jeden Wert zählen, dann lande ich bei 4,2 Mrd. -> nicht sonderlich effizient

 

[mihe7]

Man kann natürlich auch einfach streichen.

1. Sind die Arrays A und B gleich lang? Falls nicht, gib false zurück.
2. Für jedes Element aus A: suche ein Element mit dem gleichen Wert in B. Falls gefunden: streiche, das Element, ansonsten gib false zurück.
3. Gib true zurück.

Beispiel:

A={1,2,3,4,5,1}, B={5,1,3,2,1,4}

Arrays sind gleich lang, also weiter.

1. Element aus A = 1 -> streiche das erste Vorkommen von 1 aus B -> B = {5,-,3,2,1,4}
2. Element aus A = 2 -> streiche das erste Vorkommen von 2 aus B -> B = {5,-,3,-,1,4}
3. Element aus A = 3 -> streiche das erste Vorkommen von 3 aus B -> B = {5,-,-,-,1,4}
4. Element aus A = 4 -> streiche das erste Vorkommen von 4 aus B -> B = {5,-,-,-,1,-}
5. Element aus A = 5 -> streiche das erste Vorkommen von 5 aus B -> B = {-,-,-,-,1,-}
6. Element aus A = 1 -> streiche das erste Vorkommen von 1 aus B -> B = {-,-,-,-,-,-}

Da jedes Element aus A in B gestrichen werden konnte -> true

Wäre z. B. B = {5,1,3,2,6,4} gewesen, dann hätte im 6. Schritt die zweite 1 aus A nicht in B gestrichen werden können -> false.