La Congettura di Collatz (collatz) - 2014 - D=1

Una delle simulazioni più semplici probabilmente ma ottima per prendere confidenza con il sistema di esercitazione/consegna delle Olimpiadi. La soluzione  viene esposta in C++ senza usare i template  in C dati dall'organizzazione. 

Descrizione del problema

Consideriamo il seguente algoritmo, che prende in ingresso un intero positivo N:

  1. Se N vale 1, l’algoritmo termina.
  2. Se N è pari, dividi N per 2, altrimenti (se N è dispari) moltiplicalo per 3 e aggiungi 1.

Per esempio, applicato al valore N=6, l’algoritmo produce la seguente sequenza (di lunghezza 9, contando anche il valore iniziale N=6 e il valore finale 1):

 6, 3, 10, 5, 16, 8, 4, 2, 1.

La congettura di Collatz, chiamata anche congettura 3N+1, afferma che l’algoritmo qui sopra termini sempre per qualsiasi valore N; in altri termini, se prendo un qualsiasi numero intero maggiore di 1 applicare la regola numero 2 conduce sempre al numero 1.

(È riferendosi a questa celebre congettura che il famoso matematico Erdős ha commentato sul come questioni semplici ma elusive mettono in evidenza quanto poco noi si possa accedere ai misteri del “grande Libro”).

Giovanni sta cercando di dimostrare la congettura, ed è interessato alla lunghezza della sequenza. Il vostro compito è quello di aiutare Giovanni scrivendo un programma che, ricevuto in ingresso un numero N, calcoli la lunghezza della sequenza che si ottiene a partire da N.

 Dati di input

Il file input.txt è composto da una riga contenente N, un intero positivo.

 Dati di output

Il file output.txt è composto da una sola riga contenente un intero positivo L: la lunghezza della sequenza a partire da N.

 Assunzioni e note

 2 N 1000

  • E’ noto che, per qualsiasi N minore di 1000, la lunghezza L della sequenza è minore di 200

 

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <string>
#include <list>

using namespace std;

int main()
{
    /** VARIABILI */
    fstream fin;
    fstream fout;

    int N = 1; /** valore iniziale delle serie */
    int l = 1; /** lunghezza della sequenza */

    fin.open("input.txt", ios::in);
    fout.open("output.txt", ios::out);

    /** cout << "Inserisci il numero N della congettura di Collatz, chiamata anche congettura 3N+1"<<endl; */
    fin >> N;

    while (N != 1)
    {
        l++;
        /** controllo se N è pari */
        if (N % 2 == 0)
        {
            N = N / 2;
        }
        else
        {
            N = 3 * N + 1;
        }
    }

    fout << l;

    fin.close();
    fout.close();

    return 0;
}