Autor Tema: Re: Los gatos en el sombrero (Leído 12505 veces)

JuanK · « **en:** Miércoles 27 de Agosto de 2003, 17:52 »

Es broma,
realmente ya lo hice y no es ninguna tarea.

Hace algun tiemponuestrop amigo JoseD nos dejo algunos ejercios, pues bien me gustaria que los retomaramos poco a poco, y este me parecio bastanta bueno, espero que se animen a resolverlo.

LOS GATOS CON SOMBRERO

Tenemos un gato que usa un sombrero.
Dentro del sombrero del gato hay un grupo de gatos (más pequeños) que también usan sombrero, y que también tienen mas gatos (más pequeños aun) con sombrero dentro del suyo.

Solo los gatos más pequeños no tienen otros gatos dentro de su sombrero.

Ahora, sucede que nuestro gato camina por una habitación desarreglada que necesita limpiar. Como él no quiere hacer el trabajo, decide utilizar los gatos (más pequeños) dentro de su sombrero para que hagan el trabajo por él. Cada uno de estos gatos ayudantes tiene su propio sombrero, por lo que prefieren no trabajar, y usar los gatos (más pequeños) que tienen dentro de sus respectivos sombreros; y así sucesivamente.

Eventualmente los gatos alcanzan el tamaño más pequeño. Estos gatos, los más pequeños, no tienen gatos adicionales en su sombrero, y por eso les toca hacer la limpieza.

El número de gatos dentro de cada sombrero (excepto el de los más pequeños) es una constante, N.
La altura de los gatos dentro de un sombrero es 1/(N + 1) veces la altura del gato dueño del sombrero en el que ellos están.

Los más pequeños gatos tienen altura de 1, y son los que hacen todo el trabajo.

Todas las alturas son enteros positivos.

Dada la altura de nuestro gato y el número de gatos que finalmente hacen la limpieza (gatos de altura uno), realice un programa que calcule el número de gatos que no hacen nada del trabajo (gatos de altura mayor que uno) y también determine la suma de todas las alturas de los gatos (la altura que forman todos los gatos montados uno sobre otro).

DATOS DE ENTRADA: “gato.in”

La entrada consta de una secuencia de especificaciones de gato-en-el-sombrero.
Cada especificación se encuentra en una línea que consta de dos enteros positivos separados por un espacio en blanco.
El primer entero es la altura de nuestro gato, y el segundo entero es el número de gatos que trabajan.
El archivo termina con #.

DATOS DE SALIDA: “gato.out”
Para cada línea del archivo de entrada (especificación de gato-en-el-sombrero), se deberá imprimir dos enteros positivos.
El primero indicando el número de gatos que no trabajan, y el segundo determina la altura que forman todos los gatos uno sobre otro.
Deberá haber una línea de salida por cada línea de entrada.
EJEMPLO:
Lo coloque dentro de el tag de codigo solo para que puedan ver bien el formato.

Código: Text

 
archivo “gato.in”
16 9
216 125
#
---------
archivo  "gato.out”
4 37
31 671
 
 

A N I M E N S E
Hay que saber aprovechar este foro!!!...
si tienen dudas con el ejercicio me avisan y miro a ver en que les puedo ayudar.

La solucion la publicare en unas semanas o meses, segun como se desarrolle este post....

Juank:hippi:

essios

wenas, empece a trabajar con este reto. de momento he desarrollado un programa en el que se inserta los gatos que trabajan y te devuelve el numero de gatos que no trabajan. es solo una pequeña parte del reto, pero lo pongo pa k se vaya animando esto:

#include<stdio.h>
void main(void)
{
   int divisor=0,gatostrabajan=0,gatostotales=gatostrabajan+(divisor+1);

   printf("escribe el numero de gatos que trabajan: ");
   scanf("%d",&gatostrabajan);

      for(divisor=2;divisor<=gatostrabajan/2;divisor++)
      {
         if(gatostrabajan%divisor==0)
         {
            gatostotales=gatostrabajan+(divisor+1);
         }
      }

   printf("el numero total de gatos que no trabajan es %d",gatostotales-=gatostrabajan);
   getch();
}

tiene algun error pq con algunos ejemplos no funciona, ya me contaran

JuanK

En efecto esta mal, no aplica sino para unos pocos casos.

El algoritmo funcional debe aplicar para todos, te voy a dar pista pequeñita:

Si un sombrero 'x' posee N gatos, quiere decir que cada sombrero dentro de el sombrero 'x' tendra N*N gatos, es decir N al cuadrado...
y a la vez cada uno de los sombreros que poseen N*N gatos, tienen sombreros a los cuales les cabe tambien N gatos... y asi sucesivamente menos los ultimos gatos....

Recuerda que antes de diseñar los algoritmos, debes entender el sistema, asi que lo primero es que diseñes un diagrama donde expliques como funciona este sistema.. es decir no trabajes aun en conseguir los datos pedidos, trabaja primero en como representar el funcionamiento de este sistema de manera grafica y matematica...
Cuando entiendas cual es el funcionamiento del sistema, podras comenzar a mirar como obtienes los datos datos que te piden, a partir de la informacion que descubras.

Suerte, y sigue metiendole ganas!!!

a medida que progreses, o que otros progresen, les dare más pistas, porque al fin y al cabo ustedes estan aprendiendo.

Juank

JuanK

esto les va a ser de utilidad:

Juank

© Jonathan ©

Hola, estoy intentando resolver este reto, ya tengo casi listo el programa que resuelve el reto.... queria agregar al reto la forma de encontrar "N" que seria el umero de gatos que hay dentro de cada sombrero, creo que se puede hallar utilizando el numero de gatos que trabajaran, es decir si el numero de gatos que trabajaran sera de 125 gatos, este numero se puede dividir por 2, 3, 5 o 7, asi hallariamos la cantidad de gatos dentro de cada sombrero.

EJ:

125 gatos trabajan
/******************************/
......... implementar un bucle que divida este numero por 2, tantas veces como sea necesario, si se logra alcanzar a 1 entonces quiere decir que dentro de cada sombrero hay 2 gatos.
En este ejemplo si dividimos por dos, no nos dara de ninguna manera como resultado un 1, entonces intentamos con 3, al intentar vemos que tampoco funciona, probamos por 5 y ahi si, eso quiere decir que hay 5 gatos dentro de cada sombrero, porque:

125 / 5 = 25
25 / 5 = 5
5 / 5 = 1

Ahi tambien estan hallados la cantidad de gatos que no trabajan, al saber cuantos hay en cada sombrero encontramos la solucion, en este caso sumamos los 25+5+1=31 no sumamos los 125 chiquitos porque son los que trabajan.

Bueno, continuare con mi desarrollo, vere si puedo terminar el programa, espero esto sirva de algo y que no este mal elaborado, me costo bastante llegar hasta ahi. Saludos para todos y suerte con el reto.

JuanK

bueno, yo no lo solucione asi, perop posiblemente hayan muchas maneras de resolverlo, asiq ue sigue tratando a ver como te va, te aconsejo que hagas pruebas continuamente para no cometer errores que te puedan afectar al final...

te felicito Jhonathan.

© Jonathan ©

Hola a todos y las gracias a juank por el apoyo que nos brinda diariamente... esta vez les escribo para comentar que la forma en la cual me basaba para resolver el algoritmo es erronea, ya que hay numero que no tienen divisores mas que 1 y ellos mismos y algun otro. Por Ej 77.

Me habia costado llegar hasta ahi, parecia sencillo, pero ahora me doy cuenta que no es nada facil.

Una pregunta para juank....

Se puede resolver la cantidad de gatos que no trabajan sin antes saber cuantos gatos hay por sombrero?

Bueno, esto es todo, espero que nos largues alguna otra pistita...POR FAVOR.

Saludos y suerte para todos.

JuanK

Es necesario saber cuanto s el valor de N, para averiguarlo debes....

No quiero decirtelo todavia.. recuerda que la gracia del ejercicio es que tu mismo deduscas todas las posibilidades, porque sino no seria un reto...

tan solo te dire que analices esta parte:

Citar

El número de gatos dentro de cada sombrero (excepto el de los más pequeños) es una constante, N.
La altura de los gatos dentro de un sombrero es 1/(N + 1) veces la altura del gato dueño del sombrero en el que ellos están.

Los más pequeños gatos tienen altura de 1, y son los que hacen todo el trabajo.

y esta otra:

Citar

DATOS DE ENTRADA: “gato.in”

La entrada consta de una secuencia de especificaciones de gato-en-el-sombrero.
Cada especificación se encuentra en una línea que consta de dos enteros positivos separados por un espacio en blanco.
El primer entero es la altura de nuestro gato, y el segundo entero es el número de gatos que trabajan.
El archivo termina con #.

ves el dibujo que hice?..
no lo hice solo por ayudarles a ustedes.. la version original la hice para mi, de esta manera pude decifrar el algoritmo, ..
te aconsejo que dibujes todo lo que piensas, fijate en el dibujo y trata de hacer algo parecido con los datos que debes analizar... descubriras una inetresante solución...

Juank

JuanK

hola ,
bueno quiero informarles que el dia 1 de octubre publicaré la solucion completa al reto con lo cual lo dare por finalizado, si requieren un poco mas de tiempo pueden pedirlo sin problemas.

Esto se debe a que el 1 de octubre publicaré un reto diferente... como adelanto tiene que ver con HDLC.

Juank

desorden

Tengo una solución, aunque no creo que sea demasiado buena:P

Calcula los gatos que no trabajan si existe más de un sombrero y los gatos que trabajan son más de 1.

desorden

La solución que publiqué no es correcta. Además de los casos que no contemplaba, no resuelve otros -por ejemplo 289 256 N=16-. La verdad es que me puse a programar sin pensar mucho. A ver si antes de que juank publique su solución, resuelvo el problema.

desorden

Otro intento. Creo que está bien. Aunque es muy lento.

JuanK

Examine el codigo y aparentemente esta bien hasta donde vas.. si hay algo de problema en la velocidad, pero recuerda que el enunciado del reto no exigia ningun nivel de rendimiento.

Ahora, aparentemente, solo te resta adecuar el programa para que lea todas las lineas del archivo segun las especificaciones, y para que igualmente la salida sea el archivo gatos.out...

Animo te falta poco!!!....

JuanK

A N I M O ! ! !

Yo se que todos pueden terminar el reto, quiero invitarlos a todos a que sigan adelante, seria muy interesante ver los 3 programas que hay hasta el momento terminados, o por lo menos ver hasta donde llegara cada uno...!!!

No se rindan y sigan adelante!!!
queda poco tiempo.

desorden

No va más:)

Sueño con gatos y sombreros:P

Con esta entrada:

Código: Text

gato.in
3112136 3048625
13 12
64 1
28561 20736
3048625 2985984
37015056 35153041
9 4
16 9
216 125
6561 4096
4913 4096
729 512
289 256
117649 110592
5764801 1679616
#
 

Esta salida:

Código: Text

gato.out
12321231
25
127
122461
12068929
462540 180390211
19
37
671
26281
17985
2465
817
456385
335923 30275911
 

© Jonathan ©

Hola desordem, te felicito por el programa, eres una persona muy inteligente, yo todavia no se como hacer para encontrar N, me gustaria si puede ser que se explique la resolucion del problema.

Algo mas, intente compilar tu programa, lo compila perfecto y sin warning, pero cuando lo ejecuto aparece la ventana en donde debo ingresar los datos de altura y numero de gatos pero no deja escribir, a tal efecto debo cerrar la ventana con ctrl+c, Felicitaciones y Saludos.

JuanK

Bueno, la solucion solo sera explicada despues del primero de octubre, donde publicare la solucion teorica del ejercicio y tambien la solucion que yo tengo en conjunto con las diferentyes soluciones que entreguen las personas que participen de este reto.

Te invito a continuar con el reto, pues aunque no hayas sido el primero, lo importante es que lo puedas hacer, al final veremos cual programa quedo mejor, o que elementos de cada programa se deben destacar, en lo personal, y aunque no lo he constatado, parece que el que hizo desorden soporta numeros de mayor tamaño que el que yo hice, aunque el de él es un poco más lento en comparacion cn el mio... despues revisare eso...
Por ahora solo quiero animarte a que termines tu programa.. recuerda lo del dibujo y veraz como lo puedes deducir....

Un saludo.

JuanK

Hola, te felicito por tu programa,
Parece que esta bien, sin embargo tenemos una diferencia en nuo de los datos,seguramente causada porque es un dato exepcional que en niingun momento se requiere para cumplir el reto, estye caso es cuando el numero de gatos que trabajan es 1, ya que es ilogico pensar en este valor , porque si observas y aplicas las formulas, resulta que seria un arbol infinito ya que la raiz cuadrada de uno es uno...
Asi que la solucion para casos que posean un gato que trabaja, es como indeterminada.. creo yo...

Aqui va:

Código: Text

 
gato.in
 
3112136 3048625
13 12
64 1
28561 20736
3048625 2985984
37015056 35153041
9 4
16 9
216 125
6561 4096
4913 4096
729 512
289 256
117649 110592
5764801 1679616
#
 
 

Código: Text

 
gato.out
 
12321231
25
3
122461
12068929
462540 180390211
19
37
671
26281
17985
2465
817
456385
335923 30275911
 
 

Y este es mi codigo fuente:

JuanK

Bueno, muy bien por tu programa.

En especial la manera en que normalizaste tus funciones y variables, esto es muy importante.. a mi en general me gusta colocar nombres largos, es una excelente practica, pero en el momento que hice el programa no pense en eso puesto que inicialmente solo lo hice por hobbie y en mis ratos libres de trabajo, es decir a la hora de almuerzo.

Otra de las fortalezas de tu programa es que esta bien estructurado y es muy entendible aunque no este documentado.

Me parece.. no no me parece...
Definitivamente debes ser màs cuidadoso con el control de errores ya que practivamente es inexistente en tu programa, lo cual lo hace bastante vulnerable, lo mejor que se puede hacer cuando se programa es pensar en controlar todo lo que pueda pasar.

Bueno eso es todo, tambien espero comentarios de mi programa para ver en que más de puede mejorar.

Si alguien consigue otra solucion o logra resolver el asunto de que solo trabaje 1 gato.. le agradeceria sus comentarios tambien.

Hasta luego y gracias a todos.

Veremos que se puede hacer para darle un reconocimiento especial a todos los participantes y por supuesto a desorden , quien resulto ganader de este reto.

Mañana 2 de octubre publicare la solucion conceptual del algoritmo.

desorden

Yo no he podido incluir el caso de un gato trabajando, así que lo consideraba a parte:P

Para 64 1, la solución buena es 6 127.

¿Para cuándo el próximo reto?

JuanK

El proximo reto es acerca de protocolo hdlc.. y ya esta listo y resuelto tambien,
este reto es más sencillo que el anterior, ya que el anterior compromteia mucho de matematica y poco de programaciñon...

Este es más programación que matematica.

Ojalà hoy tenga más tiempo en la oficina para poder publicarlo, junto a la solución de este reto.

Ahh si esa solucion que daS no es buena, porque si observas , en el case de que el ultimo gato sea solo1, el numero de gatos del nivel anterior seria el equivalente a alguna raiz de uno.. que por supuesto siempre sera 1... asi que siempre habria 1 gato con un sombrero...

desorden

mmmmm

pues eso, ¿no?

Código: Text

 
gatos  altura
   G      64
   G      32
   G      16   
   G       8   
   G       4   
   G       2
   G       1
 
 

Gatos que no trabajan: 6.
Altura del conjunto: 127.

JuanK

Umm si ya veo, creo que tienes razon, pero como no lo habia hecho el caso del 1 en papel pues no lo habia analizado bien, me puse a hacer el razonamiento para el caso del 1 completo para que todos lo entiendan...jejeje

Código: Text

 
gatos1= N
gatos2= N a la 2
gatos3 = N a la 3
gatos4 = N a la 4
gatos5 = N a la 5
 
 

entonces si en gatos 5 N=1 (un gato que trabaja), se puede decir:

Código: Text

 
gatos1= N
gatos2= N a la 2
gatos3= N a la 3
gatos4= N a la 4
gatos5= N a la 5 =1
 
 

Segun esto, tambien se da que:

Código: Text

 
raiz quinta de 1  = N
la raiz quinta de 1 =1
entonces N = 1
entonces...
 
gatos1= 1 =1
gatos2= 1 a la 2=1
gatos3 = 1 a la 3=1
gatos4 = 1 a la 4=1
gatos5 = 1 a la 5=1
 
 

Entonces la suma de las alturas en cada fila seria x(1/(N+1)).. como N =1 quedaria:
x(1/2)
entonces si en gatos5 altura =1 quedaria:

x(1/2)=1
x=2
entonces:

Código: Text

 
gatos    altura
...
...
   G1=1       16   
   G2=1       8   
   G3=1       4   
   G4=1       2
   G5=1       1
 
 

Y esta fué mi explicacion...

JuanK

Bueno con el razonamiento anterior , se completa la explicacion de como hallar el valor de N.. por eso no lo explicare nuevamente.

Si alguien tiene alguna inquietud o duda, me puede enviar un mensaje por U2U o a mi mail, y con gusto la respondere por el mismo medio, o si lo docnsidero pertienente lo publicare en el foro.

juanjgm

A mi me mandaron este mismo programa pero a realizarlo en java pero no se ni por donde empezar... les agradeceria que me ayuden con este programa para realizarlo en java. ya que es un proyecto de mi universidad y me cuesta 30% de la materia.