vBracco

Sitio personal de Victor Bracco [Programador PHP]

1. Tordek 19.02.09 a las 10pm
   

   Hay una forma O(1):

   Entre 1 y N hay floor(N/k) numeros divisibles por K.

   Vos querés la suma de esos números, para K=3 y K=5. Pero si simplemente sumaras los divisores correspondientes, sumarías los múltiplos de 3*5 dos veces. Entonces, querés:
   suma_de_divisores(3)+suma_de_divisores(5)+suma_de_divisores(15).

   Sabiendo la cantidad de divisores, podemos hacer:
   for i in range(1, cantidad + 1): suma += i*3

   Pero eso nos da dos pistas. La primera, es que podemos pasar el producto hacia afuera:
   for i in range(1, cantidad + 1): suma+=i
   suma*=3

   La segunda, es que estamos sumando todos los números de 1 a n. Y eso ya aprendimos que es igual a n * (n + 1)/2. Finalmente

   def suma_de_divisores(num, div):
   cant = math.floor(num / div)
   suma = cant * (cant + 1)/2
   return suma * num

   suma_de_divisores(100, 3)+suma_de_divisores(100, 5)-suma_de_divisores(100, 15)

   2148
2. Sabo 19.02.09 a las 11pm

   Efectivamente Tordek, la solución usando progresiones aritmeticas es creo la mejor que resuelve este problema y creo que también es la que más abunda por internet.

   Al marge, el problema es con los multiplos hasta 1000 y no hasta 100, pero ese código igual lo resulve en un tiempo cortisimo.

   Mi solución simplemente es “no tan común” y que reduce considerablemente el tiempos y los calculos sobre el primer código.

   Gracias por participar y espero que comentes los problemas que siguen tambien!
3. Tordek 20.02.09 a las 12am
   

   De paso, en tu solución:
   for(int i=0; i < 1000; i+=patron[x-1] ){

   Me sorprende que siquiera funcione, dado que en el primer paso estás accediendo a patron[-1].

   Una vez eliminado el -1 de ahí, podemos evitar el que el índice empiece en 1:
   x = (x==7) ? 1 : x+1;
   por
   x = (x+1)%7

   Y, dado que x sólo actua sobre el índice, y no el resultado, me parece más apropiado que sea parte del bucle:

   
main()
{
int patron[7] = {3,2,1,3,1,2,3};
int result=0;

   for(int i=0, x=0; i < 1000; i += patron[x], x = (x+1)%7)
   result += i;

   printf("%d",result);
}

4. Tordek 20.02.09 a las 4am

   Ahora, dos problemas interesantes (creo) relacionados a ambas soluciones:

   1) Dada una lista de números A, generar una lista Restas, tal que sum(flatten(map(hallar_divisores, A))) - sum(flatten(map(hallar_divisores, Restas))) sea la suma de todos los múltiplos de A entre 1 y 1000 (asumiendo que hallar_divisores encuentra los números divisibles por k entre 1 y 1000).

   2) Dada una lista de números A, generar una lista que haga la función de tu array patron.
5. Sabo 20.02.09 a las 8am

   Tordek, a menos que mi lógica me este engañando, en el primer ciclo no entra en la posición [-1]. Esa asignación de i dentro del for se ejecuta cuando finaliza cada bucle, y para el final del bucle x ya tiene un valor 1 y entonces ingresa en la posición [0].

   Y por cierto, ese último código me parece mucho más lindo, solo que que demora más en resolverlo. Con números hasta 1.000.000.000 mi código esta demorando 3.5s y el tuyo 7.7s. Mas allá de eso, me parece buenisimo.

   Pero poniendolo de esta forma, queda si más amigable que mi último código, y demora practicamente lo mismo

       for(int i=0, x=0; i < 1000; i += patron[x], x = (x==6)? 0 : x+1)
          result += i;
       printf("%d\n",result);
   

   Los problemitas (creo) son bastante locos pero te escribo algunos posts si lo llegas a hacer.
6. Tordek 20.02.09 a las 3pm
   

   Tordek, a menos que mi lógica me este engañando, en el primer ciclo no entra en la posición [-1]. Esa asignación de i dentro del for se ejecuta cuando finaliza cada bucle, y para el final del bucle x ya tiene un valor 1 y entonces ingresa en la posición [0].

   Ah, buen detalle… Un punto a favor para escribir el bucle de mi forma, supongo ;).

   El segundo problema, lo resolví anoche en O(N^2) mientras intentaba dormir:
   Haciendo un bucle de 0 a N con un step de k, para cada numero k, sobre un array A, poniendo 1 en A[k]. A tiene que tener suficiente espacio para sostener “una vuelta entera”. “Una vuelta entera” == MCM (conjunto de números). Ahora tenés un array booleano que te dice si los números pertenecen al conjunto (esta parte es la O(N^2), que domina la complejidad). Después, lo único que hay que hacer, es un bucle de 0 a N, calculando la diferencia entre cada par de unos.

   El primero todavía está…
7. Tordek 17.10.09 a las 7pm
   

   WTF? ¿Por qué tengo sombrerito de Troll?

Powered by Hemingway flavored Wordpress.
Este blog esta licenciado bajo Creative Commons.

RSS de Entradas RSS de Comentarios