Resolución de algoritmos [Reto semanal] #1

B

el primero con python

spoiler

no os rias de un pobre no informatico xd

1 respuesta
guner

Solución al de los palíndromos. Al menos da lo que dice el problema para < 1000.
Lenguaje: fortran
Si alguien lo pide lo comento y le pongo nombres de variables decentes.

spoiler

El resultado me da 130 palíndromos con solución válida con una serie de suma de cuadrados de enteros consecutivos, y la suma total, 312062975

spoiler

Edit: #30 ¿Has comprobado la solución de cuadrados de los palíndromos o has comprobado que sucesivas series eran palíndromos? Intenté optimizar con la segunda opción, pero no tengo claro que se hagan menos cálculos.

2 respuestas
B

el segundo estoy intentando usar python en vez de maple para resolver el sistema y no me salen las soluciones porque no tengo ni idea de en que formato me escupe sympy el resultado xD

Si alguien quiere le digo como se hace y que lo programe el ahi to pro xD, teamwork

B

#32 He ido haciendo todas las series posibles menores que un millon(10 elevado a 8). Vamos dos for de mierda con numeros del 1 hasta el 500 creo que he puesto, e iba creando la serie con esos dos for
1+2+3+4+etc
Cuando me pasaba del millon salia del segundo bucle for y empezaba otra vez
2+3+4+etc
Luego antes de ir haciendo la serie más grande compruebo si el numero actual es un palindromo
1+2 = x (compruebo si es palindromo)
1+2+3 = y (compruebo si es palindromo)
1+2+3+4 = z (se pasa del millon, ni compruebo)
2+3 = xx

1 respuesta
chocula

#34 Era 108. 100 millones :D Pero imagino que en el código está bien, porque tienes resultados mayores que 106.

1 respuesta
B

numero 2

spoiler

Usando calculo simbolico para resolver las ecuaciones, lo que pasa que claro tarda un tiempo del carajo en ahcer los numeros. Mañana lo hago para calcularlo con un metodo numerico que es mucho mas rapido y redondeo a un entero

Para L<150 esa son las salidas, si alguien tiene un pc de la nasa y quiere probar 1500000 suerte pa el que le va a echar humo xD

GuaNaGe

Me animo con el primero, un principiante que lleva solo 2 añitos programando, se agradece la ayuda y que me echéis un cable en todo lo que veáis que puedo mejorar.

spoiler

No enfadaros mucho por la chapuza del array de [0,1] pero tampoco tenía ganas de complicarme mucho. Javascript he usado por usar algo rápido. Ahora hago algún otro o lo intento^^

1 respuesta
R

Tengo el primero en C con dos Arrays de mil posiciones de tipo Char.
El segundo lo tengo pero me funciona en un tiempo razonable para valores más bajos, sobre los 5000-10000, para el valor del ejercicio tarda demasiado.

Kaiserlau

El primer ejercicio en Python3

spoiler

Para el resto tendre que repasar matracas y tal xD

n3krO

Hay algun requisito para las soluciones?

En plan se tiene que transformar en problema de tipo P (por eso de que el algoritmo sea escalable) o nos vale con cualquier codigo que hace las cosas a lo bruto?

1 respuesta
sraam

En el segundo, he conseguido bajarlo a 6000 longitudes en 2 minutos pero esto sigue sin ser viable para llegar a 1500000, empiezo a pensar viendo como estáis los demás que no se puede sacar en un tiempo razonable.

2 respuestas
B

#35 Es ponerlo 0 al if que comprueba los numeros

Mkay

mkay

1 respuesta
B

Mi solución al palíndromo usando windows powershell, que no tengo ningún compilador instalado :rofl:

spoiler

a partir de 106, empieza a echar humo como es de esperar (es powershell, no c), con soluciones tipo:
999831 = 53²+ 54²+ 55²+ 56²+ 57²+ 58²+ 59²+ 60²+ 61²+ 62²+ 63²+ 64²+ 65²+ 66²+ 67²+ 68²+ 69²+ 70²+ 71²+ 72²+ 73²+ 74²+ 75²+ 76²+ 77²+ 78²+ 79²+ 80²+ 81²+ 82²+ 83²+ 84²+ 85²+ 86²+ 87²+ 88²+ 89²+ 90²+ 91²+ 92²+ 93²+ 94²+ 95²+ 96²+ 97²+ 98²+ 99²+ 100²+ 101²+ 102²+ 103²+ 104²+ 105²+ 106²+ 107²+ 108²+ 109²+ 110²+ 111²+ 112²+ 113²+ 114²+ 115²+ 116²+ 117²+ 118²+ 119²+ 120²+ 121²+ 122²+ 123²+ 124²+ 125²+ 126²+ 127²+ 128²+ 129²+ 130²+ 131²+ 132²+ 133²+ 134²+ 135²+ 136²+ 137²+ 138²+ 139²+ 140²+ 141²+ 142²+ 143²+ 144²+ 145²+146²

para ejecutarlo cualquier persona que tenga windows: Win+R → powershell → copypaste (y cambiar el 8 de arriba por algo inferior, 4 es rápido)

B

Soy idiota, no sé qué es un palíndromo, pongo la nueva solución en dos minutos...:psyduck:

1 respuesta
guner

#45 Ojo, comprobando que el resultado de las sucesivas series son palíndromos podría hacer que cuentes alguno más de una vez si existen dos series que dan ese número como resultado. Entiendo que el problema no pide eso.

Edit: Ni idea de que powershell permitiera tal nivel de scripting.

1 respuesta
B

#46 No, primero cojo el número y luego le busco la serie, no al revés.

Voy a optimizar el código haciéndome un generador de palíndromos, esto agiliza mucho el código ya que no son 108 elementos, sino muchísimos menos que comprobar.

spoiler
2 respuestas
guner

#47 Ah, ok. Lo estabas intentando como lo intenté yo.
Hay una cosa que no me queda clara.
¿Valen series de un solo miembro o hay que empezar por dos? Porque si el mínimo es 2 el máximo que tú usas para empezar a calcular series es 1/2(sqrt(2n+1)-1).

1 respuesta
B

#48 Si es una serie de un solo miembro, no es una serie (he considerado)

B-eman

Los estoy haciendo en cobol y en el primero cobol no me deja meter más de 18 dígitos en una variable y en el segundo lo he ejecutado con 6000 y lleva media hora no lo veo posible esto.
El tercero no se ni por donde empezar.

B

#41 yo como lo he hecho es imposiblle que un ordeador nornal lo haga. Tiene quehaber otra forma.
Lo que me he dao cuenta esq la longitud siempre es par, esto significa que los lados son o bien par par par o par impar impar.
Estoy seguriiiiiisimo que por ahi van los tiros para resolverlo sin tener que resolver la requacion, haciendo algun tipo de filtr con la paridad

2 respuestas
guner

#51 En el de los triángulos tiene toda la pinta de que hay que ir excluyendo todos los múltiplos de cada triángulo que encuentres y ir buscando sólo los que sean nuevos triángulos con perímetros múltiplos de los que no eran válidos.

B

El de los triángulos me parece el más difícil, hay que saber algo de mates

S

#47 Si haces eso estas calculando las mismas series varias veces y queda un algoritmo muy ineficiente.

El tercero en js, tarda 3 segundos en el navegador:
Me da la misma solución que a #43 y distinta que a #32

spoiler
Soulscx

estaria muy bien adjuntar tiempo de ejecucion medio, es q esos algoritmos que ni siquiera lo resuelven en años, no los veo solucion :sweat_smile:

2 1 respuesta
B

#55 el 2 para l=500 se me iba a 19s. Para l=1500000 a saber cuants años.
Sigo creyendo que tiene que haber algo con la paridad jajajja

Soulscx

pues si este hilo te ayuda a mejorar un algoritmo de años a minutos entonces, ya ha valido la pena

sraam

#51 Lo he reducido a casi 7000 en un minuto, creo que ahí lo voy a dejar y voy a empezar a mirar el de los palindromos porque se me acaban las ideas para mejorarlo.

En cuanto a lo de par/impar, he visto que pueden ser 2 pares y 1 impar, o 2 impares y 1 impar, no veo una normal clara.

1 respuesta
B

#58 mmmm 2 pares y 1 impar va a dar un numero impar, y yo no he obteniedo ninguna longitud impar con el programa que puse en #36

1 respuesta
sraam

#59 Vale, me he liado y lo he visto mal, serian 3 números pares.