DOMANDA Programmi con ricorsione C++

MPG

Utente Attivo
544
4
Ho fatto cosi' modificando il code (aiutato anche un po' guardando online)
Non riesco solo a capire
return primo(n, d - 1);
nel senso come fa il programma a creare i valori dei divisori?
Non è che ho impostato di controllare ogni numero con cui devo provare a dividere n sino a d<n/2...
es poniamo che metto 100 come numero farà il calcolo sino a n/2
quindi 2, 4, 5, 10, 20, 25, 50 e ovviamente 100 non è primo ma come trova questi divisori per arrivare al risultato?


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

using namespace std;

int primo(int n, int d)
{
    if (n < 2) {
        return 0;
    }

    if (d == 1) {
        return 1;
    } else {
        if (n % d == 0) {
            return 0;
        } else
      {
            return primo(n, d - 1);
        }
    }
}

int main()
{

int n;
cin >> n;
cout << (primo(n, n / 2) ? "numero primo" : "non e' primo")<< "\n";
}
[CODE]
 
Ultima modifica:

_Achille

Utente Èlite
3,067
725
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
HDD
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
GPU
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
PSU
RM550X
Case
NZXT S340
Periferiche
Anne Pro 2, Razer Abyssus
OS
Windows 10 Pro
Ho fatto cosi' modificando il code (aiutato anche un po' guardando online)
Non riesco solo a capire
return primo(n, d - 1);
nel senso come fa il programma a creare i valori dei divisori?
Non è che ho impostato di controllare ogni numero con cui devo provare a dividere n sino a d<n/2...
es poniamo che metto 100 come numero farà il calcolo sino a n/2
quindi 2, 4, 5, 10, 20, 25, 50 e ovviamente 100 non è primo ma come trova questi divisori per arrivare al risultato?


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

using namespace std;

int primo(int n, int d)
{
    if (n < 2) {
        return 0;
    }

    if (d == 1) {
        return 1;
    } else {
        if (n % d == 0) {
            return 0;
        } else
      {
            return primo(n, d - 1);
        }
    }
}

int main()
{

int n;
cin >> n;
cout << (primo(n, n / 2) ? "numero primo" : "non e' primo")<< "\n";
}
[CODE]
Il problema è che si vede troppo cosa copi da internet. int primo(int, int) dovrebbe ritornare un bool e non un int visto che sei in C++ e non in pre C99.

Non è proprio così. Il programma controlla se il numero è esattamente divisibile per la sua metà. Se si, ritorna false (0), altrimenti controlla per metà - 1. E fa così finché non controlla per 1, a tal punto può ritornare true (1)
 
  • Mi piace
Reazioni: MPG

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,210
1,846
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
Semplicemente decrementa i divisori da n/2 a 1. Se d==1 allora è primo.
La ricorsione si interrompe subito, non appena avviene il return 0 o il return 1.
La metà la passi tu la prima volta, non divide per la metà ad ogni chiamata; ad ogni chiamata decrementa solo il divisore.
 
  • Mi piace
Reazioni: MPG

MPG

Utente Attivo
544
4
Scusate per una ricorsione di una potenza con due parametri x e y (in partica x^y) va bene cosi'?

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

using namespace std;


double potenza(int x, int y)
{

if (x == 0 &&  y==0)
    return -1;
if (x==0)
    return 0;
if (y==0)
return 1;
else
return x*potenza(x,y-1);

}

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

[CODE]
 
Ultima modifica:

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,210
1,846
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
No, non è corretto. E anche le condizioni non è che siano corrette.
Devi moltiplicare x per sé stessa y volte.
 

MPG

Utente Attivo
544
4
Scusa mi dici perchè le condizioni non sono corrette?
il return -1 è perchè è 0 elevato a 0 è impossibile/indeterminata , return 1 quando y=0 per cui x elevato a 0 è 1, return 0 quando x= 0
Inoltre se metto ad es x =2 e y=3 risulta perfettamente 8, per cui fammi capire perchè non è corretto.
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,210
1,846
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
Chiedo venia, ho visto la somma e non la moltiplicazione, ecco perchè ti ho scritto che devi moltiplicare...
E' corretto.

L'unica cosa che non è proprio corretta è l'utilizzo di double, in quanto restituisci un numero intero.
 

rodhellas

Utente Èlite
1,522
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
Scusa mi dici perchè le condizioni non sono corrette?
il return -1 è perchè è 0 elevato a 0 è impossibile/indeterminata , return 1 quando y=0 per cui x elevato a 0 è 1, return 0 quando x= 0
Inoltre se metto ad es x =2 e y=3 risulta perfettamente 8, per cui fammi capire perchè non è corretto.
Funziona, ti manca solo il caso in cui y sia < 0 (spoiler: ti esplode)
 
  • Mi piace
Reazioni: DispatchCode

MPG

Utente Attivo
544
4
Chiedo venia, ho visto la somma e non la moltiplicazione, ecco perchè ti ho scritto che devi moltiplicare...
E' corretto.

L'unica cosa che non è proprio corretta è l'utilizzo di double, in quanto restituisci un numero intero.

Scusa pe ril disorso del double dovrei forse mettere double potenza(double x, double y)?
E' che se anche metto cosi' se metto x= 2,5 mi da' subito return 1 perchè??
 

rodhellas

Utente Èlite
1,522
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
Scusa pe ril disorso del double dovrei forse mettere double potenza(double x, double y)?
No devi mettere int potenza(int x, int y). Una moltiplicazione tra interi ritorna un intero.
Per la storia del 2.5, tu hai dichiarato x come intero (nel main). Se vuoi farlo funzionare come double, allora mettilo double (e non solo nel main).
Ormai ti dovrebbe essere chiara la differenza tra int e double...
 

Zeus Giove

Nuovo Utente
21
11
Non sono esperto, ma io metterei a potenza un tipo dati più grande di quello dato a X e Y, perché 10(che sta in 1 byte)^3(che sta in un byte)=1000(che non sta in un byte), giusto per dire l'oedine di grandezza, esponenziale letteralmente, che temo rischi di far arrivare a overflow di variabili, con riaultati errati

N. B. Non so se la cosa ha senso in programmi per pc, io vengo da microcontrollori, appunto micro, dove quello delle variabili é un problema serio
Post unito automaticamente:

Non sono esperto, ma io metterei a potenza un tipo dati più grande di quello dato a X e Y, perché 10(che sta in 1 byte)^3(che sta in un byte)=1000(che non sta in un byte), giusto per dire l'oedine di grandezza, esponenziale letteralmente, che temo rischi di far arrivare a overflow di variabili, con riaultati errati

N. B. Non so se la cosa ha senso in programmi per pc, io vengo da microcontrollori, appunto micro, dove quello delle variabili é un problema serio
 

MPG

Utente Attivo
544
4
No devi mettere int potenza(int x, int y). Una moltiplicazione tra interi ritorna un intero.
Per la storia del 2.5, tu hai dichiarato x come intero (nel main). Se vuoi farlo funzionare come double, allora mettilo double (e non solo nel main).
Ormai ti dovrebbe essere chiara la differenza tra int e double...
Si è chiara la differenza double e int ma cosi' nemmeno va se metto un numero decimale in x perchè???

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

using namespace std;

double potenza(double x, double y)
{

if (x == 0 &&  y==0)
    return -1;
if (x==0)
    return 0;
if (y==0)
return 1;
else
return x*potenza(x,y-1);
}

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

[CODE]
 

_Achille

Utente Èlite
3,067
725
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
HDD
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
GPU
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
PSU
RM550X
Case
NZXT S340
Periferiche
Anne Pro 2, Razer Abyssus
OS
Windows 10 Pro
Si è chiara la differenza double e int ma cosi' nemmeno va se metto un numero decimale in x perchè???

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

using namespace std;

double potenza(double x, double y)
{

if (x == 0 &&  y==0)
    return -1;
if (x==0)
    return 0;
if (y==0)
return 1;
else
return x*potenza(x,y-1);
}

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

[CODE]
Quando elevi 10 alla 3.2 non puoi moltiplicare 10 per se stesso 3.2 volte. Quello che in matematica si fa è scrivere 3.2 come 16/5 e fare la radice quinta di 10 alla 16.
In definitiva con questo procedimento puoi fare sì potenze con base razionale ma solo con esponente intero. Anzi puoi pure gestire esponenti negativi (ma sempre interi!) come divisioni.

Non sono esperto, ma io metterei a potenza un tipo dati più grande di quello dato a X e Y, perché 10(che sta in 1 byte)^3(che sta in un byte)=1000(che non sta in un byte), giusto per dire l'oedine di grandezza, esponenziale letteralmente, che temo rischi di far arrivare a overflow di variabili, con riaultati errati

N. B. Non so se la cosa ha senso in programmi per pc, io vengo da microcontrollori, appunto micro, dove quello delle variabili é un problema serio
Post unito automaticamente:

Non sono esperto, ma io metterei a potenza un tipo dati più grande di quello dato a X e Y, perché 10(che sta in 1 byte)^3(che sta in un byte)=1000(che non sta in un byte), giusto per dire l'oedine di grandezza, esponenziale letteralmente, che temo rischi di far arrivare a overflow di variabili, con riaultati errati

N. B. Non so se la cosa ha senso in programmi per pc, io vengo da microcontrollori, appunto micro, dove quello delle variabili é un problema serio
int al 99% è almeno 4 byte, non ci sono problemi.
 
  • Mi piace
Reazioni: MPG

BAT

Moderatore
Staff Forum
Utente Èlite
22,668
11,452
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
L'esercizio è sulla ricorsione non sull'analisi matematica: stando così le cose, puoi ignorare bellamente le potenze negative.
Per quanto riguarda il tipo di dati, il tipo di ritorno della funzione deve essere uguale a quello della base che vuoi elevare a potenza, quindi se ti servono i numeri in virgola mobile devi avere
double potenza(double base, int esponente)
invece l'esponente deve essere per forza un tipo intero altrimenti non fai un esercizio di ricorsione.
Il caso di base=0 ed esponente=0 va trattato a parte, restituire un valore convenzionale pari a -1 è poco corretto (meglio sollevare un'eccezione) perché coincide con -1^(esponente dispari); è (quasi) accettabile solo se la cosa va considerato un puro esercizio, in realtà da programma devi evitare di chiamare la funzione potenza con base ed esponente 0 (basta un semplicissimo if)
 

MPG

Utente Attivo
544
4
L'esercizio è sulla ricorsione non sull'analisi matematica: stando così le cose, puoi ignorare bellamente le potenze negative.
Per quanto riguarda il tipo di dati, il tipo di ritorno della funzione deve essere uguale a quello della base che vuoi elevare a potenza, quindi se ti servono i numeri in virgola mobile devi avere
double potenza(double base, int esponente)
invece l'esponente deve essere per forza un tipo intero altrimenti non fai un esercizio di ricorsione.
Il caso di base=0 ed esponente=0 va trattato a parte, restituire un valore convenzionale pari a -1 è poco corretto (meglio sollevare un'eccezione) perché coincide con -1^(esponente dispari); è (quasi) accettabile solo se la cosa va considerato un puro esercizio, in realtà da programma devi evitare di chiamare la funzione potenza con base ed esponente 0 (basta un semplicissimo if)

Ho provato come dici tu ma non cambia nulla se metto X=2,5, mi viene subito return 1..

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

using namespace std;

double potenza(double x, int y)
{

if (x == 0 && y==0)
return -1;
if (x==0)
return 0;
if (y==0)
return 1;
else
return x*potenza(x,y-1);
}

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

[CODE]
 

Ci sono discussioni simili a riguardo, dai un'occhiata!

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili