elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.
 
Inicio Ayuda Buscar Ingresar Registrarse
27 Mayo 2012, 10:18  


Tema destacado: ¡Aprende hacking con práctica! - WarZone, el wargame de elhacker.net

+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Projecto Euler problema 12 		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Projecto Euler problema 12  (Leído 1,353 veces)
lDanny

Desconectado Desconectado

Mensajes: 21


Ver Perfil
Projecto Euler problema 12
« en: 7 Octubre 2010, 12:51 »
Hola, bueno estoy comenzando en python y vi estos problemas que tienen en Projecto Euler, la verdad que etsan muy bien, bueno el problema 12 que es este

Citar
La secuencia de los numeros del triangulo se genera mediante la adicion de los numeros naturales.
Asi que el 7mo numero triangulo seria 1+2+3+4+5+6+7=28.Los 10 primeros terminos serian:
                         1, 3, 6, 10, 15, 21, 28, 36, 45, 55,.....
Vamos a enumerar los factores de los números triangulo siete primeros:
1:    1
3 :   1, 3
6 :   1, 2, 3 ,6
10 : 1, 2, 5, 10
15 : 1, 3, 5, 15
21 : 1, 3, 7, 21
28 : 1, 2, 4, 7, 14 ,28

Podemos ver que el 28 es el numero primer triangulo de tener mas de cinco divisores.
¿Cual es el valor del numero de primer triangulo de tener mas de 500 divisores?
 
El codigo lo tengo pero no es optimo demora mucho de hecho todavía no me sale cual es el numero con mas de  500 divisores, pero me sale el de 400  ;-)
Es por eso que les digo si pueden resolverlo y que termine en un tiempo aceptable (el mio mas de 30 minutos y no lo resuelve xD) a poder ser en python, aunque pueden ponerlo en cualquier lenguaje.
Gracias.
En línea
lDanny

Desconectado Desconectado

Mensajes: 21


Ver Perfil
Re: Projecto Euler problema 12
« Respuesta #1 en: 7 Octubre 2010, 12:53 »
Bueno para que se animen pongo mi codigo, recien empiezo en pyhton asi que si ven algo que podria hacerse mejor, quitar lineas de codigo que sobran me avisan.

Código
def divisores(n):
	cont=0
	L=[]
	div=2
	turno=-1
	while (n>1):
		if (n%div==0):
			L.append([div,cont])			
			turno+=1
			while True:
				if (n%div==0):
					n=n/div
					cont=cont+1
					L[turno][1]=cont
				else:
					break
		cont=0
		div+=1
	total=1
	for i in range(len(L)):
		total=total*(L[i][1]+1)
	return total
cont=0
adicional=1;
div=0
while True:
	cont = cont +adicional
	adicional+=1
	div = divisores(cont)
	if (div == 501):
		break
print cont,'  ',div
 
 
En línea
Novlucker
Ninja y
Ex-Staff
*
Desconectado Desconectado

Mensajes: 10.239


Yo que tu lo pienso dos veces


Ver Perfil
Re: Projecto Euler problema 12
« Respuesta #2 en: 7 Octubre 2010, 14:01 »
Buenas

Tengo esto ...
Código
import math
cant = input('Ingrese cantidad de divisores: ')
def divisible(n):
    count = 0
    for i in range(1,int(math.sqrt(n))+1):
        if n%i == 0:
            count += 2
    return count
 
temp = 1
suma = 0
while True:
    suma += temp
    temp += 1
    if divisible(suma) > cant:
        print(suma)
        break

En el ejercicio no pide que se impriman los divisores por lo cual no lo agrego, de modo de ahorrarme unos pocos recursos :P
Cronometrando en un Core2Duo E7500 2.93ghz lleva unos 5,2 segundos de media para encontrar el de los 501 divisores :P

Saludos

Saludos
« Última modificación: 7 Octubre 2010, 14:26 por Novlucker » En línea
Contribuye con la limpieza del foro, reporta los "casos perdidos" a un MOD XD
http://twitter.com/novlucker
"Hay dos cosas infinitas: el Universo y la estupidez  humana. Y de la primera no estoy muy seguro."
Albert Einstein
lDanny

Desconectado Desconectado

Mensajes: 21


Ver Perfil
Re: Projecto Euler problema 12
« Respuesta #3 en: 7 Octubre 2010, 16:15 »
Novlucker  gracias por responder, pero creo que mi codigo es mas rapido xDDDDDD(suerte de principiante jejeje).
En mi ordenador el tuyo lo hace en en 33s y el mio en 21s jejeje.
Bueno mi error era que yo no ponia como condicion de parada que fuera mayor a 500 divisores, lo que hacia era que parara cuando exista un numero con 501 divisores exactos  :-[, bueno cambiado esto va bien y lo hace en 21s, pero supongo que se podra hacer mas rapido.
Puedo seguir poniendo en este post ejercicios del projecto euler?.
Gracias
Aqui el code para que lo comprueben.
Código
def divisores(n):
	cont=0
	L=[]
	div=2
	turno=-1
	while (n>1):
		if (n%div==0):
			L.append([div,cont])			
			turno+=1
			while True:
				if (n%div==0):
					n=n/div
					cont=cont+1
					L[turno][1]=cont
				else:
					break
			cont=0
		div+=1
	total=1
	for i in range(len(L)):
		total=total*(L[i][1]+1)
	return total
 
cont=0
adicional=1;
div=0
while True:
	cont = (adicional*(adicional+1))/2
	adicional+=1
	div = divisores(cont)
	if (div > 500):
		break
print cont,'  ',div
 
 
En línea
Novlucker
Ninja y
Ex-Staff
*
Desconectado Desconectado

Mensajes: 10.239


Yo que tu lo pienso dos veces


Ver Perfil
Re: Projecto Euler problema 12
« Respuesta #4 en: 7 Octubre 2010, 16:23 »
Jaja :xD, es que de hecho no me moleste en intentar hacerlo más rápido, simplemente vi que ponías que tu code demoraba media hora, así que cuando vi que este eran 5 segundos no miré más, no tenía tanto tiempo como para quemarme la cabeza con el algoritmo :xD

Excelente entonces si ahora quedo bien :D

Saludos
« Última modificación: 7 Octubre 2010, 16:46 por Novlucker » En línea
Contribuye con la limpieza del foro, reporta los "casos perdidos" a un MOD XD
http://twitter.com/novlucker
"Hay dos cosas infinitas: el Universo y la estupidez  humana. Y de la primera no estoy muy seguro."
Albert Einstein
[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.507


El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Projecto Euler problema 12
« Respuesta #5 en: 16 Octubre 2010, 04:33 »
Yo tengo uno con el cual participe en ese mismo problema:

Código
b=1
a=1
while(1):
    b+=1
    a+=b
    c=0
    for i in range(1,a+1):
        if a%i==0:c+=1
    if c>500:break
print a
 
En línea
H-Sec... Exclusividad Ante Todo (Nos reservamos el Derecho a Admision)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  
Powered by SMF 1.1.16 | SMF © 2006-2008, Simple Machines