miércoles, 26 de noviembre de 2014

3n + 1 (uva 100)

Los problemas en informática se clasifican a menudo de acuerdo a un cierto tipo (p.e. irresolubles, recursivos, imposibles,...). En este problema analizareis una propiedad de un algoritmo cuya clasificación no es conocida para todas las posibles entradas.

El Problema:

Considera el siguiente algoritmo
1. input n

2. print n

3. if n = 1 then STOP

4. if n is odd then tex2html_wrap_inline44

5. else tex2html_wrap_inline46

6. GOTO 2


Dada como entrada el número 22, se imprimirían la siguiente secuencia de números 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Se supone que el algoritmo anterior terminará (cuando se imprime un uno) para cualquier valor entero. A pesar de la simplicidad del algoritmo, se desconoce si la suposición/conjetura es cierta. Ha sido verificada, sin embargo, para todos los enteros n tales que 0

Dada una entrada n, es posible detrerminar el número de números impresos (incluyendo al uno). Para un número n se le llama longitud de ciclo n. En el ejemplo superior, la longitud de ciclo de 22 es 16.
Para cualesquiera números i y j tienes que determinar la longitud de ciclo para todos los números entre i y j.


La entrada.

Consistirá en un par de enteros i y j, un par de enteros por línea. Todos los enteros menores que 1000000 y mayores que cero.

Debes procesar todos los pares de enteros y determinar el ciclo de longitud máxima comprendida entre esos dos valores incluyendo i y j.

Ppuedes asumir  que no habrá operaciones mayores que enteros de 32 bits.

La salida.

Para cada par de enteros i y j debes mostrar i, j y la máxima longitud de ciclo para los enteros comprendidos e incluyendo i y j. Estos tres números se mostrarán separados por un espacio, uno por  línea. Los enteros i y j deben aparecer en el mismo orden que aparecen en la entrada y deben ir seguidos de la longitud de ciclo máxima (en la misma línea.

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174



Explicación y solución: serverfault.com/questions/40156/puppet-force-service-restart-after-configuration-file-was-modified package pkg3nmas1;
import java.util.Scanner;

/**
*
* @author juan
*/
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    
        Scanner leer = new Scanner(System.in);
        int num1,num2,mayor,menor,maximo;
        while (leer.hasNextInt()) {
            num1=leer.nextInt();
            num2=leer.nextInt();
            menor=Math.min(num2, num1);
            mayor=Math.max(num2, num1);
        
            maximo=0;
            for (int i = menor; i <=mayor; i++) {
                maximo= Math.max(maximo, cuentaSaltos(i));
            }
            System.out.println(num1+ " " + num2 + " " + maximo);
        
        
        }
      


    

    }

    public static int sig(int n)
    {
        int retorno;
    
        if (n%2==0) retorno= n/2;
        else retorno = n*3 +1;
    
        return retorno;
    }

    public static int cuentaSaltos(int n)
    {
        int saltos;
        if (n==1) saltos=1;
        else saltos= 1 + cuentaSaltos(sig(n));
    
        return saltos;
    }

}
package solucion2;
import java.util.Scanner;

/**
*
* @author juan
*/
public class Solucion2 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
      
        Scanner leer = new Scanner(System.in);
      
        int num1,num2,mayor,menor,maximo;
        while (leer.hasNextInt()) {
            num1=leer.nextInt();
            num2=leer.nextInt();
            menor=Math.min(num2, num1);
            mayor=Math.max(num2, num1);
          
            maximo=0;
            for (int i = menor; i <=mayor; i++) {
                maximo= Math.max(maximo, cuentaSaltos(i));
            }
            System.out.println(num1+ " " + num2 + " " + maximo);
          
          
        }
    }
    public static int cuentaSaltos(int i){
        int retorno;
        int num,cont;
        num=i;
        cont=1;
        while (num!=1)
        {
            if (num%2==0) num=num/2;
                    else num = 3*num+1;
            ++cont;
        }
        return (cont);
    }
  
}

1 comentario:

Sandra Torres Une dijo...

Muy interesante el blog..Me sirvió mucho !