[c++] funzione ricorsiva definita come segue

[mistergks]

Sia A l'insieme ricorsivo di numeri naturali definito come segue:

0 non appartiene ad A
1 appartiene ad A
X appart. ad A se e solo se (3x-2)/6 appartiene ad A, per ogni x>1

Si scriva in C++ una funzione ricorsiva che verifichi se un dato numero appartiene o meno all'insieme A.
Specificare quale deve essere la prima invocazione per la funzione.
NOTA: La divisione si intende fra interi (non negativi), quindi da approssimare per difetto.

cos'è che non va?

mio codice

#include <iostream>
using namespace std;

bool verifica(int x);

int main(){
    int x=5;
    if(verifica(x))
    cout<<"ok"<<endl;
    else
    cout<<"no"<<endl;
    
    
system("pause");
return 0;
}

bool verifica(int x){
     int xx=0;
     
     if(x == 0 || xx == 0)
     return false;
     
     if(x == 1 || xx == 1)
     return true;
     
    if(x > 1)
    xx=(3*x-2)/6;
    
    return verifica(xx);
     
}

[ESSE-EFFE]

Originariamente inviato da mistergks

Sia A l'insieme ricorsivo di numeri naturali definito come segue:

Cioè come?

[mistergks]

C'è stato un errore di copia incolla..ora ho messo la definizione..

Inviato dal mio GT-I9003 usando Tapatalk

[vendettaaaaa]

Originariamente inviato da mistergks

Sia A l'insieme ricorsivo di numeri naturali definito come segue:
0 non appartiene ad A
1 appartiene ad A
X appart. ad A se e solo se 3x-2/6 appartiene ad A

Si scriva in C++ una funzione ricorsiva che verifichi se un dato numero appartiene o meno all'insieme A.
Specificare quale deve essere la prima invocazione per la funzione.
NOTA: La divisione si intende fra interi (non negativi), quindi da approssimare per difetto.

cos'è che non va?

mio codice

#include 
using namespace std;

bool verifica(int x);

int main(){
    int x=5;
    if(verifica(x))
               cout<<"ok";
    else   cout<<"no";

return 0;
}

bool verifica(int x){
        int xx= 0;

        if(x == 0 || xx ==0)
            return false;

         if(x == 1 || xx == 1)
            return true;

       xx=(3*x-2)/6;
          return verifica(xx);
}

Non ho ben capito la definizione...devo ricorsivamente applicare la formula fino a che il mio numero x diventa o 1 o 0?
E la formula qual è? Nella definizione hai scritto 3x-2/6, nel codice invece (3x-2)/6, che già usando 2 non da un numero intero...

A prescindere da tutto ciò, verifica uscirà sempre con false senza mai richiamarsi nemmeno una volta, perchè tu imponi xx = 0 e poi esci subito al primo if...

[mistergks]

ora ho messo definitivamente apposto la traccia e il codice...scusate ma ho postato con lo smartphone e mi sono perso qualcosa

Quindi credo che si debba fare cosi...se x è uguale a deve ritornare false, se x è uguale a 1 true e se x>1 deve passare nella formula (3x-2)/6 .
E credo debba convergere verso uno dei casi base...altrimenti non ho capito nemmeno io la traccia!

[vendettaaaaa]

Originariamente inviato da mistergks

ora ho messo definitivamente apposto la traccia e il codice...scusate ma ho postato con lo smartphone e mi sono perso qualcosa

Quindi credo che si debba fare cosi...se x è uguale a deve ritornare false, se x è uguale a 1 true e se x>1 deve passare nella formula (3x-2)/6 .
E credo debba convergere verso uno dei casi base...altrimenti non ho capito nemmeno io la traccia!

Sarà come dici tu con la formula (3x-2)/6. Ieri ho detto che usando x = 2 non si ottiene un numero intero ma in realtà essendo una divisione tra interi si otterrebbe 0.
Cmq basta che negli if tu metta il controllo solo su x e non su xx, il resto va bene.

[mistergks]

Originariamente inviato da vendettaaaaa

Sarà come dici tu con la formula (3x-2)/6. Ieri ho detto che usando x = 2 non si ottiene un numero intero ma in realtà essendo una divisione tra interi si otterrebbe 0.
Cmq basta che negli if tu metta il controllo solo su x e non su xx, il resto va bene.

Ad esempio mettendo x=5...facendola a mano dopo tutte le ricorsioni verrebbe 1 e quindi restituirebbe true...invece mi dà false! (sempre arrotondando per difetto e quindi usando gli int)..

Ho inizializzato x=3 e mi stampa OK... provando a mano..viene 1 al primo passo...quindi secondo me si ferma a un solo passo e non viene richiamata piu' volte la funzione... l'errore è questo ma non so come risolverlo

[vendettaaaaa]

5 è false:
1° chiamata 5 == 0? no, 5 == 1? no, allora xx = (15-2)/6 = 13/6 = 2; return verifica(2).
E sappiamo che 2 restituisce false.

[vendettaaaaa]

#include <iostream>

using namespace std;

bool verifica(int x);

int main()
{
	for (int i = 0; i <= 100; ++i) {
		cout << i << " does";
		if (!verifica(i)) cout << " not";
		cout << " belong to this weird recursive sequence" << endl;
	}
	cout << endl;

	return 0;
}

bool verifica(int x)
{
	if (x == 0) return false;
	else if (x == 1) return true;
	else {
		int y = (3*x - 2)/6;
		return verifica(y);
	}     
}

[mistergks]

Originariamente inviato da vendettaaaaa

5 è false:
1° chiamata 5 == 0? no, 5 == 1? no, allora xx = (15-2)/6 = 13/6 = 2; return verifica(2).
E sappiamo che 2 restituisce false.

opsss è vero!! non so manco fare i conti più ..
E allora qual'è un numero > 1 che restituisce true?! non riesco a trovarlo!

[cenarius_88]

Mi sbaglierò ma...

prova con x = 3.

3==0? no... procede
3==1? no... procede
(3*3-2)/6=(9-2)/6=7/6=1 (per arrotontamento all'intero più vicino)
procede con verifica(1)

1==0?no... procede
1==1?si... vero....stampa ok