[RETO] Project Euler 1

Iniciado por Psyke1, 23 Enero 2013, 12:15 PM

0 Miembros y 2 Visitantes están viendo este tema.

LeandroA

Hola yo la verdad, no entiendo, en primer instancia dice que  3, 5, 6 and 9 son los que estan por devajo de 10, hasta hay todo bien, pero luego sus resultados no me son coherentes con esta lógica (aunque segun la pagina el resultado final es correcto)

pero por ejemplo el ejemplo de Danyfirex, solo mirando los primeros números de multiplos de 3 imprime esto
Citar1             2             4             5             7             8             10            11

y no veo que el 2 sea un múltiplo de 3 , ni el resto de los siguientes.

ami la logica me dice algo asi,
Código (vb) [Seleccionar]

Private Sub Form_Load()
    Dim i As Long
    Dim lSum As Long
    Dim lResult As Long
   
    For i = 1 To 1000000
        lResult = 3 * i
        If lResult >= 1000 Then
            Exit For
        Else
            lSum = lSum + lResult
        End If
       
    Next
   
    For i = 1 To 1000000
        lResult = 5 * i
       
        If lResult >= 1000 Then
            Exit For
        Else
            lSum = lSum + lResult
        End If
       
    Next
   
    Debug.Print lSum
End Sub


porque estoy equivocado???







Danyfirex

Cita de: LeandroA en 23 Enero 2013, 20:38 PM
Hola yo la verdad, no entiendo, en primer instancia dice que  3, 5, 6 and 9 son los que estan por devajo de 10, hasta hay todo bien, pero luego sus resultados no me son coherentes con esta lógica (aunque segun la pagina el resultado final es correcto)

pero por ejemplo el ejemplo de Danyfirex, solo mirando los primeros números de multiplos de 3 imprime esto
y no veo que el 2 sea un múltiplo de 3 , ni el resto de los siguientes.

ami la logica me dice algo asi,


porque estoy equivocado???








hasta ahi vas bien. pero entonces te faltaría quitar los múltiplos de 15.

Psyke1

#12
¡Jajajaja! ¡Menudo lío se ha montado! :laugh: Y eso que estamos con el reto 1. :silbar:

Creo que lo idóneo sería que le pudieramos pasar el número por parámetro, es más genérico.
Y la función debe funcionar SIEMPRE.

Aquí dejo unos ejemplos de llamadas que deben de devolver resultado correcto:
Código (vb) [Seleccionar]

Debug.Print Euler1(1000) '-> 233168
Debug.Print Euler1(0)    '-> 0
Debug.Print Euler1(-983) '-> 0





Aquí dejo mi forma de hacerlo:
Código (vb) [Seleccionar]

Public Static Function PE_1(ByVal lNum As Long) As Long
Dim Q                           As Long
   
   If lNum And &H80000000 Then Exit Function
   
   lNum = lNum - 1
   
   For Q = 3 To lNum Step 3
       PE_1 = PE_1 + Q
   Next Q
   
   For Q = 5 To lNum Step 5
       If Q Mod 3 Then
           PE_1 = PE_1 + Q
       End If
   Next Q
End Function


La próxima vez pondré el reto traducido, y el resultado que debe retornar para evitar confusiones. :rolleyes:

DoEvents! :P

Danyfirex

@Psyke1
creo la primera debería imprimir 234168 en vez de 233168.

100% de acuerdo en poner el reto en Español.

Psyke1

@Danyfirex

http://code.google.com/p/projecteuler-solutions/wiki/ProjectEulerSolutions

Ahí está el resultado de todas las soluciones. ;)

DoEvents! :P

Danyfirex

Cita de: Psyke1 en 23 Enero 2013, 22:13 PM
@Danyfirex

http://code.google.com/p/projecteuler-solutions/wiki/ProjectEulerSolutions

Ahí está el resultado de todas las soluciones. ;)

DoEvents! :P

A pues así pues si. bueno en fin aqui dejo la mia como la pides. no es lo mas optimo pero funciona bien.


Código (vb) [Seleccionar]
Function mul_3_5(numero As Long) As Long
Dim i As Integer
For i = 0 To numero - 1
If (i Mod 3) = 0 Or (i Mod 5) = 0 Then mul_3_5 = mul_3_5 + i
Next i
End Function




Cuando y donde podemos colocar el reto 2?

imoen

En mi opinion este es el codigo mas claro

Al final pongo el visual basic eh xD

bs imoen
Medion Akoya p6624
i-3 370
8 gigas DDR 3 RAM //750 hd 5400
gforce gt425 optimus XDD
Esta es mi casa, mi pueblo , o lo que queda de el aun asi lucharemos ... POR BENALIA....!!

srta imoen

BlackZeroX

#17
mmm el código es fácil de hacer por lo cual yo solo me preocupe por la velocidad... evite calcular el modulo/residuo... ¿Alguien puede probar la velocidad?... se ve que la simplicidad de la función de 79137913 es más veloz.

Versión 1.
Código (vb) [Seleccionar]

Public Function mul3and5(Optional ByVal dwBelowTo As Long = &H3E8&) As Long
Dim i As Long
Dim dwNewMax As Long

   If (dwBelowTo And &H80000000&) Then Exit Function
   
   dwNewMax = (dwBelowTo + &HFFFFFFFF&)
   dwNewMax = (dwNewMax - (dwNewMax Mod &HF&))
   
   For i = &H5& To dwNewMax Step &HF&
       mul3and5 = mul3and5 + i + i + &HFFFFFFFE&
   Next
   For i = &HA& To dwNewMax Step &HF&
       mul3and5 = mul3and5 + i + i + i + &HFFFFFFFB&
   Next
   For i = &HF& To dwNewMax Step &HF&
       mul3and5 = mul3and5 + i + i + &HFFFFFFFD&
   Next
   
   i = (dwNewMax + &H3&):
                   If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H3&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
End Function


Versión 2 (Menos iteraciones, más código).
Código (Vb) [Seleccionar]

Public Function mul3and5_Ver2(Optional ByVal dwBelowTo As Long = &H3E8&) As Long
Dim i As Long
Dim dwNewMax As Long
Dim dwNewMaxFast As Long

   If (dwBelowTo And &H80000000) Then Exit Function

   dwNewMax = (dwBelowTo + &HFFFFFFFF)
   dwNewMax = (dwNewMax - (dwNewMax Mod &HF&))
   
   If (dwNewMax > &H1E&) Then
       dwNewMaxFast = (dwNewMax - (dwNewMax Mod &H1E&))
       For i = &H5& To dwNewMaxFast Step &H1E&
           mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + i + &H1A&
       Next
       For i = &HA& To dwNewMaxFast Step &H1E&
           mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + i + i + i + &H23&
       Next
       For i = &HF& To dwNewMaxFast Step &H1E&
           mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + i + &H18&
       Next
   End If
   
   For i = dwNewMaxFast + &H5& To dwNewMax Step &HF&
       mul3and5_Ver2 = mul3and5_Ver2 + i + i + &HFFFFFFFE&
   Next
   For i = dwNewMaxFast + &HA& To dwNewMax Step &HF&
       mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + &HFFFFFFFB
   Next
   For i = dwNewMaxFast + &HF& To dwNewMax Step &HF&
       mul3and5_Ver2 = mul3and5_Ver2 + i + i + &HFFFFFFFD
   Next

   i = (dwNewMax + &H3&):
                   If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H3&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
End Function


P.D.: ¿Empezare a realizar el segundo... o me espero?.

Dulces Lunas!¡.
The Dark Shadow is my passion.

BlackZeroX

#18
Estos resultados fueron generados desde el IDE ya que no puedo compilar.

Tiempo 7913   978.902 msec
Resultado 7913              233168

Tiempo dany   1,647.315 msec
Resultado dany              233168

Tiempo Spyke1 488.101 msec
Resultado Spyke1            233168

Tiempo BlackZeroX V1        205.944 msec
Resultado BlackZeroX V1     233168

Tiempo BlackZeroX V2        125.884 msec
Resultado BlackZeroX V2     233168


CTiming.cls



Option Explicit
Option Base 0

Sub main()
Const LIM       As Long = 1000&
Const MAX_FOR   As Long = 100000

Dim i   As Long
Dim ct  As New CTiming
Dim obj As Object

   MsgBox "Empezara luego del Ok"

   ct.Reset
   For i = 1 To MAX_FOR
       mul3and5_Ver2 LIM
   Next

   Debug.Print "Tiempo BlackZeroX V2", ct.sElapsed
   Debug.Print "Resultado BlackZeroX V2", mul3and5_Ver2(LIM) & vbCrLf

   ct.Reset
   For i = 1 To MAX_FOR
       mul3and5 LIM
   Next
   Debug.Print "Tiempo BlackZeroX V1", ct.sElapsed
   Debug.Print "Resultado BlackZeroX V1", mul3and5(LIM) & vbCrLf

   ct.Reset
   For i = 1 To MAX_FOR
       mul5and3below1000
   Next
   Debug.Print "Tiempo 7913", ct.sElapsed
   Debug.Print "Resultado 7913", mul5and3below1000() & vbCrLf

   ct.Reset
   For i = 1 To MAX_FOR
       mul_3_5
   Next
   Debug.Print "Tiempo dany", ct.sElapsed
   Debug.Print "Resultado dany", mul_3_5() & vbCrLf

   ct.Reset
   For i = 1 To MAX_FOR
       PE_1 LIM
   Next
   Debug.Print "Tiempo Spyke1", ct.sElapsed
   Debug.Print "Resultado Spyke1", PE_1(LIM) & vbCrLf

End Sub


Private Function mul5and3below1000() As Long
   Dim ct As Long
   Dim aux As Long
   Dim aux2 As Long
   Do
       mul5and3below1000 = mul5and3below1000 + aux + aux2
       ct = ct + 1
       aux = ct + ct + ct
       aux2 = ct + ct + ct + ct + ct
   Loop While aux2 < 1000
   Do
       mul5and3below1000 = mul5and3below1000 + aux
       ct = ct + 1
       aux = ct + ct + ct
   Loop While aux < 1000
   ct = 0
   aux = 0
   Do
       mul5and3below1000 = mul5and3below1000 - aux
       ct = ct + 1
       aux = ct + ct + ct + ct + ct + ct + ct + ct + ct + ct + ct + ct + ct + ct + ct
   Loop While aux < 1000
End Function

Function mul_3_5() As Long
Dim i As Integer
For i = 1 To 999
If (i Mod 3) < 1 Or (i Mod 5) < 1 Then
mul_3_5 = mul_3_5 + i
End If
Next i
End Function

Public Static Function PE_1(ByVal lNum As Long) As Long
Dim Q                           As Long

   If lNum And &H80000000 Then Exit Function

   lNum = lNum - 1

   For Q = 3 To lNum Step 3
       PE_1 = PE_1 + Q
   Next Q

   For Q = 5 To lNum Step 5
       If Q Mod 3 Then PE_1 = PE_1 + Q
   Next Q
End Function

Public Function mul3and5(Optional ByVal dwBelowTo As Long = &H3E8&) As Long
Dim i As Long
Dim dwNewMax As Long

   If (dwBelowTo And &H80000000) Then Exit Function

   dwNewMax = (dwBelowTo + &HFFFFFFFF)
   dwNewMax = (dwNewMax - (dwNewMax Mod &HF&))

   For i = &H5& To dwNewMax Step &HF&
       mul3and5 = mul3and5 + i + i + &HFFFFFFFE
   Next
   For i = &HA& To dwNewMax Step &HF&
       mul3and5 = mul3and5 + i + i + i + &HFFFFFFFB
   Next
   For i = &HF& To dwNewMax Step &HF&
       mul3and5 = mul3and5 + i + i + &HFFFFFFFD
   Next

   i = (dwNewMax + &H3&):
                   If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H3&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5 = mul3and5 + i
End Function

Public Function mul3and5_Ver2(Optional ByVal dwBelowTo As Long = &H3E8&) As Long
Dim i As Long
Dim dwNewMax As Long
Dim dwNewMaxFast As Long

   If (dwBelowTo And &H80000000) Then Exit Function

   dwNewMax = (dwBelowTo + &HFFFFFFFF)
   dwNewMax = (dwNewMax - (dwNewMax Mod &HF&))

   If (dwNewMax > &H1E&) Then
       dwNewMaxFast = (dwNewMax - (dwNewMax Mod &H1E&))
       For i = &H5& To dwNewMaxFast Step &H1E&
           mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + i + &H1A&
       Next
       For i = &HA& To dwNewMaxFast Step &H1E&
           mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + i + i + i + &H23&
       Next
       For i = &HF& To dwNewMaxFast Step &H1E&
           mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + i + &H18&
       Next
   End If

   For i = dwNewMaxFast + &H5& To dwNewMax Step &HF&
       mul3and5_Ver2 = mul3and5_Ver2 + i + i + &HFFFFFFFE
   Next
   For i = dwNewMaxFast + &HA& To dwNewMax Step &HF&
       mul3and5_Ver2 = mul3and5_Ver2 + i + i + i + &HFFFFFFFB
   Next
   For i = dwNewMaxFast + &HF& To dwNewMax Step &HF&
       mul3and5_Ver2 = mul3and5_Ver2 + i + i + &HFFFFFFFD
   Next

   i = (dwNewMax + &H3&):
                   If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H3&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H1&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
   i = (i + &H2&):    If (i >= dwBelowTo) Then Exit Function
   mul3and5_Ver2 = mul3and5_Ver2 + i
End Function



Dulces Lunas!¡.
The Dark Shadow is my passion.

MCKSys Argentina

Pongo el mío, aunque es más lento que el de BlackZeroX:

Código (vb) [Seleccionar]

Public Function Euler_1(ByVal lNum As Long) As Long
Dim Q As Long
Dim S5 As Long

    If lNum& And &H80000000 Then Exit Function

    lNum& = lNum& - &H1
   
    For Q& = &H0 To (lNum& \ &HF)
        Euler_1& = Euler_1& + (&HF * Q&)
    Next Q
   
    S5& = 0
    For Q& = &H1 To (lNum& \ &H5)
        S5& = S5& + (&H5 * Q&)
    Next Q
    Euler_1& = S5& - Euler_1&
   
    For Q& = &H1 To (lNum& \ &H3)
        Euler_1& = Euler_1& + (&H3 * Q&)
    Next Q
End Function


En un EXE compilado, los tiempos me dan:


Tiempo BlackZeroX V2        55.732 msec
Resultado BlackZeroX V2     233168

Tiempo BlackZeroX V1        39.737 msec
Resultado BlackZeroX V1     233168

Tiempo 7913   152.260 msec
Resultado 7913              233168

Tiempo dany   1,627.764 msec
Resultado dany              233168

Tiempo Spyke1 175.199 msec
Resultado Spyke1            233168

Tiempo MCKSys 98.207 msec
Resultado MCKSys            233168


PD: Mirando el ASM generado, veo que el secreto está en no usar multiplicaciones ni divisiones. Aunque no es sencillo hallar un algoritmo con eso (y que sea diferente al de BlackZeroX!!  ;D)
MCKSys Argentina

"Si piensas que algo está bien sólo porque todo el mundo lo cree, no estás pensando."