El problema 3n + 1
Trasfondo
Los problemas en ciencias computacionales son siempre
clasificados según pertenezcan a ciertas clases de problemas (por ejemplo, NP,
Irresolvibles, Recursivos). En este problema tendrás que analizar las
propiedades de un algoritmo cuya clasificación no es conocida por todas las
posibles entradas.
El Problema
Considerando el siguiente algoritmo:
1.
Entrada n
2.
Imprime n
3.
Si n = 1 entonces PARA
4.
Si n es impar entonces n ß 3n + 1
5.
Si no n ß
n/2
6.
Volver al paso 2
Dada la entrada 22, se imprimirá por pantalla la siguiente
secuencia de números; 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Se conjetura que el algoritmo anterior terminará (cuando un
1 sea impreso por pantalla) por cualquier entrada de valor entero. Este
algoritmo se verifica, sin embargo, por todos los enteros n que estén comprendidos entre 0 < n < 1.000.000 (y, en
efecto, por muchos más números.)
Dada una entrada n,
es posible determinar el número de números que serán impresos por pantalla
(incluyendo el 1). Para el número dado n este
proceso es llamado el ciclo-de-la-extensión
de n. En el ejemplo anterior, el
ciclo de la extensión de 22 es 16.
Para cualquiera de dos números i y j se determinará el ciclo
de la extensión máximo de los números comprendidos entre i y j.
La Entrada
La entrada constará de una serie de parejas de enteros i y
j, una pareja de enteros por línea. Todos los enteros serán inferiores a
1.000.000 y mayores que 0.
Debes procesar todas las parejas de enteros y por cada
pareja determinarás el ciclo de la extensión máximo para todos los enteros
comprendidos entre i y j, ambos incluidos.
Puedes asumir que ninguna operación va a superar a un entero
de 32 bits.
La Salida
Por cada pareja de enteros i y j debes mostrar la salida i,
j, y el ciclo de la extensión máximo para los enteros comprendidos e incluyendo
i y j. Estos tres números deben estar separados por al menos un espacio y aparecer
en una sola línea para cada salida. Los enteros i y j deben aparecer en la
salida en el mismo orden en el cual aparecían en la entrada y deben ser
seguidos por el ciclo de extensión máximo (en la misma línea).
Ejemplo de Entrada
1 10
100 200
201 210
900 1000
Ejemplo de Salida
1 10 20
100 200 125
201 210 89
900 1000 174
No hay comentarios:
Publicar un comentario