Ich habe mich am Standford Online-Kurs über Algorithmenentwurf beteiligt und löse jetzt die erste Programmierfrage.
Le site Datei enthält alle 100.000 ganzen Zahlen zwischen 1 und 100.000 (einschließlich beider) in einer zufälligen Reihenfolge (keine ganze Zahl wird wiederholt). Ihre Aufgabe ist es, die Anzahl der Invertierungen in der gegebenen Datei zu finden (jede Zeile hat eine einzelne ganze Zahl zwischen 1 und 100.000). Nehmen Sie an, dass Ihr Array von 1 bis 100.000 und die i-te Zeile der Datei gibt Ihnen den i-ten Eintrag in der Array.
Update: Ich habe festgestellt, dass mein Code nur für den Fall 2^n funktioniert. Das Problem liegt im Code, nicht in Python. Ich habe den Code aktualisiert, jetzt funktioniert er gut und ich habe das Quiz gemacht. Danke an alle, die geholfen haben
Der feste Code lautet:
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]Dieses Programm funktioniert gut für kleine Arrays, aber für das große Array aus der Frage gibt es Array von 65536 Zahlen in der richtigen Reihenfolge, nicht 100000, wie ich erwarte. Er lässt Zahlen an zufälligen Stellen aus.
Was ist der Grund für dieses unerwartete Verhalten von python?
