DOMANDA Programmi con ricorsione C++

Pubblicità
Ma spiegatemi una cosa, a detta dell'OP gli esercizi erano scrivere delle funzioni con 1 (uno) parametri ciascuna, due interi ed una stringa, quando è comparso il bisogno di 2 (due) parametri nelle funzioni intere, di cui uno un array di interi?
 
Scusate ho bisogno di capire bene la ricorsione.
IN questo esempio in cui deve implementare la divisione intera ricorsiva procedendo per sottrazioni successive viene usato
return 1+divisione(a-b,b)
ora se i 2 numeri sono 9 e 4 avrei
1+(9-4/4)= qui già mi perdo il meccanismo...


C++: 
#include <iostream>

using namespace std;

int divisione(int a, int b);

    int main(){
    int a,b;
        do{
            cin>>a ;
            cout<<endl;
            cin>>b;
            cout<<endl;
        }
while(a < 0 || b < 0);
       cout<< divisione(a,b);
    }
    int divisione(int a, int b){
        if (a == 0)
            return 0;
        if(b == 0)
            return -1;
        return 1+divisione(a-b,b);
    }

Poi per il MCD ho capito il meccanismo nella seconda forma qui con
return mcd(m-n, n);
else return mcd(m, n-m)

non ho capito bene il meccanismo con
return mcd(y,x%y)

C++: 
// Massimo comun divisore

#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>

using namespace std;

int mcd (int x, int y)
{
if (y==0)
return x;
else
return mcd(y,x%y);
}

int main()
{
int x;
cin>>x;
int y;
cin>>y;
cout<<mcd(x,y);
}

/*


#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>

using namespace std;
int mcd(int m, int n)
{if (m==n)
return m;
else
if (m>n)
return mcd(m-n, n);
else return mcd(m, n-m);
}

int main()
{
int m;
cin>>m;
int n;
cin>>n;
cout<<mcd(m,n);
}
*/
[CODE]

Infine per la ricerca di un numero primo mi dite perchè questo non va?

C++: 
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>



using namespace std;

int numeroprimo(int n, int div);

{
    if (n==1)
    return 0;
    if (div==1)
    return 1;
    if ((n%div)>0))
    return numeroprimo (n, div-1);
    return 0
 }
 
Ultima modifica:
Cominciamo a chiarire una cosa: che compito hai? Prima parli di "stringhe palindrome", ora parli di "divisione" e "MCD", senza aver finito (a quanto mi risulta) il compito precedente.
 
I primi 3 esercizi nel post di inzio li ho risolti, ora vorrei capire meglio l'esercizio ricorsivo della divisione, del mcd e del numero primo.
 
Nel programma della divisione ci sono un paio di errori, credo. Riscriviamone la funzione, spiegandola (a parte che se chiunque abbia dato questo esercizio è un sadico:) ). Partiamo da un fatto: 10:2=5
Come alle elementari dicono che la moltiplicazione è un insieme di somme la divisione sarà un insieme di sottrazioni, fino a che esse sono possibili, vediamola come tale.
10, 2. 10>=2? Si, faccio 1 sottrazione e me la segno (risultato++)10-2=8, 2
8,2, 8>=2? Si, faccio una sottrazione e me la segno (risultato ++) 8-2=6, 2
...4,2
...2,2
2>=2? Si, faccio una sottrazione e me la segno (risultato ++) 2-2=0, 2
0,2. 0>=2? NO, quindi NON faccio la sottrazione e ho finito, ritorno al livello precedente e, sommando tutti i "e me lo segno" ottengo il risultato

Come vedi ho ottenuto il risultato, segno in 2,2+4,2+6,2+8,2+10,2=5 segno=5
E se fosse stato 11? È questo l'errore nella funzione, centra con il primo if di uscita
--- i due messaggi sono stati uniti ---
MPG ha detto:
I primi 3 esercizi nel post di inzio li ho risolti, ora vorrei capire meglio l'esercizio ricorsivo della divisione, del mcd e del numero primo.
Clicca per espandere...
Ok, scusa
 
Zeus Giove ha detto:
Nel programma della divisione ci sono un paio di errori, credo. Riscriviamone la funzione, spiegandola (a parte che se chiunque abbia dato questo esercizio è un sadico:) ). Partiamo da un fatto: 10:2=5
Come alle elementari dicono che la moltiplicazione è un insieme di somme la divisione sarà un insieme di sottrazioni, fino a che esse sono possibili, vediamola come tale.
10, 2. 10>=2? Si, faccio 1 sottrazione e me la segno (risultato++)10-2=8, 2
8,2, 8>=2? Si, faccio una sottrazione e me la segno (risultato ++) 8-2=6, 2
...4,2
...2,2
2>=2? Si, faccio una sottrazione e me la segno (risultato ++) 2-2=0, 2
0,2. 0>=2? NO, quindi NON faccio la sottrazione e ho finito, ritorno al livello precedente e, sommando tutti i "e me lo segno" ottengo il risultato

Come vedi ho ottenuto il risultato, segno in 2,2+4,2+6,2+8,2+10,2=5 segno=5
E se fosse stato 11? È questo l'errore nella funzione, centra con il primo if di uscita
--- i due messaggi sono stati uniti ---

Ok, scusa
Clicca per espandere...

La mi difficoltà è questa , se io imposto
return 1+divisione(a-b,b)
io immagino che al numero 1 devo sempre sommare a 1 la divisione di a-b/b per cui
se a= 10
b=2
io penso
1+8/2=1+4= 5...

invece in pratica se fosse ad es 6 e 2 devo ragionare cosi' anche se non capisco perchè...
6 / 2 -> divisione(6, 2) -> 1+divisione(4, 2) -> 1+1+divisione(2, 2) -> 1+1+1+divisione(0, 2) -> 1+1+1+0 = 3
 
Ultima modifica:
Si, ma nella forma
10/2=1+
8/2=1+
6/2=1+
4/2=1+
2/2=1+
0/2=0 fine

Cosa ci trovi di diverso da quello che avviene? Scusa, ma non lo posso provare, quindi non lo so
--- i due messaggi sono stati uniti ---
Il problema, nel programma che hai, si ha con due numeri non divisibili, come 9 e 4, perché,l proprio perché non sono divisibili 9-(4*N) non farà mai 0, ma scenderà sotto e l'insieme delle sottrazioni continuerà, la condizione di uscita numero 1 è sbagliata, non è A==0
 
IN sostanza mi aspettavo che se ho
return 1+divisione(a-b,b)
dovrei aggiungere ogni volta 1 a quello che mi risulta dalla divisione di divisione(a-b,b)
per cui se ragionassi cosi' mi troverei 15 come totale invece devo fare un ragionamento di contare solo la somma dei vari 1 , è questo il punto.
Ovviamente so che sbaglio ma volevo capire meglio il meccanismo per entrare i questa logica.
10/2=1+5
8/2=1+4
6/2=1+3
4/2=1+2
2/2=1+ 1
 
Dopo 2/2 rifai la sottrazione, quindi arrivi a 0/2, che fa 0, quindi risaliamo
0/2=0 punto
2/2=1+0=1
4/2=1+1=2
6/2=1+2=3
...
 
Si risali ma cosa ottieni??
Intendo dire ripeto hai
return 1+divisione(a-b,b)
se lo leggo io capisco aggiungo 1 alla divisione di a-b/b
che tradotto sarebbe 1+ (10-2)/2= 1+4= 5 questo comunque è il concetto e il risultato
Se e fosse esempio 9 e 4 , oppure 4 e 9 ?
 
MPG ha detto:
Si risali ma cosa ottieni??
Intendo dire ripeto hai
return 1+divisione(a-b,b)
se lo leggo io capisco aggiungo 1 alla divisione di a-b/b
che tradotto sarebbe 1+ (10-2)/2= 1+4= 5 questo comunque è il concetto e il risultato
Se e fosse esempio 9 e 4 , oppure 4 e 9 ?
Clicca per espandere...

Perché procedi per sottrazioni e non per divisioni. Ciò che fai con il +1 è contare quante volte il numero b sta in a. Non devi "tradurre" usando il /, perché non è ciò che avviene nella realtà.
I valori di a, per a=9 e b=4 sono:
9-4=5
5-4=1
1-4=-3

La condizione errata è il confronto con a==0, in quanto dovrebbe essere a<=0.
 
Speravo di riuscire a farti capire dove era l'errore, ma te lo dico. Il primo if della funzione è sbagliato, non è A==0, ma è A<B, che vuol dire che se sono arrivato a non poter fare la sottrazione ritorno 0, quindi 4/9 fa 0, 9/4 fa 1+0=1.
Facciamo 9/2
Chiamata 1, ho 9 e 2, nove è maggiore di due, quindi mi segno una sottrazione e la faccio, Richiamo con 7 e 2
Chiamata 2, ho 7 e 2, sette maggiore di due quindi mi segno una sottrazione e la faccio, Richiamo con 5 e 2
Chiamata 3 ho 5 e 2, cinque maggiore di due quindi mi segno una sottrazione e la faccio, Richiamo con 3 e 2
Chiamata 4, ho 3 e 2, tre maggiore di due quindi mi segno una sottrazione e la faccio, Richiamo con 1 e 2
Chiamata 5, ho 1 e 2, uno è MINORE di due, quindi NON faccio la sottrazione, e ritorno 0
Lo ritorno alla chiamata quattro, dove mi son segnato 1, 1+0=1, matematica, ritorno 1
Lo ritorno allachiamata 3, dove mi son segnato 1, 1+1=2, matematica, ritorno 2,
lo ritorno alla chiamata 2, dove mi son segnato 1, 2+1=3, matematica, ritorno 3
Lo ritorno alla chiamata 1, dove mi son segnato 1, 1+3=4, matematica, ritorno 4
Non essendoci una chiamata superiore il risultato di 9/2 è 4
 
Stavo per postare il code, l'avevo capito poi solo che mi stavo concentrando sulla divisione, anzi avevo fatto 2 modifiche.
Comunque il punto cruciale in pratica e' che quel 1 non va sommato alla divisione di a-b/b ma è in pratica calcolo quante chiamate diciamo "regolari" si hanno (nel tuo ultimo esempio la chiamata 5 comporta una sottrazione che non va bene perchè 1<2)

C++: 
#include <iostream>

using namespace std;

int divisione(int a, int b);



    int main(){

    int a,b;


        do{

            cin>>a ;
            cout<<endl;

            cin>>b;
            cout<<endl;
        }while(a < 0 || b < 0);


       cout<< divisione(a,b);
    }


    int divisione(int a, int b){

        if (a == 0  && b == 0)

            return -1;


        if(b == 0)
            return -2;

        if (a<b)
            return 0;


        return 1+divisione(a-b,b);

    }
--- i due messaggi sono stati uniti ---
Passando alla ricerca numero primo con ricorsione cosa non va?
Mi si blocca alla prima parentesi graffa....

C++: 
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>



using namespace std;

int numeroprimo(int n, int div);

{
if (n==1)
return 0;
if (div==1)
return 1;
if ((n%div)>0))
return numeroprimo (n, div-1);
return 0
}
[CODE]
 
Ultima modifica:
Sono un po' di fretta ti rispondo solo in merito all'errore: c'è il punto è virgola prima della giraffa. Viene vista come la dichiarazione della funzione, non come definizione.
Comunque il compilatore lo dice... impara a leggere gli errori, è fondamentale.
 
Pubblicità
Pubblicità
Indietro
Top