DOMANDA Programmi con ricorsione C++

[Zeus Giove]

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?

 

[rodhellas]

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?

https://forum.tomshw.it/threads/programmi-con-ricorsione-c.767767/#post-7219379

 

[MPG]

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...

#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)

// 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?

#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
 }

 

[Zeus Giove]

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.

 

[MPG]

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.

 

[Zeus Giove]

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

Post unito automaticamente: 5 Maggio 2019

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.

Ok, scusa

 

[MPG]

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

Post unito automaticamente: 5 Maggio 2019

Ok, scusa

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

 

[Zeus Giove]

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

Post unito automaticamente: 5 Maggio 2019

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

 

[MPG]

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

 

[Zeus Giove]

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
...

 

[MPG]

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 ?

 

[DispatchCode]

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 ?

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.

 

[Zeus Giove]

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

 

[MPG]

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)

#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);

    }

Post unito automaticamente: 5 Maggio 2019

Passando alla ricerca numero primo con ricorsione cosa non va?
Mi si blocca alla prima parentesi graffa....

#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]

 

[DispatchCode]

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.