Honlap címe

Előző - #39 Collatz Sequence | Tartalomjegyzék | Következő - #41 ROT 13 titkosítás

40. GYAKORLAT: KÉT RENDEZETT LISTA ÖSSZEVONÁSA

mergeTwoLists([1, 3, 6], [5, 7, 8, 9]) → [1, 3, 5, 6, 7, 8, 9]

Az egyik leghatékonyabb rendezési algoritmus az összevont rendezési algoritmus. Az összevonási rendezésnek két fázisa van: a felosztási és az egyesítési fázis. Ebben a könyvben nem merülünk el ebbe a fejlett algoritmusba. A második felére azonban írhatunk kódot: két előre rendezett egész számlistát egyetlen rendezett listává egyesítünk.

Gyakorlat leírása

Írjon egy mergeTwoLists()függvényt két paraméterrel list1és list2. Az ezekhez a paraméterekhez átadott számok listái már a legkisebbtől a legnagyobbig rendezett sorrendben vannak. A függvény egyetlen rendezett listát ad vissza a két listából származó összes számból.

Ezt a függvényt egy kódsorba írhatja a Python sorted()függvény használatával:

vissza rendezve (1. lista + 2. lista)

Ez azonban meghiúsítaná a gyakorlat célját, ezért ne használja a sorted()funkciót vagy sort() módszert a megoldás részeként.

Ezek a Python- assertutasítások leállítják a programot, ha feltételük False. Másolja őket a megoldási program aljára. Az Ön megoldása akkor helyes, ha a következő assertállítások feltételei mind igazak :

assert mergeTwoLists([1, 3, 6], [5, 7, 8, 9]) == [1, 3, 5, 6, 7, 8, 9]

assert mergeTwoLists([1, 2, 3], [4, 5]) == [1, 2, 3, 4, 5]

assert mergeTwoLists([4, 5], [1, 2, 3]) == [1, 2, 3, 4, 5]

assert mergeTwoLists([2, 2, 2], [2, 2, 2]) == [2, 2, 2, 2, 2, 2]

assert mergeTwoLists([1, 2, 3], []) == [1, 2, 3]

assert mergeTwoLists([], [1, 2, 3]) == [1, 2, 3]

Próbáljon megoldást írni a leírásban szereplő információk alapján. Ha továbbra is problémái vannak ennek a gyakorlatnak a megoldásával, további tippekért olvassa el a Megoldástervezés és a Különleges esetek és Gotchák című részt.

Előfeltételek: listák, while ciklusok, logikai operátorok, append(), for ciklusok, range()két argumentummal,len()

Megoldás tervezése

Az egész számok listái, már rendezett sorrendben, paraméterként list1és list2ként kerülnek átadásra a függvénynek . Az algoritmus két változóval kezdődik, i1 és i2, amelyek mindketten a 0megfelelő listájuk indexével kezdődnek. Létrehozunk egy üres listát is egy nevű változóban, resultamely a két lista egyesített eredményeit tárolja.

A cikluson belül whilea kód a következőket teszi:

Nézd meg azokat a számokat, amelyekre i1és i2 mutat.
A két szám közül a kisebbet fűzze hozzá result.
Ha i1a szám hozzá lett fűzve, növelje a lépést, hogy a list1i1 következő számára mutasson . Ellenkező esetben növelje a lépést, hogy a következő számra mutasson .i2list2
Ismételje addig, amíg az egyik i1vagy az i2 túllép a lista végén.

Például a 40-1. ábra a ciklus első három iterációját mutatja listák [1, 3, 6]és [5, 7, 8, 9] egyesítésekor .

Tekintsd ezt a kódot aszimmetrikus cipzárnak: az i1 és i2a változók folyamatosan mozognak a megfelelő listáik mentén, hozzáfűzve az értékeket az eredményhez. Amikor valamelyik i1vagy i2eléri a listája végét, a másik lista többi része hozzáfűződik az eredményhez . Ez resulta lista tartalmazza az összes számot a listában list1és a list2- ben rendezett sorrendben, így a függvény ezt adja vissza.

Különleges esetek és Gotchák

Ne feledje, hogy bár a list1és list2 paramétereknek rendezett listáknak kell lenniük, nem kell azonos hosszúságúaknak lenniük.

Ha a lista argumentumai közül bármelyik mergeTwoLists() nincs rendezve, a függvény egy összevont listát ad vissza, amely szintén nincs rendezett sorrendben. Ennél a gyakorlatnál azonban azt feltételezzük, hogy ezt mergeTwoLists() mindig érvényes argumentumokkal hívjuk meg.

Most próbáljon meg egy megoldást írni az előző szakaszok információi alapján. Ha továbbra is problémái vannak a gyakorlat megoldásával, olvassa el a Megoldássablon részt további tippekért.

Megoldás sablon

Próbáljon először megoldást írni a semmiből. De ha nehézségei vannak, akkor a következő részprogramot használhatja kiindulási helynek. Másolja ki a következő kódot a https://invpy.com/mergetwolists-template.py webhelyről , és illessze be a kódszerkesztőbe. Cserélje ki az aláhúzást kódra, hogy működő programot készítsen:

def mergeTwoLists(lista1, lista2):

# Hozzon létre egy üres listát a végső rendezett eredmények tárolására:

eredmény = ____

# Indítsa el az i1-et és az i2-t a 0 indexnél, a list1 és list2 elején:

i1 = ____

i2 = ____

# Folytassa az i1 és i2 felfelé mozgását, amíg az egyik el nem éri a lista végét:

míg i1 < len(____) és ____ < len(list2):

# Adja hozzá a két aktuális elem közül a kisebbet az eredményhez:

if lista1[____] < lista2[____]:

# A lista1 aktuális elemének hozzáadása az eredményhez:

result.append(____[i1])

# Növekedés i1:

i1 += ____

más:

# Adja hozzá a list2 aktuális elemét az eredményhez:

result.append(____[i2])

# Növekedés i2:

i2 += ____

# Ha az i1 nincs a lista1 végén, adja hozzá a list1 többi elemét:

if i1 < len(____):

j esetén tartományban(i1, len(lista1)):

result.append(____[j])

# Ha az i2 nincs a lista2 végén, adja hozzá a fennmaradó elemeket a list2-ből:

if i2 < len(____):

for j in range(i2, len(list2)):

result.append(____[j])

# Return the merged, sorted list:

return result

The complete solution for this exercise is given in Appendix A and https://invpy.com/mergetwolists.py. You can view each step of this program as it runs under a debugger at https://invpy.com/mergetwolists-debug/.