c++ ricorsione su array

[wgd-developer]

Salve,
dovrei scrivere un algoritmo ricorsivo che assegnati due array S1 e S2 restituisca TRUE se il secondo è contentuto tutto nel primo, FALSE in caso contrario.

qualche suggerimento su come impostarlo?

Grazie

[mondobimbi]

tu cosa suggerisci ?

[wgd-developer]

io pensavo di confrontare prima se S2 era maggiore di S1
in quel caso non doveva fare confronti

poi dopo se S2 era minore effettuare i confronti sulle singole lettere...

però non so se conviene fare scorrere prima l'array S2, e poi S1
Cioè
la prima lettera di S2 è M
trovo M in S1
e poi vedo se la seconda di S2
è uguale alla successiva di S1

cosa ne pensi?
grazie

[wgd-developer]

questo è la parte principale
ora cerco di creare la function

int main(){
    char S1[25];  
    int n, n2;  
    
    cout<<"Inserisci la prima parola : ";
    cin.getline(S1,25);
    n=strlen(S1);
    cout<<"Inserisci la seconda parola : ";
    cin.getline(S2,25);
    n2=strlen(S2);
    
    if(n2>n1)
             cout<<"La seconda parola non può essere contenuta nella prima";
             else
                 cout<<controllo(S1,S2,n1,n2);
    
    system("pause");   
}

[mondobimbi]

ricorsivamente il problema è risolvibile in questa maniera:
una array a1 è contenuta in una array a2 se il primo elemento di a1 è contenuto in a2 e la array ricavata da a1 sottratto il primo elemento è anch'esso contenuto in a2.
ciao
sergio

[wgd-developer]

Scusa, ma non ho capito

Se io ho

SMACCHIARE = S1

E

MACCHIA =S2

la prima lettera di s1 non è s2
ma l'array s2 è in s1
?

[mondobimbi]

Originariamente inviato da wgd-developer
Scusa, ma non ho capito

Se io ho

SMACCHIARE = S1

E

MACCHIA =S2

la prima lettera di s1 non è s2
ma l'array s2 è in s1
?

nel tuo caso tu devi verificare che s2 sia contenuto in s1.
Verifichi che M sia in S1, se si che anche ACCHIA sia contenuto in s1 .
prima ricorsione
Verifichi che A sia in S1, se si che anche CCHIA sia contenuto in s1 .
seconda ricorsione
Verifichi che C sia in S1, se si che anche CHIA sia contenuto in s1 .
....

prova a esprimerlo in codice
ciao

[mondobimbi]

:master: , con sono sicuro che funzioni, mi ci devo pensare un po'
ciao
sergio

[wgd-developer]

ciao, ho pensato ad una cosa del genere

/*
Testo :
Scrivere un algoritmo ricorsivo che assegnati due array S1 e S2 
restituisca TRUE se il secondo è contentuto tutto nel primo, 
FALSE in caso contrario.
*/


#include<cstdlib>
#include<iostream>

using namespace std;

bool controllo(char S1[], char S2[], int n1, int n2);

int main(){
    char S1[25];  
    char S2[25];  
    int n1, n2;  
    
    cout<<"Inserisci la prima parola : ";
    cin.getline(S1,25);
    n1=strlen(S1);
    cout<<"Inserisci la seconda parola : ";
    cin.getline(S2,25);
    n2=strlen(S2);
    
    if(n2>n1)
             cout<<"La seconda parola non può essere contenuta nella prima";
             else
                 cout<<controllo(S1,S2,n1,n2);
    
    system("pause");   
}


bool controllo(char S1[], char S2[], int n1, int n2){
     if (n2<0)
        return true;
        else if (S2[n2]==S1[n1])
             return controllo(S1, S2, n1-1, n2-1);
                    else
                    return controllo(S1, S2, n1-1, n2);
}

il problema sta nel caso base...
cioè faccio controllare tutto a ritroso...
dalla fine all'inizio delle parole
hai suggerimenti?

antonio

[mondobimbi]

ho abbozzato questo, guarda se può fare il caso tuo

/*
Testo :
Scrivere un algoritmo ricorsivo che assegnati due array S1 e S2 
restituisca TRUE se il secondo è contentuto tutto nel primo, 
FALSE in caso contrario.
*/


#include<cstdlib>
#include<iostream>

using namespace std;


bool controllo(char * S1, char * S2) {
	
	if (!*S1)
		return true;
	else {
		// cerca la prima occorrenza della prima lettera di S1
		while (*S2 && *S1 != *S2) S2++;
		if (!*S2) return false;	// non trovata, allora esci
		else return controllo(++S1, ++S2);
	}
}

int main(){

    char S1[25];  
    char S2[25];  
    
    cout<<"Inserisci la prima parola : ";
    cin.getline(S1,25);

    cout<<"Inserisci la seconda parola : ";
    cin.getline(S2,25);
    
    if (!controllo(S1, S2))
             cout<<"La prima parola non può essere contenuta nella seconda" << endl;
    else
             cout<<"La prima parola è contenuta nella seconda" << endl;
}

attenzione!! ho invertito i due array (il primo l'ho trasformato nel secondo e viceversa

ciao