0votos

División equivalente en C

por josejuan hace 6 años

No me parece nada fácil obtener la solución. De hecho, no tengo ni idea de cual puede ser. La propiedad que usa "akaJumi" es que, para todo 'n' existe solución SI Y SOLO SI existen números 'a' y 'b' tales que 1<a<b<=n pero ésto requiere demostración. Por otra parte, si SUPONEMOS que dicha propiedad es correcta, la solución es directa, pues basta despejar 'b' de la relación mencionada (ver detalles en la solución).

Dividir los n primeros números en dos grupos A y B tales que la suma de los elementos de A sea igual al producto de los elementos de B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*  
     Supuesto hay solución sii existen a y b tales que se cumple  
  
            1 < a < b <= n  
  
     con  
  
            n (n + 1) / 2 - 1 - a - b = a b  
  
     basta despejar 'b' para obtener  
  
           b = (n^2 + n - 2 (a + 1)) / (2 (a + 1))  
  
    así (ignorando posibles excepciones con n pequeño).  
  
    Es posible hacer speedups adicionales, porque es posible establecer  
    acotaciones.  
  
    Como se pide velocidad está en C y optimizado, cada iteración (de 2 a n)  
    requiere (en el peor caso):  
  
    * tres comparaciones (<=, ==, <=)  
    * una resta  
    * una división  
  
    En mi humilde Intel Atom calcular hasta 1 000 000 le lleva 45 milisegundos.  
*/  
int solucion(int n, int *_a, int *_b) {  
  int k = n * n + n;  
  int a = 6, L = n << 1;  
  while(a <= L) {  
    if((k - a) % a == 0) {  
      int b = (k - a) / a;  
      if(b <= n) {  
        *_a = (a >> 1) - 1;  
        *_b = b;  
        return 1; // solución 1 * a * b  
      }  
    }  
    a += 2;  
  }  
  return 0; // sin solución  
8 comentarios
0votos

Escrito por jjesus296 hace 6 años

Hola JoseJuan. Tu solución me ha gustado mucho a nivel de codigo y me parece elegante y eficiente (aunque desconozco si se ahorra mucho tiempo de CPU usando desplazamientos de bits en la multiplicacion/division por 2, para numeros no demasiado grandes). Como mi nivel de Matematicas no es muy bueno, te importaria explicarme como llegas a esto a partir del enunciado?

Supuesto hay solución sii existen a y b tales que se cumple

1 < a < b <= n

con

n (n + 1) / 2 - 1 - a - b = a b

GRacias.
0votos

Escrito por josejuan hace 6 años

Usar shift en lugar de div para dividir por dos es un ahorro ENORME en tiempo de CPU (da igual si el número es grande o pequeño, debe caber en la palabra de la máquina).

Por otro lado, sólo hay que despejar "b" de la expresión, como "n" es fijo, iteramos sobre "a" hasta que la división es entera, no se me ocurre qué es lo que quieres que explique de la parte "matemática".
0votos

Escrito por jjesus296 hace 6 años

Despejar b si lo veo. Lo que no pillo aun es de donde sale esta expresión:

n (n + 1) / 2 - 1 - a - b = a b

No se si viene a partir de la desigualdad:

1 < a < b <= n

Gracias.
0votos

Escrito por josejuan hace 6 años

Ah! ok, como digo en la descripción de la solución, NO SE SI ES CORRECTA, únicamente he utilizado la implementación de "akaJumi" que es bastante "rara" porque crea un vector cuando claramente no hace falta.

Él, recorre los números (de ahí que no haga falta el vector), buscando dos números que cumplan la propiedad que yo indico, realmente él escribe (lo simplifico porque él realmente lo ha escrito feo, feo, feo [lo siento akaJumi]):

sumatotalmenosmultiplos = self.totalmenos_uno - a - b;

Para obtener la suma total no hace falta iterar, basta saber que el sumatorio de 1 a n (ésto en secundaria se da seguro) es: n(n+1)/2. Luego dice que le quita uno y que le quita los números 'a' y 'b', Y DICE SIN DEMOSTRAR que "eso" es la parte del problema de los números que se suman (por descarte, los números que se multiplican son 1, a y b). Es decir, justo la relación que he puesto.

En lugar de buscar 'a' y 'b', únicamente buscamos un 'a' para el que el cálculo de 'b' es exacto (sin resto).

Luego ya el tema de la optimización.
0votos

Escrito por josejuan hace 6 años

Mi hipótesis es que "akaJumi" ha encontrado la respuesta "por ahí" escrita con subíndices (típico en matemáticas) y de ahí que haya usado un vector cuando realmente no hace falta.

¡Estaría bien saber esa fuente!
0votos

Escrito por akaJumi hace 6 años

Tu hipótesis es incorrecta. La solución la saque a base de lápiz y papel y la formula la escribí tal cual aparece en el problema (en el papel).

Lo que pasa es que soy un mal programador y lo de la eficiencia no es algo que me importase demasiado en el momento de implementar la solución.

NOTA: Yo mismo no se si la solución es valida, pero para un montón de casos que evalúe manualmente así parecía.
0votos

Escrito por josejuan hace 6 años

"Tu hipótesis es incorrecta"

es lo que tienen las hipótesis, que a veces son falsas

"Lo que pasa es que soy un mal programador"

siempre es bueno tener margen para la mejora XD XD, pero en verdad que no entiendo como se te ocurrió escribir semejante código (es feo, feo, ...)

"pero para un montón de casos"

yo también busqué millones de contraejemplos y no encontré ninguno, no quiere decir que sea cierta, quizás aplicando la solución de JAlonso se pueda demostrar (así a ojo, no lo veo).
0votos

Escrito por jjesus296 hace 6 años

Gracias josejuan. Siento no poder votarte aún, ya que no tengo suficiente reputación. Te debo uno ;-).

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.