J'ai rejoint le cours en ligne de Standford sur la conception d'algorithmes et je suis en train de résoudre la première question de programmation.
El fichier contient les 100 000 entiers compris entre 1 et 100 000. (y compris les deux) dans un ordre aléatoire (aucun entier n'est répété). Votre tâche tâche est de trouver le nombre d'inversions dans le fichier donné (chaque ligne a un seul nombre entier entre 1 et 100 000). Supposons que votre tableau aille de 1 à 100 000 et la i-ème ligne du fichier vous donne la i-ème entrée du tableau. tableau.
Mise à jour : J'ai constaté que mon code ne fonctionne que pour le cas 2^n. Le problème est dans le code, pas dans Python. J'ai mis à jour le code, maintenant il fonctionne bien et j'ai fait le quiz. Merci à tous ceux qui ont aidé
Le code fixe est :
def merge_count_split (a, b):
c = []
inv = 0
i=0
j=0
for k in range( len(a) + len(b) ):
if i < len(a) and j < len(b):
if a[i] < b[j]:
c.append(a[i])
i += 1
elif a[i] > b[j]:
c.append(b[j])
inv += len(a)-i
j += 1
elif i == len(a):
c.append(b[j])
j += 1
elif j == len(b):
c.append(a[i])
i += 1
return c, inv
def count_inv (data):
n = len(data)
if n == 1:
return data, 0
a, x = count_inv(data[:n/2])
b, y = count_inv(data[n/2:])
c, z = merge_count_split(a,b)
return c, x + y + z
with open('IntegerArray.txt') as f:
array = [int(line) for line in f]
print count_inv(array)[0]Ce programme fonctionne bien pour les petits tableaux, mais pour le grand tableau de la question, il imprime un tableau de 65536 les nombres dans le bon ordre, et non 100000, comme je m'y attendais. Il omet des chiffres à des endroits aléatoires.
Quelle est la raison de ce comportement inattendu de python ?
