En esta serie de apuntes voy a estar revisando algunos acertijos de programación.
Hoy voy a revisar aquel que se conoce, entre otros nombres, por “el problema de la suma de dos números enteros”. Se lo puede encontras en otros casos por “problemas de las dos sumas”.
El plan de esta entrada es el de poder hacer varias cosas al mismo tiempo.
Por un lado escribir esto me da una excusa para poder seguir aprendiendo programación. Y por otra parte tengo la oportunidad de crear nuevo material para el blog.
Recuerden que yo no soy un experto en nada de esto, solamente soy una persona a la que le gusta intentar aprender enseñando.
Versión 1 del problema de las dos sumas:
El acertijo con el que estamos trabajando dice lo siguiente:
Dado un array de integers llamado:
array_cifras = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15]
Y un integer “x”:
“x=8”
Necesitamos primero crear una función booleana que compruebe si existen en “array_cifras” dos elementos que sumados den por resultado el integer “x”.
Los materiales
Tenemos en el problema una colección de números.
De entre todos esos números de la colección necesitamos averiguar si es cierto que al menos dos de ellos sumados dan por resultado el valor de “x”.
Sabemos que para trabajar tenemos lo siguiente:
– Array:
Los array se utilizan para guardar datos de algún tipo. No es exactamente una lista, aunque en un primer momento se parece a una.
Entre otras diferencias, una lista puede tener elementos de distintas clases mientras que un array solamente puede contener elementos de una misma clase. Aunque supongo que este concepto puede variar entre lenguajes de programación, nos alcanza saber que nuestro array tiene solamente integers.
Otro detalle importante es saber que se pueden acceder a los elementos del array por medio del índice.
Por ejemplo, en Python un array como el nuestro aparece de la siguiente forma:
array_cifras = [1, 2, 3, 4, 5]
Pero por otra parte, un array en Bash aparece de esta otra forma:
array_cifras=(1 2 3 4 5)
O también puede aparecer de la siguiente forma:
declare -a array_cifras=(“1” “2” “3” “4” “5”)
En este caso necesitamos usar primero el comando “declare” junto con la opción “-a” para señalar que la variable se trata de un array, al que podemos agregarle otras opciones también.
En resumen: los detalles entre lenguajes pueden variar en los detalles para escribir la respuesta, pero el concepto es más o menos siempre el mismo.
– Integer:
En programación es un tipo de datos que representa números enteros. Positivos, negativos, cero; cualquier número que no tengas decimales.
Para resolver el problema, tenemos que encontrar si existen o no dos números enteros en el array que sumados den por resultado el número dentro de la variable “x”.
Para simplificar la lectura del problema podemos cambiarle el nombre a esta variable, pasando de:
x=8
a uno más descriptivo, por ejemplo:
resultado=8
No necesitamos mostrar cuales dos son esos números de la suma, solamente decir si existen o no dentro del conjunto.
– Boolean function:
se trata de una función booleana.
Es una función que regresa un valor de “verdadero” o “falso”.
Para poder entender este tipo de funciones vamos a necesitar tener presente el tema de conectores lógicos dentro de programación.
Resolución en Python:
Por búsqueda exhaustiva:
Hay varias formas de resolver este problema. La siguiente forma es por “búsqueda exhaustiva”, porque revisa todos los números en el array.
Digamos que el número que tenemos que constatar como resultado de la suma es:
resultado = 8
Y el array es:
array_cifras = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15]
Realmente no importa conocer el orden de los números, porque ahora vamos a revisarlos todos.
Pero sabemos que tenemos que descartar del array cualquier número igual o superior a 8, ya que ninguna cifra sumada a un número superior a 8 va a dar por resultado 8.
E incluimos al ocho en la búsqueda porque ese número sumado al cero tambien responde la pregunta como verdadera.
Eso lo hacemos en la primera parte de la función.
Esto vuelve el programa un poco más compleja, tiene que hacer dos pasadas en lugar de una. Pero creo que también lo vuelve más interesante para aprender otras cosas.
Luego continuamos probando sumar cada número del array con todos los demás para ver que combinación resulta en “x”. Pero directamente dentro del nuevo array que solo tiene las cifras que cumplen la condición de ser menores al resultado.
El código terminado es el siguiente:
# ver 0.1 programa de Python para saber si es verdadero o falso si dos números del array suman el resultado
def revisar_array(array_cifras, resultado):
cifras_posibles = [] # nuevo array para guardar las cifras posibles.
for num in array_cifras:
if num <= resultado: #buscamos las posibles cifras que cumplenla condición.
cifras_posibles.append(num) #guardamos lo encontrado en el nuevo array.
for i in range(len(cifras_posibles)):
for j in range(i+1, len(cifras_posibles)): # sumar cada num. con el siguiente.
if cifras_posibles[i] + cifras_posibles[j] == resultado:
print ("los posibles números que comprueban la suma: ", cifras_posibles)
return True
return False # si la suma no es posible, regresa False
array_cifras = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15]
resultado = 8
cifras_posibles = revisar_array(array_cifras, resultado)
print(cifras_posibles) Ejecutar este código nos tiene que regresar lo siguiente:
los posibles números que comprueban la suma: [1, 2, 3, 4, 5, 6, 7, 8] True
Esto nos dice dos cosas.
Primero nos dice que existen en el array algunos valores mejores e iguales que a 8, que al sumarlos pueden llevarnos al resultado.
Y luego nos dice que es True (verdadero) que la suma de dos de estos dos números da por respuesta ocho. Pero solamente estamos resolviendo la función boleana, que no da un si o no por respuesta. No conocemos todavía los dos valores que resuelven el problema de la suma en el array.
¿Cuáles son esos números? Para conocer eso vamos a necesitar una versión del código mejorada:
# ver 0.2 programa de Python para saber si dos números de un array suman igual valor pedido
array_cifras = array_cifras = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15]
resultado = 8
def revisar_array(array_cifras, resultado):
cifras_posibles = [] # nuevo array para guardar las cifras posibles.
for num in array_cifras:
if num <= resultado: #buscamos cifras menores o iguales al resultado.
cifras_posibles.append(num) # guardamos lo encontrado en el nuevo array.
print(cifras_posibles)
posicion_i = None # variable para guardar índice de i
posicion_j = None # variable para guardar índice de j
for i in range(len(cifras_posibles)):
for j in range(i+1, len(cifras_posibles)): # sumar cada num. con el siguiente.
if cifras_posibles[i] + cifras_posibles[j] == resultado:
posicion_i = i # índice i
posicion_j = j # índice j
print("De esa lista los números que sumados dan", resultado, "son ", cifras_posibles[i], "y", cifras_posibles[j])
print("El par de índices corresponde a: ", [posicion_i, posicion_j])
return True
return False # si la suma no es posible, regresa False
respuesta = revisar_array(array_cifras, resultado)Y al ejecutarlo vamos a tener por respuesta:
[1, 2, 3, 4, 5, 6, 7, 8] De esa lista los números que sumados dan 8 son 1 y 7 El par de índices corresponde a: [0, 6]
Ahora podemos saber cuáles son los dos primeros números que sumados dan 8, esto es el 1 y el 7.
Pero además podemos saber el índice que ocupan los dos valores seleccionados dentro del array. Recordemos que el index comienza asignándole el número 0 al primer valor. Es por eso que en este caso como el array se encuentra ordenado de menor a mayor, el número 1 tiene un índice de 0 y el número 7 un índice de 6.
Los detalles importantes del caso:
De todo ese código creo que hay dos fragmentos a las que tenemos que prestarles particular atención.
Sabemos que tenemos un array:
array_cifras = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15]
Lo primero es:
cifras_posibles = [] # nuevo array para guardar las cifras posibles.
for num in array_cifras:
if num <= resultado: #buscamos cifras menores o iguales
cifras_posibles.append(num) # guardamos lo encontrado
print(cifras_posibles)Estamos utilizando un “for” loop, un bucle que revisa cada uno de los elementos de “array_cifras” y si cumplen la condición pedida los agrega al nuevo array “cifas posibles”.
Entonces podemos intuir que el programa decide:
Para el elemento 1 en array_cifras ¿Es este elemento entero menor o igual a 8? Verdadero Agregar 1 al cifras_posibles Para el elemento 2 en array_cifras ¿Es este elemento entero menor o igual a 8? Verdadero Agregar 2 a cifras_posibles … Para el elemento 15 en array_cifras ¿Es este número enteror menor o igual a 8? Falso No agregar 15 a cifras_posibles
Y cada elemento es revisado de esa forma.
Lo mismo ocurre en este otro fragmento del código:
for i in range(len(cifras_posibles)):
for j in range(i+1, len(cifras_posibles)):
if cifras_posibles[i] + cifras_posibles[j] == resultado:
return True Una vez más estamos trabajando con un “for loop”. En toda la extensión del array el programa prueba sumar un número con todos los que le siguen.
Es por eso que aunque existe otra respuesta correcta para nuestro problema en “2 + 6 = 8” el programa nunca llega a comprobarla. Se detiene en cuanto llega a “1 + 7 = 8” porque ese es el punto en el que le pido que se detenga.
Para encontrar todas las sumas, podemos cambiar ese bloque de código de esta forma:
sumas = []
for i in range(len(cifras_posibles)):
for j in range(i+1, len(cifras_posibles)):
if cifras_posibles[i] + cifras_posibles[j] == resultado:
sumas.append((cifras_posibles[i], cifras_posibles[j]))
if not sumas:
return False
else:
print(f"De esa lista los números que sumados dan {resultado} son: ")
for x, y in sumas:
print(f"\t{x} + {y}")
return TrueLo que puesto en conjunto con el resto del programa va a darnos por resultado:
[1, 2, 3, 4, 5, 6, 7, 8]
De esa lista los números que sumados dan 8 son:
1 + 7
2 + 6
3 + 5
En esta oportunidad estamos sumando cada número de “cifras_posibles” con el que le sigue, y guardamos cada coincidencia en el array “sumas”.
Al terminar el código podemos encontrar todas las operaciones dentro del array que nos llevan al resultado 8.
Por búsqueda exhaustiva en Bash:
La solución en este otro lenguaje es similar al anterior.
Revisamos exhaustivamente cada elemento en el array con todos los demás, hasta encontrar el par de números que resulten en “x”.
La solución es la siguiente:
#!/bin/bash
# programa para saber si es verdadero o falso si dos números del array suman el resultado
# El array para revisar
array_cifras=(1 2 3 4 5 6 7 8 9 10 14 15)
# la variable con la cifra de resultado
resultado=8
function revisar_array {
local cifras_posibles=() # armamos un array local para guardar los valores menores o iguales al resultado
for (( i=0; i<${#array_cifras[@]}; i++ )); do
if [ ${array_cifras[i]} -le $resultado ]; then
cifras_posibles+=(${array_cifras[i]}) # actualizamos el array local
fi
done
echo "Números que pueden dar la posible respuesta: ${cifras_posibles[@]}" # imprimimos los elementos válidos para comprobar nuestra suma
declare -A sumas=( )
# Comprobamos sumar cada valor con el que le sigue para probar si existen dos números que llevan al resultado
for (( i=0; i<${#cifras_posibles[@]}; i++ )); do
for (( j=i+1; j<${#cifras_posibles[@]}; j++ )); do
if (( ${cifras_posibles[$i]} + ${cifras_posibles[$j]} == resultado )); then
key="${cifras_posibles[$i]}+${cifras_posibles[$j]}" # formato del par de coincidencias.
sumas["$key"]="$i,$j" # guardar coincidencias en el array
fi
done
done
if [ ${#sumas[@]} -gt 0 ]; then
for key in "${!sumas[@]}"; do
indices=${sumas[$key]}
echo "El par que suma $resultado es: $key (posiciones: $indices)"
done
else
echo "False"
exit 1
fi
}
revisar_array
Lo que nos va a dar por respuesta:
Números que pueden dar la posible respuesta: 1 2 3 4 5 6 7 8 El par que suma 8 es: 3+5 (posiciones: 2,4) El par que suma 8 es: 1+7 (posiciones: 0,6) El par que suma 8 es: 2+6 (posiciones: 1,5)
Versión 2 del problema:
Esta es otra ligera variante del problema.
En este caso tenemos un array desordenado, por ejemplo:
array_cifras = [1, 4, 3, 2, -6, 5, 10, 8, 9, 7, 14, 15]
Y ahora necesitamos encontrar directamente todos los casos donde dos cifras suman:
resultado = 8
Encontrando en cada caso la posición de la cifra en el array.
Nueva resolución del problema en Python
Esta es otra opción para resolver el problema, pero esta vez sin necesidad de realizar operaciones entre todos los números del array.
# ver 2 programa de Python para saber si dos números de un array suman igual valor pedido
array_cifras = [1, 4, 3, 2, -6, 5, 10, 8, 9, 7, 14, 15]
resultado = 8
# Función para mostrar si dos números sumados llegan al resultado
def revisar_array(array_cifras, resultado):
num_set = set() # valores revisados
valores = [] # índices de los valores sumados
for i, cifra in enumerate(array_cifras):
# calcular la diferencia entre el resultado y el número actual
diferencia = resultado - cifra
# Si la diferencia fue encontrada antes, existe que hay dos valores que juntos dan el resultado
if diferencia in num_set:
valores.append((array_cifras.index(diferencia), i))
num_set.add(cifra)
return valores
valores = revisar_array(array_cifras, resultado)
# Función para mostrar los índices de los valores
def expresar():
print(valores)
for par in valores:
index1, index2 = par
print(f"Los valores de los índices {index1} y {index2} son: {array_cifras[index1]} | {array_cifras[index2]}")
expresar()Y al ejecutar el código obtenemos:
[(2, 5), (0, 9), (4, 10)] Los valores de los índices 2 y 5 son: 3 | 5 Los valores de los índices 0 y 9 son: 1 | 7 Los valores de los índices 4 y 10 son: -6 | 14
Creo que loo más importante que necesitamos saber ahora es que esta vez no estamos probando realizar operaciones cruzando todos los números.
Por el contrario, esta vez esta probamos restar cada cifra contra el resultado.
Por ejemplo, una diferencia es:
8 - 3 = 5 Agregar 3 a num_set
Luego contina por ejemplo:
8 - 2 = 6 Revisar si 6 aparece en num_set: todavía no. Agregar 2 a num_set.
Y sigue:
8 - 5 = 3 Revisar si 3 aparece en num_set: si aparece. Agregar 5 a num_set y emparejarlo con 3 en valores
De esta forma el programa revisa si unnúmero ya fue comprobado, y en el momento que encuentra dos restos los empareja dentro del nuevo array “valores”.
Es una forma un poco más compleja de entender que la primera versión, pero es más simple en tanto que no tiene que cruzar cada número con todos los demás como en el caso anterior.
Otra forma de resolver el problema en Bash
La nueva alternativa en Bash puede presentarse de esta forma:
#!/bin/bash
# ver 2 programa de Python para saber si dos números de un array suman igual valor pedido
revisar_array() {
local array_cifras=("${!1}")
local resultado=$2
declare -A encontrados
for i in "${!array_cifras[@]}"; do
num=${array_cifras[i]}
complement=$((resultado - num))
if [[ ${encontrados[$complement]} ]]; then
echo "Un par de índices que responde al problema ${encontrados[$complement]} y $i esto es: ${array_cifras[${encontrados[$complement]}]} + $num = $resultado"
fi
encontrados[$num]=$i
done
}
main() {
array_cifras=(1 4 3 2 -6 5 10 8 9 7 14 15)
resultado=8
revisar_array array_cifras[@] $resultado
}
mainY al ejecutarlo nos devuelve:
Un par de índices que responde al problema 2 y 5 esto es: 3 + 5 = 8 Un par de índices que responde al problema 0 y 9 esto es: 1 + 7 = 8 Un par de índices que responde al problema 4 y 10 esto es: -6 + 14 = 8
En este caso también evitamos sumar todos los números entre si, usando una aproximación alternativa.
Conclusión
Con esto llegamos al final del texto sobre cómo resolver el problema de la suma de dos números enteros con distintos lenguajes de programación.
Cualquier error que encuentres en el material, por favor avisame para que pueda corregirlo.
La seguimos en el próximo apunte.
Leave a Reply