Problema del 3n+1

[blackdie]

Scusate per la banalità ma come faccio a scrivere in linguaggio c++ il seguente algoritmo,detto di collatz:


Si prenda un intero positivo n.
Se n è pari, si divida per due; se è dispari, si moltiplichi per 3 e si aggiunga 1.
Se n = 1, l'algoritmo termina; altrimenti si ripete dal secondo passo.


Mi potete fornire il codice?


Grazie .

[ilprincipe1984]

Qua qualcuno ha le idee un po' confuse sul programma...cercherò di spiegarti io come funzionano quei programmi, semplicemente:
devi utilizzare la ricorsione. E' anche vero che è possibile fare una funzione iterativa, che in generale è meglio dal punto di vista della memoria, ma nella gran maggioranza dei casi è più difficile da scrivere, o non esiste. Nessuno dei programmi precedenti(che ho letto molto rapidamente) funziona. Perchè ogni volta devi applicare lo stesso algoritmo al nuovo numero che generi! Il codice presenta dei commenti , che sono preceduti dal // così il preprocessore del C li elimina da quello che poi trasforma in codice oggetto e in codice macchina! Eliminali anche dalla relazione.


#include

void collatz(int n){
if (n=1) return;
else if (n % 2 ==0) {
printf("%d",n/2); // stampiamo a video n diviso per 2
collatz(n/2); // richiamiamo collatz su n/2, cioè se la prima volta n = 12, chiamiamo questa volta collatz con n=6, che poi la richiamerà con n=3 ecc.
}
else
{
printf ("%d",3n+1); // stampiamo a video 3n+1;
collatz(3n+1); //rieseguiamo collatz su 3n+1;
}
}

void main(){
int a;
printf("Inserisci un numero ");
scanf("%d", &a); // lettura di un carattere dalla tastiera in C
collatz(a);
}

Stai attento che l'algorimto da come l'hai descritto termina solo in certi casi, in altri mi sembra vada avanti all'infinito:
Esempio n=6
viene eseguito collatz(6)
collatz(6) stampa 6/2 e lancia collatz(6/2)
collatz(3) stampa 3*3 +1 e lancia collatz(3*3+1)
collatz(10) stampa 10/2 e lancia collatz(5)
collatz(5) stampa 16 e lancia collatz di 16 e cosi via...
in realtà N tende a crescere all'infinito per ogni numero non divisibile per 2!

La versione iterativa, invece, appare così

void main(){
int a;
printf("Inserisci un numero ");
scanf("%d", &a); // lettura di un carattere dalla tastiera in C
while (a!=1) {
if (a%2)=0
{
a=a/2;
printf("%d",a);
}
else
{
a=3a +1;
printf("%d",a);
} // fine if
} // fine ciclo while
} // fine void main

il codice in realtà è scritto in C e non in C++, perchè mi è più praaaaatico!

[blackdie]

ma il compiler mi da errore anche nei tuoi.....

[carlo232]

"blackdie":ma il compiler mi da errore anche nei tuoi.....

blackdie, ma il mio programma almeno lo hai provato?

[lorven]

Il programma Pascal da me postato è stato testato e funziona regolarmente, se si corregge l'errore (di battitura) ponendo "+" al posto do "-" nell' istruzione if... else n:=n*3-1;

[Bemipefe]

Allora ...vediamo se riesco a fare qualcosa di semplice.
Te lo faccio in C tanto il C++ si usa solo per gli oggetti e qualcosa di grafico.

#include <stdio.h>
#include <stdlib.h>


int main()
{
int buffer = 0;
int n = 0;
int value=0;

while(1)
{
printf("\n\n\n");
printf("|--------------------Congettura di Syracuse--------------------|\n");
printf("|                                                              |\n");
printf("|                                                              |\n");
printf("|--------------------------------------------------------------|\n");

printf("\nInserire il valore 'x' da Calcolcare:");
scanf("%d" , &buffer);




   while(1)
   {
      if(buffer == 1)
      {printf("Calcolo non definito per valore '1'\n");break;}

   n++;
   printf("********************************************\n");
   printf("Passo %d\n" , n);
   printf("x = %d\n" , buffer);
   value = (buffer % 2);

      if(value == 0)
      {
      printf("Pari\n");
      buffer = (buffer / 2);
      printf("x = x/2\n");
      }

      else 
      {
      printf("Dispari\n");
      buffer = (buffer * 3); 
      buffer = (buffer + 1);
      printf("x = 3x+1\n");
      }

   }

printf("\n\n\nPer uscire (CTRL + C)\n");

}


return 0;
}

...a me funziona alla grande . Se vuoi ti possomandare l'eseguibile per email.

Fammi sapere CIAO!

[luciano791]

"ilprincipe1984":Qua qualcuno ha le idee un po' confuse sul programma...cercherò di spiegarti io come funzionano quei programmi, semplicemente:
devi utilizzare la ricorsione. E' anche vero che è possibile fare una funzione iterativa, che in generale è meglio dal punto di vista della memoria, ma nella gran maggioranza dei casi è più difficile da scrivere, o non esiste. Nessuno dei programmi precedenti(che ho letto molto rapidamente) funziona. Perchè ogni volta devi applicare lo stesso algoritmo al nuovo numero che generi! Il codice presenta dei commenti , che sono preceduti dal // così il preprocessore del C li elimina da quello che poi trasforma in codice oggetto e in codice macchina! Eliminali anche dalla relazione.

Ma sei convinto di quello che dici?

Prima del tuo codice sono state scritte solo 3 funzioni, una sola sbagliata. Come fai a dire tutte?
La prima, scritta in C, non può funzionare, ok.
La seconda è in pascal e mi sembra corretta.
La terza è quella che ho scritto io in C e non ci vedo niente di sbagliato, mi sembra anche piuttosto semplice.

while(n != 1)
    {
        if (n % 2 == 0)
            n = n / 2;
        else
            n = n * 3 + 1;
        printf("%d\n",n);
        getch();
    };

La ricorsione non è sbagliata, ma in questo caso è eccessiva, dal punto di vista dello script è forse più semplice, ma dal punto di vista applicativo e di utilizzo risorse non c'è paragone. Se per esempio N assume 1000 valori pensa che il pc deve riservare lo spazio in memoria per 1000 variabili di tipo LongInteger contro una sola variabile di una semplice funzione. Se poi, come hai fatto te, non pensassimo a far visualizzare un numero alla volta (non lasci all'utente il tempo di leggerli), ci perdi anche per quel che riguarda la velocità. Quindi in questo caso non solo non serve una ricorsione, ma fa anche del "danno". Va utilizzata per casi molto + complicati. Per esempio quando si tratta di grafi, per scorrere le cartelle di un pc...

Il programma migliore non è quello più semplice da scrivere, ma quello che da la massima convenienza in termini tempo/risorse utilizzate. Stiamo parlando di un piccolo programma, ma quando i programmi si fanno lunghi occorre ottimizzare anche le cose più piccole per cercare di ottenere il massimo

"ilprincipe1984":Qua qualcuno ha le idee un po' confuse sul programma

Meglio evitare commenti

[blackdie]

@ carlo
ti ho risp via email
@bemifeme
mandami pure l'eseguibile via email!:-D

[Bemipefe]

Se ti connetti su MSN ce lo scambiamo li....anche perchè non riesco a reperire la tua e-mail.

[ilprincipe1984]

no la tua era giusta ma ho il mouse che scrolla male luciano:D

[zazzymomo]

So che magari ora non serve più a niente e che forse avete risolto privatamente...ma è meglio rendere pubblica la soluzione no?

#include
#include

using namespace std;

int main()
{

int n;
cout<<"Inserire numero: ";
cin>>n;

if((n%2==0)&&(n!=1)) cout< else if ((n%2!=0)&&(n!=1)) cout<<(n*3)+1<<"\n";
else return 0;

system("PAUSE");
return 0;
}

[superpunk733]

"Tittyna":So che magari ora non serve più a niente e che forse avete risolto privatamente...ma è meglio rendere pubblica la soluzione no?

#include
#include

return 0;
}

è normale che questo programma non funzioni a tutti xke le "vecchie" librerie d c++ sono state sostituite da altre con i nuovi compilatori: ora è semplicemente e ora è ;

[zazzymomo]

Guarda... http://www.cplusplus.com/ref/indexr.html

[Res1]

Se non ho capito male il processo è ricorsivo ed N si dovrebbe assottigliare sino a diventare 1.
Se così è bisognerebbe dimostarre che qualsiaisi N intero converge ad 1, altrimenti bisogna mettere un trap per mouse o tatiera per schiodarlo se si inlooppa.

[lorven]

Converge sempre a 1, per la nota "congettura di Syracuse" o di Collatz.
http://it.wikipedia.org/wiki/Congettura_di_Collatz

[Res1]

OK, pronti !

do
input n# ' input numero intero
n#=abs(n#) ' forza in posiitivo
if n#=0 then exit do ' esce se è zero

while n>1

if n mod(2)=0 then
n=n/2
else
n=n*3+1
end if

wend

loop

end