Problema ricorsione

di il
8 risposte

Problema ricorsione

Non riesco a capire quale sia il problema di questo programma, il testo è :

Scrivere in C++ una procedura o funzione ricorsiva che di come risultato true se una
matrice A rettangolare di N righe ed M colonne possiede due colonne uguali, false
altrimenti.

La variabile bol assume dei valori veramente assurdi e mi sembra che non mi sia chiara qualcosa di questa maledetta ricorsione..
#include<iostream>
using namespace std;
int matrice(int M[10][10],int n,int m,int c,int l);
main(){
	int M[10][10];
	int i,j,n,m,bol,c,d,l;
	bol=0;
	cout<<"Inserisci il numero delle righe"<<endl;
	cin>>n;
	cout<<"Inserisci il numero delle colonne"<<endl;
	cin>>m;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			cout<<"Inserisci il valore di riga "<<i<<" e colonna "<<j<<endl;
			cin>>M[i][j];
		}
	}
	c=m;
	l=n;
	d=matrice(M,n,m,c,l);
	cout<<d<<endl;
}
int matrice(int M[10][10],int n,int m,int c,int l){
	int bol;
	while ((bol==0)&&(m!=0)){
		if((M[n][m-1]==M[n][m])&&(l!=0)){
			c=c-1;
		}
		matrice(M,l-1,m,c,n);
		
		l=n;
		if (c==0){
			bol=1;
		}
		else{
			matrice(M,n,m-1,c,l);
		}
	}
	return bol;
}

8 Risposte

  • Re: Problema ricorsione

    Attenzione ad inizializzare le variabili che usi..
  • Re: Problema ricorsione

    O Dio mi sembra di averle inizializzate tutte ahahah dove sbaglio?
  • Re: Problema ricorsione

    Non mi pare

    int bol;
  • Re: Problema ricorsione

    oregon ha scritto:


    Non mi pare

    int bol;
    L'ho aggiunstato in questo modo ma il programma non parte e crasha
    #include<iostream>
    using namespace std;
    int matrice(int M[10][10],int n,int m,int c,int l,int bol);
    main(){
       int M[10][10];
       int i,j,n,m,bol,c,d,l;
       bol=0;
       cout<<"Inserisci il numero delle righe"<<endl;
       cin>>n;
       cout<<"Inserisci il numero delle colonne"<<endl;
       cin>>m;
       for(i=0;i<n;i++){
          for(j=0;j<m;j++){
             cout<<"Inserisci il valore di riga "<<i<<" e colonna "<<j<<endl;
             cin>>M[i][j];
          }
       }
       c=m;
       l=n;
       d=matrice(M,n,m,c,l,bol);
       cout<<d<<endl;
    }
    int matrice(int M[10][10],int n,int m,int c,int l,int bol){
       while ((bol==0)&&(m!=0)){
          if((M[n][m-1]==M[n][m])&&(l!=0)){
             c=c-1;
          }
          matrice(M,l-1,m,c,n,bol);
          
          l=n;
          if (c==0){
             bol=1;
          }
          else{
             matrice(M,n,m-1,c,l,bol);
          }
       }
       return bol;
    }
    
  • Re: Problema ricorsione

    La ricorsione di sicuro non è semplicissima, ma mi sembra che ti sfugga come sono passati e ritornati i parametri tra i vari passi nell'albero della ricorsione.

    Prova a spiegare che dovrebbe fare il ciclo while e vediamo insieme di risolvere il problema.
  • Re: Problema ricorsione

    SVNiko ha scritto:


    La ricorsione di sicuro non è semplicissima, ma mi sembra che ti sfugga come sono passati e ritornati i parametri tra i vari passi nell'albero della ricorsione.

    Prova a spiegare che dovrebbe fare il ciclo while e vediamo insieme di risolvere il problema.
    Il While dovrebbe confrontare le colonne della matrice e scrivere "1" se ci sono 2 colonne uguali, ma probabilmente sbaglio qualcosa
  • Re: Problema ricorsione

    La tua funzione matrice richiama all'infinito se stessa con gli stessi parametri, ecco perché va in stock overflow.

    Ti consiglio di impostare le funzioni ricorsive con il seguente schema:
    
    TipovalRitorno funRIC(Lista parametri){
        /* Passo base */
       ...
       return valRitorno;
    
       /* Ricorsione */
       funRIC(parametri modificati);
    
      /* Backtrack */
      ...
      return valRitorno;
    }
    
    Nel tuo caso il tuo obiettivo è verificare una colonna con una data, dovresti secondo me fare una funzione che confronta due colonne e usare quella per verificare il passo base.
    Al passo ricorsivo devi passare dei dati ridotti in maniera da ricadere prima o poi nel caso base.
  • Re: Problema ricorsione

    SVNiko ha scritto:


    La tua funzione matrice richiama all'infinito se stessa con gli stessi parametri, ecco perché va in stock overflow.

    Ti consiglio di impostare le funzioni ricorsive con il seguente schema:
    
    TipovalRitorno funRIC(Lista parametri){
        /* Passo base */
       ...
       return valRitorno;
    
       /* Ricorsione */
       funRIC(parametri modificati);
    
      /* Backtrack */
      ...
      return valRitorno;
    }
    
    Nel tuo caso il tuo obiettivo è verificare una colonna con una data, dovresti secondo me fare una funzione che confronta due colonne e usare quella per verificare il passo base.
    Al passo ricorsivo devi passare dei dati ridotti in maniera da ricadere prima o poi nel caso base.
    Grazie mille per l'aiuto ho capito molto meglio la ricorsione! E ho "risolto" semplicemente questo programma
Devi accedere o registrarti per scrivere nel forum
8 risposte