Trasformare un funzione da iterativa a ricorsiva

di il
21 risposte

Trasformare un funzione da iterativa a ricorsiva

Ciao a tutti, avrei bisogno di un aiuto riguardo a questa funzione. Ho scritto la funzione iterativa e funziona alla perfezione, ora dovrei convertirla in una funzione ricorsiva. Qualcuno riesce ad aiutarmi?

Si tratta una funzione che ha come parametri di ingesso due insiemi e stabilisce se questi due insiemi sono uguali.
void insiemi_uguali(double a1[], double a2[], int num_elem1, int num_elem2, int count, int i, int j)
{
	int trovato;
	trovato = 0;

	if( num_elem1 == num_elem2 )
	{
	for( i=0; i<num_elem2;i++)
	{
	    if( a2[i] == a1[j])
	    {
		count = 1;
		i++;
		j = 0;
		
	    }
	    else
	    {
		count = 0;
		
	    }
	}
		if(count == 1)
		 {
		  printf("Gli insiemi sono uguali\n"); 
		 }
		 else
		 {
		  printf("Gli insiemi sono diversi\n");
		 }
	}
	else
	{
		printf("Gli insiemi sono diversi\n");
	
	}

}
Grazie.

21 Risposte

  • Re: Trasformare un funzione da iterativa a ricorsiva

    Alcune considerazioni:
    - innanzitutto si dice "iterativo" e non "iterattivo"!
    - a cosa dovrebbero servire i parametri della funzione count, i e j?
    - ti consiglio di modificare la funzione in modo che ritorni un intero (1 se i 2 array sono uguali e 0 altrimenti);
    - la funzione mi sembra sbagliata dal punto di vista logico... di preciso cosa intendi con "insiemi uguali"?

    Inizia ad aggiustare ed ottimizzare la versione iterativa e poi pensiamo alla conversione.
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Nippolo ha scritto:


    Alcune considerazioni:
    - innanzitutto si dice "iterativo" e non "iterattivo"!
    - a cosa dovrebbero servire i parametri della funzione count, i e j?
    - ti consiglio di modificare la funzione in modo che ritorni un intero (1 se i 2 array sono uguali e 0 altrimenti);
    - la funzione mi sembra sbagliata dal punto di vista logico... di preciso cosa intendi con "insiemi uguali"?

    Inizia ad aggiustare ed ottimizzare la versione iterativa e poi pensiamo alla conversione.
    count è esattamente il 3 punto che hai scritto, l'ho chiamato così per comodità per vedere se funzionava senza a stare a modificare tutto il codice che avevo scritto e modificato in precedenza.

    i e j sono i contatori dei puntatori a1 e a2

    Con insiemi uguali intendo con gli stessi elementi.
  • Re: Trasformare un funzione da iterativa a ricorsiva

    - quanto vale inizialmente j?
    - a cosa serve quel j=0?
    - in generale perché utilizzare due contatori (i e j) e non uno solo?

    P.S.
    Tu dici che funziona alla perfezione, ma io non ne sarei tanto convinto!
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Nippolo ha scritto:


    - quanto vale inizialmente j?
    - a cosa serve quel j=0?
    - in generale perché utilizzare due contatori (i e j) e non uno solo?

    P.S.
    Tu dici che funziona alla perfezione, ma io non ne sarei tanto convinto!
    l'insieme a2 deve essere uguale all'insieme a1[j], per controllare tutti gli elementi all'interno del puntatore faccio tornare a ogni ciclo j=0 in modo tale che il primo insieme ricontrolli tutti gli elementi senza tralasciarne alcuno
    Inserisci il numero di elementi del primo insieme: 4
    Inserisci elemento: 1
    Inserisci elemento: 2
    Inserisci elemento: 3
    Inserisci elemento: 6
    Inserisci il numero di elementi dell'insieme che vuoi inserire: 6
    Inserisci elemento: 1
    Inserisci elemento: 2
    Inserisci elemento: 3
    Inserisci elemento: 6
    Inserisci elemento: 54
    Inserisci elemento: 5
    Gli insiemi sono diversi
    
    Hai ragione ricontrollando se l'insieme ha più di due elementi non funziona
    Inserisci il numero di elementi del primo insieme: 3
    Inserisci elemento: 1
    Inserisci elemento: 2
    Inserisci elemento: 3
    Inserisci il numero di elementi dell'insieme che vuoi inserire: 3
    Inserisci elemento: 1
    Inserisci elemento: 2
    Inserisci elemento: 3
    Gli insiemi sono diversi
    
    Inserisci il numero di elementi del primo insieme: 2
    Inserisci elemento: 1
    Inserisci elemento: 2
    Inserisci il numero di elementi dell'insieme che vuoi inserire: 2
    Inserisci elemento: 1
    Inserisci elemento: 2
    Gli insiemi sono uguali
    
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Devi leggere con maggior cura i suggerimenti ed applicarli!
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Ok ora ho capito cosa intendi con "insiemi uguali", in pratica anche (2 7 1 5) e (7 1 2 5) sono da considerarsi uguali, giusto?
    In quest'ottica ovviamente il fatto di scorrere il secondo array da capo per ogni singolo elemento del primo array ha senso, ma ti faccio una domanda:
    con questo metodo cosa succederebbe se gli insiemi fossero (3 3 7) e (7 3 7)?
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Ti do un indizio. Completa tu i puntini e poi ragiona da solo sull'altro esercizio sull'intersezione
    bool insiemi_uguali(double a1[], double a2[], int num_elem1, int num_elem2)
    {
    	int i;
    	double temp;
    
    	if(num_elem1 != num_elem2)
    	    return false;
    	
    	if(num_elem1 == 0)
    	    return true;
    	    
    	for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
    	       return insiemi_uguali(...);
    	    }
    	    
    	return false;
    }
    
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Nippolo ha scritto:


    Ok ora ho capito cosa intendi con "insiemi uguali", in pratica anche (2 7 1 5) e (7 1 2 5) sono da considerarsi uguali, giusto?
    In quest'ottica ovviamente il fatto di scorrere il secondo array da capo per ogni singolo elemento del primo array ha senso, ma ti faccio una domanda:
    con questo metodo cosa succederebbe se gli insiemi fossero (3 3 7) e (7 3 7)?
    Ho fatto in modo che durante 'inserimento non si possano inserire due numeri uguali.
    L'unico problema che riscontro in questo è:
    - se faccio visualizzare, alla fine dell'inserimento, i numeri che sono all'interno del vettore, non mi prende i nuovo valore inserito ma quello sbagliato, cioè doppio.

    	 
    	conta=0;
            for (j=0; j < insieme2.num_elementi; j++)
            {
    	    if (insieme2.a[j] == insieme2.a[i]) 
    	    {
                    conta++;
                }
                if (conta > 1) 
    	    {
                    printf("Errore numero già presente!\nInserisci un nuovo valore: ");
                    scanf("%g", &(insieme2.a[i]));
                    conta=0;
                }
    	}
    
    Inserisci il numero di elementi del primo insieme: 3
    Inserisci elemento: 1
    Inserisci elemento: 2
    Inserisci elemento: 3
    
    Gli elementi dell'insieme 1 sono: 1 2 3 
    
    Inserisci il numero di elementi dell'insieme che vuoi inserire: 3
    Inserisci elemento: 1
    Inserisci elemento: 1
    Errore numero già presente!
    Inserisci un nuovo valore: 2
    Inserisci elemento: 3
    
    Gli elementi dell'insieme 2 sono: 1 1 3
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Weierstrass ha scritto:


    Ti do un indizio. Completa tu i puntini e poi ragiona da solo sull'altro esercizio sull'intersezione
    bool insiemi_uguali(double a1[], double a2[], int num_elem1, int num_elem2)
    {
    	int i;
    	double temp;
    
    	if(num_elem1 != num_elem2)
    	    return false;
    	
    	if(num_elem1 == 0)
    	    return true;
    	    
    	for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
    	       return insiemi_uguali(...);
    	    }
    	    
    	return false;
    }
    

    Scusami, ma non so rispondere.
    Soprattutto non capisco tutti questi passaggi
    for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Ho fatto in modo che durante 'inserimento non si possano inserire due numeri uguali.
    Perché precludersi questa possibilità?!

    Il tutto può essere risolto semplicemente ordinando i due array.

    Volendo si può anche evitare l'ordinamento, tenendo presente quali elementi del secondo array sono già stati "considerati".
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Smarties ha scritto:



    Scusami, ma non so rispondere.
    Soprattutto non capisco tutti questi passaggi
    for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
    Vabbé ti posto la soluzione allora:
    
    bool insiemi_uguali(double a1[], double a2[], int num_elem1, int num_elem2)
    {
    	int i;
    	double temp;
    
    	if(num_elem1 != num_elem2)
    	    return false;
    	
    	if(num_elem1 == 0)
    	    return true;
    	    
    	for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
    	       return insiemi_uguali(a1, a2, num_elem1 - 1, num_elem2 - 1);
    	    }
    	    
    	return false;
    }
    
    int main(void)
    {
    	double a[5] = {3, -7, 3, -0.5, 1};
    	double b[5] = {1, 3, -0.5, 3, -7};
    
    	if(insiemi_uguali(a, b, sizeof(a)/sizeof(double), sizeof(b)/sizeof(double)))
    		printf("OK");
    	else
    		printf("KO");
    
    	getchar();
    	return 0;
    }
    
    Il significato è:

    1) verifica che gli array da controllare abbiano le stesse dimensioni: se non ce l'hanno, allora gli insiemi sono diversi
    2) se non ci sono più elementi da confrontare abbiamo finito: gli insiemi sono uguali
    3) controlla che l'ultimo elemento del primo array sia presente nel secondo array
    4) se l'hai trovato, sposta l'elemento che hai trovato all'ultimo posto del secondo array, dopodiché elemina gli elementi all'ultimo posto di entrambe gli array e ricomincia la verifica da capo con un elemento in meno da controllare
    5) se non l'hai trovato, allora gli insiemi sono diversi

    L'esercizio sull'intersezione devi, però, farlo da solo
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Weierstrass ha scritto:



    Vabbé ti posto la soluzione allora:
    
    bool insiemi_uguali(double a1[], double a2[], int num_elem1, int num_elem2)
    {
    	int i;
    	double temp;
    
    	if(num_elem1 != num_elem2)
    	    return false;
    	
    	if(num_elem1 == 0)
    	    return true;
    	    
    	for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
    	       return insiemi_uguali(a1, a2, num_elem1 - 1, num_elem2 - 1);
    	    }
    	    
    	return false;
    }
    
    int main(void)
    {
    	double a[5] = {3, -7, 3, -0.5, 1};
    	double b[5] = {1, 3, -0.5, 3, -7};
    
    	if(insiemi_uguali(a, b, sizeof(a)/sizeof(double), sizeof(b)/sizeof(double)))
    		printf("OK");
    	else
    		printf("KO");
    
    	getchar();
    	return 0;
    }
    
    Il significato è:

    1) verifica che gli array da controllare abbiano le stesse dimensioni: se non ce l'hanno, allora gli insiemi sono diversi
    2) se non ci sono più elementi da confrontare abbiamo finito: gli insiemi sono uguali
    3) controlla che l'ultimo elemento del primo array sia presente nel secondo array
    4) se l'hai trovato, sposta l'elemento che hai trovato all'ultimo posto del secondo array, dopodiché elemina gli elementi all'ultimo posto di entrambe gli array e ricomincia la verifica da capo con un elemento in meno da controllare
    5) se non l'hai trovato, allora gli insiemi sono diversi

    L'esercizio sull'intersezione devi, però, farlo da solo
    Okay ora ho capito come l'hai pensata, ho provato a metterla nel pgm ma non funziona comunque
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Smarties ha scritto:


    Weierstrass ha scritto:



    Vabbé ti posto la soluzione allora:
    
    bool insiemi_uguali(double a1[], double a2[], int num_elem1, int num_elem2)
    {
    	int i;
    	double temp;
    
    	if(num_elem1 != num_elem2)
    	    return false;
    	
    	if(num_elem1 == 0)
    	    return true;
    	    
    	for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
    	       return insiemi_uguali(a1, a2, num_elem1 - 1, num_elem2 - 1);
    	    }
    	    
    	return false;
    }
    
    int main(void)
    {
    	double a[5] = {3, -7, 3, -0.5, 1};
    	double b[5] = {1, 3, -0.5, 3, -7};
    
    	if(insiemi_uguali(a, b, sizeof(a)/sizeof(double), sizeof(b)/sizeof(double)))
    		printf("OK");
    	else
    		printf("KO");
    
    	getchar();
    	return 0;
    }
    
    Il significato è:

    1) verifica che gli array da controllare abbiano le stesse dimensioni: se non ce l'hanno, allora gli insiemi sono diversi
    2) se non ci sono più elementi da confrontare abbiamo finito: gli insiemi sono uguali
    3) controlla che l'ultimo elemento del primo array sia presente nel secondo array
    4) se l'hai trovato, sposta l'elemento che hai trovato all'ultimo posto del secondo array, dopodiché elemina gli elementi all'ultimo posto di entrambe gli array e ricomincia la verifica da capo con un elemento in meno da controllare
    5) se non l'hai trovato, allora gli insiemi sono diversi

    L'esercizio sull'intersezione devi, però, farlo da solo
    Okay ora ho capito come l'hai pensata, ho provato a metterla nel pgm ma non funziona comunque
    In che senso non funziona? Come fa a non funzionare?
  • Re: Trasformare un funzione da iterativa a ricorsiva

    Weierstrass ha scritto:


    Smarties ha scritto:


    Weierstrass ha scritto:



    Vabbé ti posto la soluzione allora:
    
    bool insiemi_uguali(double a1[], double a2[], int num_elem1, int num_elem2)
    {
    	int i;
    	double temp;
    
    	if(num_elem1 != num_elem2)
    	    return false;
    	
    	if(num_elem1 == 0)
    	    return true;
    	    
    	for(i=0; i<num_elem1; i++)
    	    if(a2[i] == a1[num_elem1 - 1])
    	    {
    	       temp = a2[num_elem1 -1];
    	       a2[num_elem1 - 1] = a2[i];
    	       a2[i] = temp;
    	       return insiemi_uguali(a1, a2, num_elem1 - 1, num_elem2 - 1);
    	    }
    	    
    	return false;
    }
    
    int main(void)
    {
    	double a[5] = {3, -7, 3, -0.5, 1};
    	double b[5] = {1, 3, -0.5, 3, -7};
    
    	if(insiemi_uguali(a, b, sizeof(a)/sizeof(double), sizeof(b)/sizeof(double)))
    		printf("OK");
    	else
    		printf("KO");
    
    	getchar();
    	return 0;
    }
    
    Il significato è:

    1) verifica che gli array da controllare abbiano le stesse dimensioni: se non ce l'hanno, allora gli insiemi sono diversi
    2) se non ci sono più elementi da confrontare abbiamo finito: gli insiemi sono uguali
    3) controlla che l'ultimo elemento del primo array sia presente nel secondo array
    4) se l'hai trovato, sposta l'elemento che hai trovato all'ultimo posto del secondo array, dopodiché elemina gli elementi all'ultimo posto di entrambe gli array e ricomincia la verifica da capo con un elemento in meno da controllare
    5) se non l'hai trovato, allora gli insiemi sono diversi

    L'esercizio sull'intersezione devi, però, farlo da solo
    Okay ora ho capito come l'hai pensata, ho provato a metterla nel pgm ma non funziona comunque
    In che senso non funziona? Come fa a non funzionare?
    Mi da OK quando dovrebbe essere KO
Devi accedere o registrarti per scrivere nel forum
21 risposte