Rekursionsprobleme

[sankafahrer]

Hallo zusammen,

ich habe ein typisches Anfängerproblem.
Meine Aufgabe lautet eine Menge Gewinnzahlen (g[]) rekursiv mit einer Menge Tippzahlen (t[]) zu vergleichen und die Übereinstimmungen zu zählen.
Iterativ war das Problem in 5-7min bewältigt. Rekursiv sitze ich jetzt schon einen ganzen Nachmittag dran. Hier mein Code :

#include <iostream>
#include <cstdlib>

int lottovergleich(int n, int m, int t[], int g[]);

int main(int argc, char *argv[])
{
  int i, t[100], g[100], n, treffer;
  cout << "Geben Sie die Anzahl der Gewinn-/Tippzahlen ein : ";
  cin >> n;
  cout << "Geben Sie die Gewinnzahlen ein : " << endl;
  for(i=0; i<n; ++i)
  {
    cin >> g[i];
  }
  cout << "Geben Sie die Tippzahlen ein : " << endl;
  for(i=0; i<n; ++i)
  {
    cin >> t[i];
  }
  treffer = lottovergleich(n-1, n-1, t, g);
  cout << endl << "Die Tippzahlen enthalten " << treffer << " Treffer!" << endl; 
  return EXIT_SUCCESS;
}

int lottovergleich(int n, int m, int t[], int g[])
{
  int z=0;

  if( n==0 )
  {
    if( m==0 )
    {
     //
    }
    else
    {
      z = z + lottovergleich(n, m-1, t, g);
    }
  }
  else
  {
    z = z + lottovergleich(n-1, m, t, g);
  }
  if( t[n] == g[m] )++z;
  return z;
}

/*
int lottovergleich(int n, int m, int t[], int g[])
{
  int j=0, z=0;

  if(n==0)
  {
    for(j=0; j<m; j++)
    { 
      if(t[n]==g[j])
	z++;
    }
  }
  else
  {
    z = lottovergleich(n-1, m, t, g);
  }
  return z;
}
*/

Die auskommentierte lottovergleich-Funktion funktioniert aber eben wieder mit einer iterativen Schleife.
Im Debugger kann ich erkennen, dass die Funktion bei 3 Gewinn-/Tippzahlen nicht 9 sondern nur 5 Vergleiche anstellt (n/m : 1. 0/0, 2. 0/1, 3. 0/2, 4. 1/2, 5. 2/2).
Wo liegt mein Denkfehler?

Vielen Dank schon mal

Andy

[Caipi]

Hallo,

int lottovergleich(int n, int m, int t[], int g[])
{
  int j=0, z=0;

  if(n==0)
  {
    for(j=0; j<m; j++)
    {
      if(t[n]==g[j])
    z++;
    }
  }
  else
  {
    z = lottovergleich(n-1, m, t, g);
  }
  return z;
}

Auch in dieser "iterativen" Version vergleichst du nicht jede Tippzahl mit jeder Gewinnzahl, sondern nur die erste Tippzahl (t[0]) mit allen Gewinnzahlen abgesehen von der letzten.

Der Denkfehler in deiner rekursiven Variante liegt darin, dass du nur die folgenden Array-Indizes miteinander vergleichst:

t[0] mit g[0]
t[0] mit g[1]
t[0] mit g[2]
t[1] mit g[2]
t[2] mit g[2]

Gruß Caipi

[FireFlow]

Ok hab erst vergessen dass es um Lottozahlen geht...

bool vorhanden(int wert, int* array, int num)
{
	for(int i=0; i<num; ++i) {
		if(wert == array[i]) {
			return true;
		}
	}
	return false;
}

int treffer(int* a, int* b, int numa, int numb)
{
	if(numa == 0) {
		return 0;
	}
	else if(vorhanden(*a, b, numb)) {
		return 1 + treffer(a + 1, b, numa - 1, numb);
	}
	else {
		return treffer(a + 1, b, numa - 1, numb);
	}
}

Gruß

[sankafahrer]

Vielen Dank schon mal.

->@caipi
meine iterative Lösung sieht so aus:

int lottovergleich(int n, int m, int t[], int g[])
{
  int z=0, j=0, i=0;

  for(i=0; i<n; ++i)
  {
    for(j=0; j<m; ++j)
    {
       if(t[i] == g[j])
         ++z;
    }
  }
  return z;
}

natürlich dann nicht mit n-1 sondern mit n aufgerufen. Die funktioniert.
Die auskommentierte Funktion aus meinem ersten Beitrag war nur ein Zwischenprodukt. Aber du hast recht, auch die hat den gleichen Denkfehler intus wie die völlig rekursive Funktion! Und genau da komme ich nicht weiter! Wie muss ich die Fkt. gestalten, dass alle Zahlen rekursiv verglichen werden? Auch die Lösung von FireFlow arbeite wieder mit einer iterativen Schleife. Genau das versuche ich zu umgehen. Weis jemand Rat?

Gruss
Andy

[Caipi]

Wie muss ich die Fkt. gestalten, dass alle Zahlen rekursiv verglichen werden?

Du willst also bei den folgenden beiden Arrays

int v1[3] = { 0, 1, 2 };
int v2[3] = { 2, 1, 0 };

das folgendermaßen verglichen wird:

v1[0] mit v2[0]
v1[0] mit v2[1]
v1[0] mit v2[2]
v1[1] mit v2[0]
v1[1] mit v2[...]
v1[2] mit v2[0]
...

??
Wenn ja: Vielleicht hilft dir folgender Ansatz weiter:

template <class T>
size_t cmp(size_t n, size_t m, const T* const p_n, const T* const p_m)
{
    size_t count = 0;
    static size_t cpy_n = n;
    if(p_n[n] == p_m[m])
        ++count;

    if(n > 0)
    {
        count = count + cmp(n - 1, m, p_n, p_m);
    }
    else if(m > 0)
    {
        n = cpy_n;
        count = count + cmp(n, m - 1, p_n, p_m);
    }
    return count;
}

Gruß Caipi

[sankafahrer]

->@caipi
Vielen Dank!
Jetzt hat's 'klick' gemacht.

Gruss
Andy