Projet euler en python (# 53)

Question

Donc j'apprends Python alors je suis en train de vivre des problèmes de projet euler. Et je ne suis pas sûr si c'est un problème python que je suis, ou juste moi être retardé, mais je semble obtenir la mauvaise réponse pour le problème 53. Voici un lien vers le problème

et ceci est mon code:

 

from math import factorial 

def ncr(n,r): 
    return (factorial(n)/(factorial(r)*factorial(n-r))) 

i = 0 

for x in range(1,100): 
    for y in range(0,x): 
     if(ncr(x,y) > 1000000): 
      i=i+1 

print i 
 

Je reçois 3982 qui est apparemment la mauvaise réponse. Est-ce que quelque chose de mal que je fais est spécifique à python?

Answer 1

range(a, b) n'inclut pas b.

Answer 2

Je pense que votre code est correct, cependant, vous devez itérer x à 100 inclus, vous devez donc utiliser

for x in range(1,101): 

espoir qui aide. Roches d'Euler!

Answer 3

Notez que n est supérieur ou égal à 1 et inférieur ou égal à 100. Actuellement, votre n va de 1 à 99. Vous pouvez aussi utiliser xrange.

from math import factorial 

def ncr(n,r): 
    return (factorial(n)/(factorial(r)*factorial(n-r))) 

i = 0 

for x in range(1,101): 
    for y in range(1,x+1): 
     if(ncr(x,y) > 1000000): 
      i=i+1 

print i 

Answer 4

Si vous êtes débutant, je profite de cette occasion, compte tenu de la nature d'Euler projet, pour donner des solutions alternatives de codage, qui est autonome et démontre l'approche de la table de recherche pour accélérer les fonctions récursives et enregistrer les réponses au dictionnaire et en utilisant le len comme compte.

Espérons que le 4075 est la bonne réponse!

from __future__ import division 
factorials={} 

def factorial(n): 
    """ factorial from lookup table ready or generate it to there """ 
    if n not in factorials: 
     factorials[n]=1 if n==0 else n*factorial(n-1) 
    return factorials[n] 

def ncr(n,r): 
    return (factorial(n)/(factorial(r)*factorial(n-r))) 

bigones= [(x,y) for x in range(1,1+100) for y in range(x) if ncr(x,y) > 1000000 ] 

print len(bigones) 

Answer 5

Compte tenu de l'entrée de la problem specification: « Ce n'est que n = 23, qu'une valeur est supérieure à un million », vous pouvez faire la gamme pour l'extérieur 23-101:

for x in range(23,101): 
    ... 

De plus, n sur k peut être calculé plus rapidement sans générer les trois factorielles:

def noverk(n,k): 
    noverk=1 
    if 2*k < n: 
    k=n-k; 
    for i in range(1,n-k+1): 
    noverk *= (i+k) 
    noverk /= i 
    return noverk;