Schnittmenge berechnen

Hallo zusammen,

also, ich hab irgendwie ne Denkblockade, hab ne Aufgabe hier, die eigentlich recht leicht zu lösen ist, aber iterativ. Verlangt ist eine rekursive Lösung, und vielleicht hat ja jemand ne Idee und n Tipp.

Ich habe zwei Mengen M1 und M2 mit jeweils n Zahlen. Gesucht wird die Anzahl der Zahlen, die in Menge M1 und M2 ist. Iterativ ja kein Problem, nur rekursiv..

Ich hab mir schonmal ne Funktion überlegt, die für eine Zahl prüft, ob diese in nem Array ist. Aber ich weiß nicht, ob mich das weiterbringt, oder ob es nicht einfach noch ne viel geschicktere Möglichkeit gibt, das zu machen (ich hab so den Verdacht, das es so ähnlich gehen muss, wie Permutationen berechnen, weil da ja auch n! Möglichkeiten existieren.. Nur komm ich da auch auf keinen grünen Zweig)

rekursion, um eins zu finden:

int suche_eins(int zahl, int arr[], int anz)
{
   if (anz==0)
     return 0;
   else
     if (arr[anz-1]==zahl)
       return 1;
     else
       return suche_eins(zahl,arr,anz-1);
}

Wär echt klasse, wenn ihr n Tipp habt (muss sich nich auf eine meiner Ideen beziehen, wenns besser geht )

Viele Grüße!

prolog

Hmm auf die schnelle.

Ich weiss allerdings nicht obs wirklich auch das tut was es soll. Unter allen umständen mein ich.

int subset(int *arr1,int anz1,int *arr2,int anz2,int count){
   return (!anz1 || !anz2) ?  count :  subset(++arr1,--anz1,++arr2,--anz2,(*arr1==*arr2) ? ++count : count); 
}

printf("%d\n",subset(set1,setsize,set2,setsize2,0));

[edit] versehentlich c++ gepostet [/edit]

Hi,

hmmm, hab das ma ausprobiert, der vergleicht in deinem code immer nur die array einträge mit gleichem index, also bei 1 2 3 in einem und 3 1 2 testet der 1 3, 2 1, 3 2 , dann kommt 0 raus, 3 wäre richtig. Und genau kapieren tu ich auch nicht, wie die Idee dahinter ist :).

Danke aber schonmal..

prolog

Ah stimmt. Du hast vollkommen recht. Ich sagte ja ohne gewähr gg.

Das lässt sich aber relativ leicht abwandeln.
Man muss eben nur bei einem Array den index verändern. Und zwar beim größeren.
Dann läuft die rekursion bis das kleinere erschöpft ist. Das bedeutet eine Abfrage mehr, aber das Prinzip ist das Gleiche.