Proyecto Euler Problema 12 - C++ - Excelente biblioteca

Estoy trabajando en el problema 12 con respecto al primer número de triángulo con 500 divisores. Intenté forzar brutalmente la solución. Obtengo 300 divisores en aproximadamente 35 segundos y no puedo obtener 400 en 10 minutos. Voy a modificar mi solución para usar el método del factor principal, pero ahora he visto que la gente sigue obteniendo esta solución con la fuerza bruta en menos de un minuto.Proyecto Euler Problema 12 - C++

¿Puede por favor criticar mi código y decirme si me falta algo que hace que esto sea terriblemente ineficiente?

unsigned long long TriangleNumberDivisors(int divisorTarget) 
{ 
    unsigned long long triangleNum=1; 
     unsigned long long currentNum=2; 
    int numOfDivisors=0; 


    numOfDivisors=NumOfDivisors(triangleNum); 
    while(numOfDivisors<divisorTarget) 
    { 
     triangleNum+=currentNum; 
     currentNum++; 
     numOfDivisors=NumOfDivisors(triangleNum); 
    } 

    return triangleNum; 
} 

int NumOfDivisors(unsigned long long dividend) 
{ 
    int numDivisors=0; 
    set<unsigned long long> divisors; 
    set<unsigned long long>::iterator it; 

    for(unsigned long long index=1; index<=dividend/2; index++) 
    { 
     if(dividend%index==0) 
     { 
      divisors.insert(index); 
      numDivisors++; 
      it=divisors.find(dividend/index); 
      if(it==divisors.end()) 
      { 
       divisors.insert(dividend/index); 
       numDivisors++; 
      } 
       /*for some reason not checking for dups above and 
just checking for how many items are in the set at the end is slower 
      for(it=divisors.begin();it!=divisors.end();it++) 
      { 
        numDivisors++; 
      } 
        */ 
     } 
    } 

    return numDivisors; 
} 

int main() 
{ 
    cout<<TriangleNumberDivisors(500)<<endl; 

    return 0; 
}

Actualización: Lo tengo ahora, gracias. Se modificó para verificar solo la raíz cuadrada del número e hizo una comprobación adicional para ver si era un cuadrado perfecto. Esto me permitió eliminar el conjunto por completo también. 500 divisores funcionaron en 12 segundos.

Fuente

2010-09-27 ChurchSkiz

Por favor ponga espacios alrededor de '=', '<', '=='; de lo contrario, es muy difícil. – Arun

Lea mi respuesta para la misma pregunta: http://stackoverflow.com/questions/3273379/understanding-some-math-relating-to-euler-12/3273405#3273405 :) – AraK

Actualmente se buscan divisores de hasta dividend/2. Puede reducir esto a sqrt(dividend), que es asintóticamente más rápido. Puede ser necesario un caso especial si dividend es cuadrado.

Mi código C++ para el problema 12 (que hace esencialmente lo mismo que el suyo, pero utiliza este límite inferior, y también a cuenta divisores en lugar de almacenarlos en el conjunto) tardará aproximadamente 1 segundo

Fuente

2010-09-27 21:54:44

No entiendo por qué revisar los divisores a sqrt (dividendo) funcionaría. Por ejemplo, los divisores de 28 son 1,2,4,7,14,28. sqrt (28) es 5. ¿Cómo puede encontrar 7 y 14 si deja de verificar en 5? –

@ Jérôme Los divisores vienen en pares (cuando se encuentra el divisor 2, también se encuentra implícitamente el divisor 14; cuando se encuentra 4, se encuentra implícitamente 7). Por lo tanto, puede contar dos divisores por cada divisor menor que la raíz cuadrada. –

for(unsigned long long index=1; index<=dividend/2; index++)

I vea que ha intentado optimizar esto al restringir su ciclo a dividend/2, en lugar de iterar todo el camino hasta dividend. Limitarse a sqrt(dividend) sería mejor (en el sentido de que está comprobando menos divisores).

Además, si se limita por la raíz cuadrada de dividendo, no tiene que buscar divisores duplicados. Eso solo ocurrirá con los números cuadrados, así que simplemente verifique si index == dividend/index, para evitar una inserción duplicada.

Fuente

2010-09-27 21:56:10 Tim

Ligera mejora: en lugar de probar si 'index == dividend/index' puede ser más rápido probar si' index * index == dividend', ya que la multiplicación suele ser más rápida que la división. – LarsH

Supongo que quiso decir eso para reemplazar sqrt (dividendo). Eso funcionaría si calculamos la raíz cuadrada para cada iteración del ciclo. Sin embargo, lo ideal sería calcular el sqrt una vez, guardarlo y luego verificar 'index <= saved_sqrt', que simplemente compara dos números. No es necesario volver a calcular el 'sqrt' para cada iteración, ya que no cambiará (pero el cuadrado de' index' sí cambia en cada iteración). – Tim

No estoy seguro de por qué necesita divisors, una variable de tipo set, en el método NumOfDivisors. ¿Por qué contar numDivisors (con índice hasta sqrt(dividend)) no es suficiente? (set se implementa como un árbol de búsqueda binaria equilibrada, está ralentizando el método). Además, parece que está invocando divisors.insert(..)dos veces.

Fuente

2010-09-27 21:58:19 Arun

Parece que podría obtener algún rendimiento si almacena en caché la cantidad de divisores para un número determinado a medida que avanzaba.

Fuente

2010-09-27 22:01:04 John

Proyecto Euler Problema 12 - C++

Respuesta

Cuestiones relacionadas