Les n termes du triangle sont donnés par tn = ½ n (n + 1). Les 10 premiers termes sont
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Est.
Après avoir converti l'alphabet du mot en valeur numérique, la somme est prise. Cette somme est appelée "valeur du mot". Par exemple, SKY vaut 19 + 11 + 25 = 55 = t10. La valeur du mot est un nombre triangulaire. À un moment donné, le mot s'appelle un triangle.
Environ 2 000 mots anglais sont écrits dans le fichier texte de 16 Ko words.txt. Combien de mots triangulaires y a-t-il? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042
La politique de réponse est la suivante. 1.Faites un ensemble de triangles pour référence. 2. Calculez la valeur du mot. 3. Déterminez si la valeur calculée est incluse dans l'ensemble des triangles. 4. S'il est déterminé qu'il est inclus, ajoutez 1 à la variable ans.
def main():
words = file2list('p042_words.txt')
MAX = max_length(words) * 26
tri = tri_dict(MAX)
ans = 0
for word in words:
if word2num(word) in tri:
ans += 1
print ans
file2list est une fonction qui ouvre un fichier et répertorie les chaînes lues. Si vous passez une fonction à la liste, cela semble être plus polyvalent, mais c'est ennuyeux, donc ce n'est pas pris en charge.
def file2list(filename):
file = open(filename)
ret = file.read().replace('"','').split(',')
file.close()
return ret
Une fonction qui calcule le nombre de caractères dans une liste de mots de mots pour déterminer la valeur maximale pour créer un ensemble de triangles.
def max_length(words):
max_len = 0
for word in words:
if len(word) > max_len:
max_len = len(word)
return max_len
Une fonction qui renvoie un objet de type dictionnaire qui stocke le nombre de triangles inférieur ou égal à la valeur maximale spécifiée.
def f(n):
return n * (n+1) / 2
def tri_dict(max):
n=1
tri = {}
while f(n)<=max:
tri[f(n)] = True
n+=1
return tri
Fonctions qui numérisent des mots, etc. J'aurais dû utiliser réduire. Notez que ord est une fonction intégrée qui renvoie un entier représentant un point de code Unicode si la chaîne est un objet Unicode, et la valeur de cet octet si la chaîne est une chaîne de 8 bits, pour une chaîne donnée de longueur 1. Dans alfa2num, la valeur de l'octet de "A" est 65, donc la valeur obtenue en soustrayant 64 est renvoyée.
def alfa2num(s):
return ord(s) - 64
def word2num(word):
return sum([alfa2num(s) for s in word])
Recommended Posts