La carrera de Collatz
Sea f la siguiente función, aplicable a cualquier número entero positivo:
- Si el número es par, se divide entre 2.
- Si el número es impar, se multiplica por 3 y se suma 1.
La carrera de Collatz consiste en, dada una lista de números ns, sustituir cada número n de ns por f(n) hasta que alguno sea igual a 1. Por ejemplo, la siguiente sucesión es una carrera de Collatz
|
1 2 3 4 5 6 7 8 |
[ 3, 6,20, 49, 73] [10, 3,10,148,220] [ 5,10, 5, 74,110] [16, 5,16, 37, 55] [ 8,16, 8,112,166] [ 4, 8, 4, 56, 83] [ 2, 4, 2, 28,250] [ 1, 2, 1, 14,125] |
En esta carrera, los ganadores son 3 y 20.
Definir la función
|
1 |
ganadores :: [Int] -> [Int] |
tal que (ganadores ns) es la lista de los ganadores de la carrera de Collatz a partir de la lista inicial ns. Por ejmplo,
|
1 |
ganadores [3,6,20,49,73] == [3,20] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
ganadores :: [Int] -> [Int] ganadores xs = selecciona xs (final xs) -- (final xs) es el estado final de la carrera de Collatz a partir de -- xs. Por ejemplo, -- final [3,6,20,49,73] == [1,2,1,14,125] final :: [Int] -> [Int] final xs | elem 1 xs = xs | otherwise = final [siguiente x | x <- xs] -- (siguiente x) es el siguiente de x en la carrera de Collatz. Por -- ejemplo, -- siguiente 3 == 10 -- siguiente 6 == 3 siguiente :: Int -> Int siguiente x | even x = x `div` 2 | otherwise = 3*x+1 -- (selecciona xs ys) es la lista de los elementos de xs cuyos tales que -- los elementos de ys en la misma posición son iguales a 1. Por ejemplo, -- selecciona [3,6,20,49,73] [1,2,1,14,125] == [3,20] selecciona :: [Int] -> [Int] -> [Int] selecciona xs ys = [x | (x,y) <- zip xs ys, y == 1] |