Resolución de algoritmos [Reto semanal] #1

B

#30 Te falta adjuntar el código!
#31 Hay que poner también lo que imprime el programa, que se vea el resultado
#37 Tampoco se ve el resultado :laughing::sweat_smile:
#40 Mientras el resultado sea el correcto yo creo que puedes hacerlo como quieras

Según he mirado las soluciones són:

Segundo problema: 161667 (al tío que la hizo le tardó 45ms)
Tercer problema: 2906969179

Las voy ha poner en #1 para que podamos saber si nuestras soluciones son o no las correctas.

3 respuestas
B

#61

spoiler

eso me daba

ostia el segundo como coño sera?

sraam

#61 No vendrá la solución del segundo en algún lado verdad? Me interesa muchísimo.

1 respuesta
B

#63 La solución la he puesto en #61 , si te refieres al código también lo tengo localizado y te lo puedo pasar por mp. También lo pondré en #1 cuando termine la semana

n3krO

#61 45 ms el segundo problema? xDDDD

B-eman

He hecho el primer ejercicio y no hay manera, lo he intentado en COBOL y en VBA que son los lenguajes que conozco y no me entran los números en las variables. Dejo el código por si alguien me echa una mano. Yo queriendome ganar la vida como programador y no soy capaz ni de hacer el fácil.

COBOL
VBA
Kaiserlau

#41 en que estas haciendolo y que micro? xD Yo ando por los 4m :$ para 6k :/ con un i5 chusta de porta

malditas matracas tete

1 respuesta
sraam

#67 En C# y el micro un i5 6200 2.30GHz

CarlosML27

Por aquí en Python, lo he hecho lo más sencillo posible, si queréis puedo completarlo y dejarlo más bonito, pero prefiero hacer las soluciones primero y luego refactorizar si es necesario.

Problema fácil

El resultado es

CarlosML27

Vale, aquí tengo el código del problema medio, aunque la solución no la tengo porque me temo que no dispongo de la computación de la NASA. Aun así lo he probado para valores más bajitos y parece que funciona bien.

Factores a tener en cuenta:

  • Viendo la ecuación a²+b²=c², no podemos tener a=b. Esto se puede demostrar haciendo la ecuación 2a²=c², la cual solo sería válida si a = c*(√2)/2, que como podemos ver a simple vista no da una solución entera. Por tanto, suponemos a < b.
  • También tenemos c > a y c > b, lo cual podemos ver a simple vista en cualquier triángulo rectángulo con el propio teorema de pitágoras. Puedo desarrollarlo un poco más pero creo que es evidente.
  • Por otra parte, a+b > c. Si "estiramos" los lados a+b y creamos un único segmento, en ningún caso puede ser menor o igual que c, puesto que de otra manera no podríamos formar el triángulo.

Gracias a este último punto, y sabiendo que a+b+c = L, podemos ver claramente que c nunca va a ser igual o mayor que L/2, lo cual reduce mucho nuestra carga de computación (LA CUAL SIGUE SIENDO INMENSA).

Aquí os dejo el código que he hecho, si alguien se atreve a probarlo o ve algún fallo puede decirlo sin problema.

Problema medio
PaCoX

el segundo problema lo planteáis mal, los problemas que incluyen ternas pitagóricas están diseñados para que se analice el problema buscando secuencias, etc Centrarse solo en el teorema de pitagoras es un error xD

2 respuestas
Kaiserlau

#71 para aprender primero hay que usar la tecnica del martillo xD

CarlosML27

#71 Mi idea, al menos personalmente, es buscar la menor cantidad de información posible e intentar hacerlo todo por mis propias deducciones (y a ser posible también, sin usar librerías ni nada parecido que me lo deje facilito). Lo que he puesto en #70 se puede deducir de manera sencilla sin tener que mirar en Google, el método de extracción de ternas pitagóricas a través de sucesiones de Fibonacci probablemente no.

Por supuesto que hay maneras muchísimo más efectivas, pero yo lo que quiero es romperme un poco la cabeza, transcribir fórmulas más o menos sabemos todos.

PaCoX

por ejemplo, una terna pitagórica siempre tiene 3 números pares o 2 impares y uno par.
Con eso sacas que la suma de los tres números de la terna siempre sera par => ya te has cargado la mitad de los números a comprobar de vuestros bucles

Luego hay mas cosas como solo buscar las ternas primitivas. Por ejemplo la terna (3,4,5) es primitiva ¿que quiere decir eso? pues que si multiplicas x2 esa terna te saldrá otra terna pitagórica valida, en ese caso (6,8,10).
Eso sirve tmb para el enunciado, los múltiplos de una terna primitiva encontrada serán validos (3,4,5) es 12-> por tanto 24,36,48,etc son números validos.

Las primeras ternas primitivas son:
(3,4,5) =12
(5,12,13) =30
(8,15,17) =40
(7,24,25) =56
(9,40,41) =90
(11,60,61) =132

ale ya teneis pa rato xD

3 2 respuestas
Kaiserlau

#74 estoy calculando con lo de las ternas ahora. Si q va mucho mas follado, benditas mates xxdxd.

2
n3krO

#74 y no es mas facil usar la formula de euclid? xd

PaCoX

esa manera es valida tmb pero es más rápido hacer arboles de ternas pitagoricas de Berggren
https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples

Kaiserlau

como no me de bien menuda perdida de hora ya casi xd

R

Dejo la solucion del tercero en Java:

codigo

spoiler

solución:

spoiler
elderaine

Bueno me uno al reto 1 y lo hago en R

spoiler

Solución:

spoiler
mecmec

En el último hasta mil no me da el resultado del enunciado que dan, el segundo pasando de abordarlo y el primero sencillo xD.

PD: done, la solución oficial contaba el 5 como un palíndromo :C

T

He resuelto el fácil. Código:

spoiler

Resultado

spoiler
S

Solución del segundo:
161667 rectángulos 0.54 segundos

spoiler
1 respuesta
R

Por aquí dejo la solución del primero en C:

Código:

spoiler

Solución:

B

#83 Podrías explicarlo por favor? a grandes rasgos. (no comentar el código, el própio método numérico)
edit: nvm, https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples es esto en esencia.

HeXaN

Para el primer problema he tirado a por el clásico método que te enseñan en segundo de carrera. Hecho en Python y ejecutado 0,06 segundos.

spoiler
1 respuesta
Soulscx

#86 puedes explicar un poco el algoritmo del fibonacci que usas? la operacion // es div?

1 respuesta
HeXaN

#87 Es una reducción del método de la exponencial de matrices para el cálculo de la serie de Fibonacci con números grandes. Si te interesa el tema puedes leer sobre la Fibonacci Q-Matrix, la fórmula de Binet o el algoritmo de Karachi.

3
S

Viendo el resultado he visto que tenia mal el tercero.
Resultado: 2906969179
Tiempo: 1.1 segundos

spoiler
Soulscx

problema 2

spoiler

super ineficiente pero sencillo de entender