Problema ricorsione

di Anonimizzato15595 il
8 risposte
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

  • Attenzione ad inizializzare le variabili che usi..
  • O Dio mi sembra di averle inizializzate tutte ahahah dove sbaglio?
  • Non mi pare

    int bol;
  • 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;
    }
    
  • 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.
  • 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
  • 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.
  • 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