Problema 31:
Supongamos que en un imaginario lenguaje de computación sólo existe una sentencia de asignación y un operador de multiplicación. Escriba un programa que pueda adaptarse a ese lenguaje de manera que permita calcular b = an (indicamos as¡ a la n-ésima potencia de a) para cualquier entero positivo n (n < 100) y para un número entero a dado, utilizando la mínima cantidad de multiplicaciones. Por ejemplo, para n = 13, el texto central del programa (con comentarios entre paréntesis) podría ser el que sigue:
X1 = a ( = a)
X2 = X1*X1 ( = a2)
X3 = X2*X2 ( = a4)
X4 = X3*X1 ( = a5)
X5 = X3*X3 ( = a8)
X6 = X5*X4 ( = a13)
b = X6
basado en el hecho de que 13 = 1 + 4 + 8 (alguna idea?).
Problema 32:
Se tienen 24 bolitas numeradas de 1 a 24 y se sabe que todas tienen el mismo peso salvo una que es más pesada que las otras. Se cuenta además con una balanza antigua. Cada "pesada" consiste en colocar bolitas en cada uno de los platos de la balanza y fijarse, de acuerdo a la inclinación de la balanza, qué grupo de bolitas pesa más.
El problema es determinar cuál es la bolita que pesa más usando, a lo sumo, 3 veces la balanza.
Piense cómo hacerlo y escriba un programa que:
1- indique qué‚ bolitas deben ser puestas en cada plato de la balanza en la primera "pesada"
2- permita ingresar el código del plato que bajó más
3- proceda como en 1) y 2) para la segunda pesada
4- proceda como en 1) para la tercera pesada
5- dé el número de la bolita que pesa más.
Problema 33:
Piense en las modificaciones que debería hacerle al programa del problema anterior en el caso en que hubiesen 25 bolitas. Si quiere hacerlo en forma general, tenga en cuenta que para 28 bolitas no alcanza con 3 pesadas, necesitará 4. Considere también cuántas pesadas deberá hacer si sabe que las 24 bolitas del problema anterior pesan igual salvo una, no sabiendo si el peso de esta última es mayor o menor que el de las otras.
Problema 34: (Juego del "ahorcado")
Dos adolescentes, A y B, quieren jugar "al ahorcado" usando su computadora: el problema consiste en escribir un programa que les permita hacerlo.
El juego consiste en lo siguiente:
A escribe en el teclado una palabra de N letras (N <30). La palabra desaparece de la pantalla y B trata de encontrarla en, a lo sumo, K intentos.
Al principio, una sucesión de N guiones ("--...-") aparece en pantalla. Cada vez que B escribe una letra que figura en la palabra elegida por A, la letra aparece en pantalla en su lugar correcto reemplazando los correspondientes guiones. Cada vez que B escribe una letra equivocada, la letra aparece en pantalla junto con todas las letras equivocadas que haya ingresado B hasta ese momento.
Al cabo de cada intento, debe aparecer también en pantalla la cantidad de intentos hechos y las chances que aún le quedan a B. El juego termina si la palabra es encontrada o bien si se han hecho ya los K intentos permitidos. Para evitar la picardía de alguno de los jugadores es conveniente que el programa valide que A ha elegido una palabra usando sólo las letras que aparecen en el teclado (evitando, por ejemplo, los símbolos *, $, +, los números, el espacio en blanco) y que, al final del juego, muestre la palabra elegida por A, si es que B no ha logrado encontrarla .
Problema 35:
Escribir un programa de manera que si uno de los chicos no quiere seguir jugando al ahorcado, el otro pueda jugar "contra" la computadora. O sea, la computadora juega por el primer jugador y las jugadas del segundo jugador se siguen entrando desde el teclado. Hay que tener en cuenta que, en este caso, se presentan dos alternativas: o bien se admite como "palabra" cualquier secuencia de N letras obtenida al azar o bien se debe crear un archivo de palabras que pueda ser utilizado por la computadora.
Problema 36:
Escribir un programa que permita el ingreso de dos números enteros A (formado por N1 dígitos) y B (formado por N2 dígitos) y que luego emita en pantalla el resultado de la multiplicación de A por B. La dificultad radica en que el programa debe realizar la multiplicación de la misma manera en que lo hacemos "a mano".
Problema 37:
Un cuadrado mágico 3x3 consiste en una tabla 3x3 que tiene en cada posición un dígito (1, 2, 3, ..., 9), sin repetirse ninguno, y de forma tal que la suma de cada fila, cada diagonal y cada columna coinciden. Un ejemplo de un cuadrado mágico es el que sigue:
4 9 2 3 5 7 8 1 6
Figura 1
en este ejemplo, cada fila, cada columna y cada diagonal suman 15. Escriba una programa que permita el ingreso de un número impar M y que produzca un cuadrado mágico de MxM utilizando los primeros M2 números naturales. A modo de ayuda le hacemos notar lo siguiente:
Si ubicamos los 9 primeros números naturales en una tabla 5x5 de la siguiente manera:
1
4 2
7 5 3
8 6
9
y "marcamos" el cuadrado 3x3 centrado en ella, veremos que, ubicando de manera conveniente sólo los números que "caen" fuera de él, obtendremos el cuadrado mágico de la Figura 1.
Problema 38:
Para cada par de enteros positivos (m,n) podemos definir una función f de la siguiente manera:
f(m,n) = [(m+n-1).(m+n-2)/2] + n
Esta función tiene dos propiedades importantes, cuya validez demuestran los matemáticos:
1- Si f(m,n) = f(s,t) entonces m = s y n = t
2- Dado cualquier entero positivo k existen dos enteros positivos m y n tales que f(m,n) = k. Dicho en otras palabras, dado cualquier entero positivo k, existe un único par de enteros positivos (m,n) tal que f(m,n) = k. Por lo tanto, esta función permite demostrar el hecho sorprendente de que "hay tantos" elementos en NxN como en N. La demostración que hacen los matemáticos no es constructiva, es decir, prueba que existe el par (m,n) pero no "muestra" el par ni dice cómo calcularlo. Sin embargo, si se hace una tabla de los valores de f para m + n < 7:
m 1 2 3 4 5
n
1 1 2 4 7 11
2 3 5 8 12
3 6 9 13
4 10 14
5 15
veremos que lo que hace f es "numerar" los elementos de una matriz. Se trata entonces de escribir un programa que:
1- permita el ingreso de un par (m,n) y calcule f(m,n), emitiendo en pantalla un mensaje adecuado.
2- permita el ingreso de un entero positivo k y determine el par (m,n) tal que f(m,n) = k, emitiendo en pantalla el resultado.
Problema 39:
El rey blanco y 8 peones negros se encuentran ubicados en un tablero de ajedrez (8 casilleros de largo por 8 casilleros de ancho). El rey y cada uno de los peones pueden "comerse" entre sí. El rey puede moverse de acuerdo a las reglas usuales del ajedrez, esto es, un casillero por vez, en cualquier dirección. Sin embargo, los peones no pueden moverse salvo para "comer" al rey; para ello, el rey debe ubicarse en cualquiera de los casilleros diagonales adyacentes al que ocupa el peón. Diremos que una "ruta" para el rey es SEGURA si el rey puede recorrerla sin ser "comido" por ninguno de los 8 peones. Se trata entonces de encontrar un algoritmo que permita determinar si existe o no una ruta segura para el rey desde el casillero A1 al H8 para una posición dada de los 8 peones negros.
Escribir un programa que:
A- permita la entrada de las posiciones de los 8 peones negros.
B- determine si existe o no una ruta segura para el rey, con respecto a la posición ingresada de los 8 peones negros, desde el casillero A1 al H8.
C- si tal ruta existe, la describa.
Problema 40 (Juego de la Vida):
Consideremos un asentamiento de K insectos en una tabla MxN (insectos geométricos, demás está decir), de modo que en cada celda de la tabla hay, a lo sumo, un insecto. Por lo tanto, cada insecto tiene, como máximo, 8 vecinos. El asentamiento se está desarrollando continuamente debido a los nacimientos y defunciones que se producen. Las reglas de evolución que se observan son las siguientes:
1- Aquellos insectos que tienen 0, 1, 4, 5, 6, 7 ú 8 vecinos mueren indefectiblemente.
2- Los insectos que tienen 2 ó 3 vecinos sobreviven.
3- En cada celda vacía en cuya vecindad hay exactamente tres insectos, nace un nuevo insecto.
4- Los insectos que nacen o mueren no afectan las reglas hasta que se ha completado un ciclo evolutivo, entendiendo por éste un ciclo en el que se ha decidido la sobrevida o muerte de los insectos (vivos al comenzar el ciclo) de acuerdo a las reglas mencionadas.
Escriba un programa que modele la evolución del asentamiento y que:
a) Permita ingresar los enteros positivos N, M y K y las coordenadas de las celdas en las que se encuentran los K insectos del asentamiento.
b) Muestre en pantalla el estado inicial del asentamiento, marcando con un asterisco (*) las celdas ocupadas por insectos.
c) Permita ingresar un entero positivo L.
d) Determine cómo estará el asentamiento luego de L ciclos evolutivos y emita en pantalla el estado del asentamiento en ese momento representándolo como en b).
Ejemplo: M = N = 6, K = 5, L = 1
ESTADO INICIAL
* *
* *
*
ESTADO FINAL
* * *
*
* *