Problema 51:
En el lenguaje de los aborígenes de la isla Makana hay exactamente N palabras (20 < N < 1000). Para escribir sus textos, los makanos, emplean sólo letras mayúsculas del alfabeto latino (excluyendo la Ñ). Los textos makanos están compuestos por oraciones terminadas siempre con un punto. Las palabras aparecen separadas por un espacio en blanco. Puede haber comas en las oraciones. Los únicos signos de puntuación que usan, la coma y el punto, se deben colocar directamente después de una palabra y son separados del texto que sigue por un espacio en blanco, por lo menos. La palabra más larga del leguaje makano es ABRACADABRA, de 11 letras. Todas las palabras del lenguaje makano figuran, correctamente escritas, en orden alfabético, en una lista que llaman Glosario. Puesto que los makanos tienen muchos errores de ortografía, es necesario que cuenten con un "corrector" de sus textos. Para ello, escriba un programa que:
1-permita el ingreso del entero positivo N y de las palabras del Glosario, suponiendo que el que las carga lo hace en orden alfabético en un vector de la forma:
[A1,A2, ... , AN]
En este vector cada Ai (1 < i < N ) es una palabra makana de no más de 11 letras.
2- permita el ingreso de un texto makano de, a lo sumo, 60 caracteres.
3- determine si los caracteres ingresados son los permitidos, esto es, letras mayúsculas, blancos, comas y puntos. En caso de que figuren caracteres no permitidos debe emitirse un mensaje solicitando que se ingrese nuevamente el texto.
4- determine si las palabras que aparecen en el texto tienen longitud permitida y, en caso de que exista una palabra de más de 11 letras, solicite que se ingrese nuevamente el texto.
5- determine si las palabras que aparecen en el texto están o no en el Glosario, emitiendo un mensaje de error cuando haya alguna palabra que no figura en él.
6- para el caso en que el texto ingresado no contenga signos de puntuación (salvo el punto final), emita otro idéntico con la sola salvedad de que las palabras mal escritas (o sea, aquéllas que no figuran en el Glosario) aparezcan entre asteriscos (*).
Ejemplo: Texto ingresado:
ABBA RANDO BEBEAS ARGENTINA.
Suponiendo que las palabras ABBA BEBEAS y ARGENTINA figuran en el Glosario pero que RANDO no figura, el texto de "salida" debe ser:
ABBA *RANDO* BEBEAS ARGENTINA.
7- para el caso de cualquier texto, emita otro similar al ingresado con las palabras mal escritas (o sea, aquéllas que no figuran en el Glosario) entre asteriscos (*) y las posiciones de los signos de puntuación (comas o puntos) corregidas de acuerdo a lo que hemos especificado.
Ejemplo: Texto ingresado:
ABBA RANDO BEBEAS ,ARGENTINA.
Suponiendo que las palabras ABBA BEBEAS y ARGENTINA figuran en el Glosario pero que RANDO no figura, el texto de "salida" debe ser:
ABBA *RANDO* BEBEAS, ARGENTINA.
Problema 52:
Considere el problema anterior en el caso en que el Glosario es un archivo que se carga por única vez con una cantidad de palabras fija que no es modificada por el programa, o sea, debe trabajarse con un archivo separado y se debe obviar la carga de N y del vector [A1,A2, ... , AN].
Problema 53:
N nodos numerados de 1 a N (0 < N < 50) están conectados por una red de vías de comunicación cada una de las cuales tiene longitud 1. Estas vías corren a diferentes alturas entre nodo y nodo de manera que sólo se intersecan en los nodos. En el momento inicial 0 se encuentran M robots (M = 2 ó M = 3) en algunos de los nodos. Los robots se mueven continuamente de un nodo a otro a una velocidad constante en forma independiente uno de otro. Sólo pueden cambiar su dirección en los nodos y no se les permite que se detengan. La velocidad del i-ésimo robot es vel[i] donde vel[i] = 1 o bien vel[i] = 2. Los robots deben ser controlados de manera tal de minimizar el tiempo que se necesitará para que se encuentren todos en un mismo nodo. Se debe entonces escribir un programa que permita:
1.- Ingresar:
- el número N de nodos y el número M de robots.
- el número K de vías.
- el recorrido de cada una de las vías.
- el número de robots (2 ó 3)
- la velocidad vel[i] (1 ó 2) de cada uno de los robots.
- la posición inicial de cada uno de los robots, o sea, el nodo en que se encuentran en el momento 0.
2.- Determinar el mínimo tiempo T necesario para que ocurra el encuentro de todos los robots en el mismo nodo o bien indicar que tal encuentro no puede producirse en ningún instante t > 0.
Problema 54:
Un ÁRBOL es un grupo de nodos todos conectados mediante arcos. Uno de estos nodos es llamado RAÍZ y los arcos pueden iniciarse pero no terminar en él. De cada nodo pueden "salir" 0, 1 o más arcos. Sólo un arco puede terminar en cada nodo (exceptuando al RAÍZ). Si de un nodo A salen arcos que lo conectan directamente con los nodos B y C se dice que A es el "padre" de B y C y, respectivamente, que B y C son los "hijos" de A. El "grado" de un nodo está dado por la cantidad de "hijos" que tiene. El "grado" del árbol es el mayor grado de los nodos que lo componen. Se dice que un árbol es binario cuando su grado es 2. En la Figura 1 damos un ejemplo de un árbol binario:
Figura 1 Figura 2
A G
B G A
C D B
E F C D
E F
En la Figura 2 aparece el mismo árbol de la Figura 1 sólo que hemos cambiado la forma de representarlo. Hay varias maneras de "almacenar" un árbol binario en la memoria de la computadora. Una de ellas es la siguiente:
Se usan tres vectores: en el primero se "guardan" los nombres asignados a los nodos; en el segundo, respetando el orden dado en el primer vector, se guardan la posición en el primer vector de los "hijos de la izquierda" de cada nodo (poniendo 0 si no tienen hijos, cuando el lenguaje que empleemos numere las posiciones de un vector a partir de 1) y en el tercer vector la posición de los "hijos de la derecha". De acuerdo a esto una forma de almacenar los nodos de la Figura 1 es:
V2 V1 V3
2 A 7
3 B 4
0 C 0
5 D 6
0 E 0
0 F 0
0 G 0
Una "travesía" de un árbol es un proceso durante el cual todos los nodos son visitados exactamente una vez. Pueden haber travesías distintas para un mismo árbol; en el caso de un árbol binario, una de ellas consiste en visitar primero al "padre" y luego a sus descendientes por izquierda y recién entonces emprenderla con los que están por derecha. Este tipo de travesía en el árbol representado en la Figura 1 sería:
A B C D E F G
y en la Figura 2:
G A B C D E F
Escriba un programa que modele una travesía de un árbol binario dado:
1- permitiendo, a través del teclado, el ingreso:- de la cantidad de nodos que deben ser considerados
- el nombre de cada uno de ellos
- los hijos por izquierda
- los hijos por derecha
2- determinando una travesía para el árbol dado
3- mostrando en pantalla el orden en que los nodos deben ser visitados.
Problema 55:
Supongamos que N hombres y N mujeres (0 < N < 10) han expresado sus deseos para formar pareja dando una lista ordenada de acuerdo a sus preferencias de las N personas del sexo opuesto. Consideremos un ejemplo en el que N = 5:
A B C D E 1 2 3 4 5
2 1 2 1 5 E D A C D
5 2 3 3 3 A E D B B
1 3 5 2 2 D B B D C
3 4 4 4 1 B A C A E
4 5 1 5 4 C C E E A
(Hemos asignado letras a las mujeres y números a los hombres para proteger el anonimato de las personas intervinientes)
Es claro que estas preferencias ofrecen varios conflictos: A y C prefieren a 2 y nadie parece querer mucho a 4. El problema consiste en determinar N matrimonios que respeten lo mejor posible las preferencias de todos y casarlos a todos en una gran ceremonia.
Para ello, diremos que una asignación de matrimonios es "inestable" si dos personas se prefieren entre sí antes que a sus respectivos esposos. Por ejemplo, de acuerdo a las listas dadas antes, la asignación:
A-1 B-3 C-2 D-4 E-5
es inestable pues A prefiere a 2 antes que a 1 y 2 prefiere a A antes que a C (en este estado de cosas, A y 2 podrían divorciarse de sus respectivos cónyuges y decidir formar pareja entre ellos). Lo que se pide entonces es encontrar una asignación de parejas que sea estable (encontrar todas las asignaciones estables es un problema bastante más difícil). Para ello, debe Ud. escribir un programa que:
1) permita la entrada desde el teclado del número natural N, y de las listas de preferencias de los N hombres y de las N mujeres.
2) determine una asignación de parejas que sea estable con respecto a las listas de preferencias ingresadas, mostrando en pantalla la asignación hallada. A modo de ayuda, les avisamos que dar una asignación arbitraria y luego tratar de "rearmar" las parejas inestables puede ser un proceso que nunca termine. Sugerimos entonces que se trate de encontrar un algoritmo que elija sistemáticamente asignaciones estables. Cuando haya resuelto el problema, estudie quiénes salen más favorecidos por su asignación: los hombres o las mujeres.
Problema 56:
Para el problema anterior, se trata ahora de elaborar un algoritmo y el correspondiente programa que permita determinar si una asignación dada es o no estable respecto de las listas de preferencias ingresadas. El programa debe:
1) permitir la entrada desde el teclado del numero natural N, y de las listas de preferencias de los N hombres y de las N mujeres y, luego, la asignación que debe ser analizada.
2) determinar si la asignación de parejas dada es o no estable con respecto a las listas de preferencias ingresadas, mostrando en pantalla un mensaje adecuado.
Problema 57:
Un equipo electrónico consta de un visor y dos únicos botones señalados con "1" y "2".Al encender el equipo aparece 0 en el visor.Si se oprime el botón 1 el número que está en la pantalla aumenta en 1, mientras que si se oprime el botón 2, el número se duplica.Escribir un programa que:
a) permita ingresar un número natural N.
b) muestre la cantidad de veces que deberá apretarse el botón 1 y la cantidad de veces que deberá apretarse el botón 2 para obtener, en la menor cantidad posible de pasos, el número N en el visor.
c) indique la manera en que deberán apretarse los botones.
Por ejemplo: Si N = 25
Se deberá apretar el botón 1: "3 veces"
Se deberá apretar el botón 2: "4 veces"
Los botones deberán apretarse en el siguiente orden: "1-2-1-2-2-2-1"
Problema 58:
Un polígono es una lista de puntos donde suponemos que dos puntos sucesivos están conectados mediante un segmento recto y, además, que el primer punto está conectado al último de manera de hacer una figura "cerrada". Un problema de enunciación simple consiste en: Dado un polígono cualquiera y un punto P en el plano, decidir si P es o no interior al polígono.
Escribir un programa que permita:
- el ingreso de un número positivo N (N > 2)
- el ingreso de las coordenadas de los vértices del polígono (respetando el orden en que deben ser recorridos)
- el ingreso de las coordenadas de un punto P
- determinar si P es o no interior al polígono, emitiendo en pantalla la respuesta.
Problema 59:
Decimos que un polígono es simple si no se "corta" a sí mismo. Escribir un programa que permita decidir si un polígono dado es o no simple.
Problema 60:
Durante la aproximación de un módulo espacial a un laboratorio espacial se hicieron mediciones sobre la distancia entre los dos aparatos. Los valores de estas distancias fueron d1, d2, ..., dn en los momentos t1, t2, ..., tn respectivamente. Debido a las técnicas de medición que se emplearon, se sabe que la diferencia entre la distancia medida y la real es menor que un número positivo r dado. Se sabe, además, que los parámetros orbitales son tales que la distancia entre los aparatos depende linealmente del tiempo. Es necesario entonces dar un algoritmo (y el correspondiente programa) que permita estimar lo mejor posible la distancia entre el módulo y el laboratorio espacial en cualquier instante.