2. Subllistes creixents

Avís

Per a resoldre aquest exercici no es poden fer servir iteracions (ni for ni while ), només funcions recursives.

2.1. Funció divideix_creixents (2 punts)

Utilitzant la recursivitat, dissenyeu la funció següent i deseu-la al mòdul creixents (fitxer creixents.py), la qual divideix una llista de nombres en subllistes creixents:

creixents.divideix_creixents(L)
Paràmetres:

L (list) – llista no buida de nombres

Retorna:

descomposició de L en subllistes estrictament creixents

Tipus de retorn:

llista de subllistes de nombres

Formalment, essent la llista retornada \([l_0, l_1, \dots , l_n]\), es compleix que:

  1. \(l_0 + l_1 + \dots + l_n = L\), és a dir, la concatenació de les subllistes coincideix amb L.

  2. \(l_i[k-1] < l_i[k] \, , \, \forall k = 1 \dots len(l_i)-1 \, , \, \forall i = 0 \dots n\), és a dir, els elements de cada subllista estan ordenats creixentment.

  3. \(l_i[-1] \geq l_{i+1}[0] \, , \, \forall i = 0 \dots n-1\), és a dir, es divideix en el menor nombre de subllistes creixents possible.

Per exemple,

>>> from creixents import divideix_creixents

>>> divideix_creixents([1])
[[1]]
>>> divideix_creixents([1, 4, 7, 88, 103])
[[1, 4, 7, 88, 103]]
>>> divideix_creixents([6, 79, 38, 62, 1004])
[[6, 79], [38, 62, 1004]]
>>> divideix_creixents([100, 20, 2, 4, 47, 8, 9, 100, 2, 2, 123, 44]) 
[[100], [20], [2, 4, 47], [8, 9, 100], [2], [2, 123], [44]]

Disposeu de més jocs de prova en el fitxer tests-creixents.txt.