Resolución de algoritmos [Reto semanal] #1

B

[Borrado] #61 Feb '18

#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
#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

[Borrado] #62 Feb '18

#61

spoiler

eso me daba

ostia el segundo como coño sera?

sraam #63 Feb '18 Diamond hands

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

1 respuesta

B

[Borrado] #64 Feb '18

#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 #65 Feb '18 Diamond hands

#61 45 ms el segundo problema? xDDDD

B-eman #66 Feb '18

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 #67 Feb '18 Penitente

#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 #68 Feb '18 Diamond hands

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

CarlosML27 #69 Feb '18

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

fibonacci = 0
fibonacci_index = 2
previous_one = 1
previous_two = 1
digits = 1000
limit = pow(10, digits-1)

while fibonacci < limit:
	fibonacci = previous_one + previous_two
	previous_two = previous_one
	previous_one = fibonacci
        fibonacci_index = fibonacci_index + 1

print(fibonacci_index)

El resultado es

spoiler

CarlosML27 #70 Feb '18

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

c = 3
max_length = 1500000
result = []
repeated = []

while c < max_length/2:
	b = 2
	while b < c:
		a = 1
		while a < b:
			if (a**2+b**2 == c**2):
				length = a+b+c
				if length <= max_length:
					if length in result:
						repeated.append(length)
						result.remove(length)
					else:
						if length not in repeated:					
							result.append(length)
			a = a+1
		b=b+1
	c=c+1

print(len(result))

PaCoX #71 Feb '18 Ant queen

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 #72 Feb '18 Penitente

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

CarlosML27 #73 Feb '18

#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 #74 Feb '18 Ant queen

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 #75 Feb '18 Penitente

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

2

n3krO #76 Feb '18 Diamond hands

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

PaCoX #77 Feb '18 Ant queen

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 #78 Feb '18 Penitente

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

R

RsTTa #79 Feb '18

Dejo la solucion del tercero en Java:

codigo

spoiler

private static long sumaPalindromosMenores(int n) {
		List<Long> numeros=new ArrayList<>();
		long suma=0; //suma total
		int i=2; //variable que indica donde empieza la serie de cuadrados
		while(i<Math.sqrt(n)){
			int j=i;
			long palindromo=(j-1)*(j-1)+(j*j);
		
		while(palindromo<n){
			if(esCapicua(palindromo) && !numeros.contains(palindromo)){
				numeros.add(palindromo);
				suma+=palindromo;
			}
			j++;
			palindromo+=j*j;			
		}
		i++;
	}		
	return suma;
}

private static boolean esCapicua(long palindromo) {
	String num=Long.toString(palindromo);
	int i=0, f=num.length()-1;
	while(i<=f)
		if(num.charAt(i++)!=num.charAt(f--))
			return false;
	return true;
}

solución:

spoiler

elderaine #80 Feb '18

Bueno me uno al reto 1 y lo hago en R

spoiler


library(gbm)
Fibonacci_1 <- as.bigz(1)
Fibonacci_2 <- as.bigz(1)
index <- 2

while(nchar(as.character(Fibonacci_2)) < 1000){
  temp <- as.bigz(Fibonacci_2 + Fibonacci_1)
  Fibonacci_1 <- Fibonacci_2
  Fibonacci_2 <- temp
  index <- index + 1
}

print(index)

Solución:

spoiler

mecmec #81 Feb '18

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

TroyaProgram #82 Feb '18

He resuelto el fácil. Código:

spoiler

Resultado

spoiler

S

Sarwaz #83 Feb '18

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

spoiler

const maxPer = 1500000;
const A = [-1, 2, 2, -2, 1, 2, -2, 2, 3];
const B = [1, 2, 2, 2, 1, 2, 2, 2, 3];
const C = [1, -2, 2, 2, -1, 2, 2, -2, 3];
const initTriple = [3,4,5];

const startTime = new Date().getTime();

let triples = [];
triples[maxPer];
let found = 0;

const getPer = triple => {
  return triple.reduce((a, b) => {
    return a + b;
  });
};

const multiplyMatrix = (a, b) => {
  return [a[0] * b[0] + a[1] * b[1] + a[2] * b[2], a[3] * b[0] + a[4] * b[1] + a[5] * b[2], a[6] * b[0] + a[7] * b[1] + a[8] * b[2]];
};

const getMultiples = triple => {
  const basePer = getPer(triple);
  for (let i = 1; i < maxPer; i++) {
    let sum = basePer * i;
    if (sum <= maxPer) {
      if (!triples[sum]) {
        triples[sum] = 0;
        found++;
      }
      triples[sum]++;
      if (triples[sum] == 2) {
        found--;
      }
    } else {
      break;
    }
  }
};

const getNextTriples = triple => {
  let triples = [multiplyMatrix(A, triple), multiplyMatrix(B, triple), multiplyMatrix(C, triple)];
  triples.forEach(triple => {
    let per = getPer(triple);

if (per <= maxPer) {
  getMultiples(triple);
  getNextTriples(triple);
}
  });
};


getMultiples(initTriple);
getNextTriples(initTriple);
console.log(found, 'End time:', new Date().getTime() - startTime);

1 respuesta

R

RsTTa #84 Feb '18

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

Código:

spoiler

void sumarArrays(char nums[2][1000], int i){
    int j, carry=0;
    for(j=999; j>=0; j--){
        nums[i%2][j] += (nums[(i-1)%2][j] + carry);
        carry = nums[i%2][j] / 10;
        nums[i%2][j] %= 10;
    }
}

int indicePrimerNum1000digitos(){
    char nums[2][1000]={0};
    nums[1][999]=1;

int i=1;
while(!nums[i%2][0]){
    i++;
    sumarArrays(nums, i);
}

return i;
}

Solución:

spoiler

B

[Borrado] #85 Feb '18

#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 #86 Feb '18

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

def fib(n, c={0: 1, 1: 1}):
    if n not in c:
        x = n // 2
        c[n] = fib(x - 1) * fib(n - x - 1) + fib(x) * fib(n - x)
    return c[n]


def euler_25(digits_number):
    index = 1
    while True:
        if len(repr(fib(index))) >= digits_number:
            return index
        index += 1

1 respuesta

Soulscx #87 Feb '18

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

1 respuesta

HeXaN #88 Feb '18

#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

Sarwaz #89 Feb '18

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

spoiler

function palimdromSum(limit) {
  const maxNumber = limit;
  const isPalimdrom = function (number) {
    const asStr = number.toString();
    return asStr == asStr.toString().split('').reverse().join('');
  }
  const initTime = new Date().getTime();
  let found = [];
  for (let i = 1; i < maxNumber; i++) {
    let sum = i * i;
    for (let j = i + 1; j < maxNumber; j++) {
      sum += j * j;
      if (sum > maxNumber) {
        break;
      }
      if (isPalimdrom(sum)) {
        if (found.indexOf(sum) == -1) {
          found.push(sum);
        }
      };
    }
  }

  console.log(found.length, found.reduce((a, b) => { return a + b }), 'Total time:' + (new Date().getTime() - initTime));
}

Soulscx #90 Feb '18

problema 2

spoiler

public static void main(String[] args) {
		int cont = 0;
		for (int i = 12;i <=1500000;i++) 
			if (i % 2 == 0 && tri(i)==1)
				cont ++;;
		System.out.println("total:    " + cont);
	}
	
public static int tri( int l) {
	int a = 0 ;
	int b = 0;
	int c = 0;
	int contador = 0 ;
	for (c = 3; c < l/2 ; c++)
		for (b = c; b < l-c ; b++) {
			a = l-b-c;
			if (a*a==b*b+c*c ) 
				contador++;	
		}
	return contador;
}

super ineficiente pero sencillo de entender

Usuarios habituales

Tags