Longueur maximale d'intervalle équilibré

On considère une liste bits constituée uniquement de 0 et 1. Écrire une fonction telle que l_max_equilibree(bits) renvoie la longueur maximale d'une tranche qui contient autant de 0 que de 1.

Exemples

🐍 Console Python

>>> bits = [0, 0, 1, 0, 0, 0, 1, 1, 0, 0]
>>> l_max_equilibree(bits)
6

En effet, la tranche [1, 0, 0, 0, 1, 1] est équilibrée et de longueur maximale.

🐍 Console Python

>>> bits = [1, 1, 1, 1]
>>> l_max_equilibree(bits)
0

En effet, la tranche [] est équilibrée et de longueur maximale.

🐍 Console Python

>>> bits = [1, 0, 1, 0, 1]
>>> l_max_equilibree(bits)
4

En effet, la tranche [1, 0, 1, 0] est équilibrée et de longueur maximale. Il y a également [0, 1, 0, 1] équilibrée et aussi de longueur maximale.

On attend un algorithme qui fait une simple boucle. Il faudra sauvegarder une information utile à chaque tour de boucle.

Lancerdef secretpy-undlpy-undmaxpy-undequilibree(bits):bksl-nl ipy-undbonuspy-und1 = [0]bksl-nl ipy-undbonuspy-und0 = [0]bksl-nl lpy-undmax = 0bksl-nl delta = 0bksl-nl for i, x in enumerate(bits):bksl-nl if x == 1:bksl-nl delta += 1bksl-nl else:bksl-nl delta -= 1bksl-nl if delta > len(ipy-undbonuspy-und1) - 1:bksl-nl ipy-undbonuspy-und1.append(i)bksl-nl elif -delta > len(ipy-undbonuspy-und0) - 1:bksl-nl ipy-undbonuspy-und0.append(i)bksl-nl elif delta >= 0:bksl-nl if i - ipy-undbonuspy-und1[delta] > lpy-undmax:bksl-nl lpy-undmax = i - ipy-undbonuspy-und1[delta]bksl-nl else: # delta <= 0:bksl-nl if i - ipy-undbonuspy-und0[-delta] > lpy-undmax:bksl-nl lpy-undmax = i - ipy-undbonuspy-und0[-delta]bksl-nl return lpy-undmaxbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlassert lpy-undmaxpy-undequilibree([0, 0, 1, 0, 0, 0, 1, 1, 0, 0]) == 6bksl-nlbksl-nlassert lpy-undmaxpy-undequilibree([1, 1, 1, 1]) == 0bksl-nlbksl-nlassert lpy-undmaxpy-undequilibree([1, 0, 1, 0, 1]) == 4bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlfrom random import getrandbitsbksl-nlfor py-und in range(10):bksl-nl bits = bin(getrandbits(10py-strpy-str5+1))[3:]bksl-nl attendu = secretpy-undlpy-undmaxpy-undequilibree(bits)bksl-nl assert lpy-undmaxpy-undequilibree(bits) == attendubksl-nlbksl-nl Valider ∞/∞ TéléchargerTéléverser RechargerSauvegarder

def lpy-undmaxpy-undequilibree(bits):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlassert lpy-undmaxpy-undequilibree([0, 0, 1, 0, 0, 0, 1, 1, 0, 0]) == 6bksl-nlbksl-nlassert lpy-undmaxpy-undequilibree([1, 1, 1, 1]) == 0bksl-nlbksl-nlassert lpy-undmaxpy-undequilibree([1, 0, 1, 0, 1]) == 4bksl-nlbksl-nldef lpy-undmaxpy-undequilibree(bits):bksl-nl ipy-undbonuspy-und1 = [0]bksl-nl ipy-undbonuspy-und0 = [0]bksl-nl lpy-undmax = 0bksl-nl delta = 0bksl-nl for i, x in enumerate(bits):bksl-nl if x == 1:bksl-nl delta += 1bksl-nl else:bksl-nl delta -= 1bksl-nl if delta > len(ipy-undbonuspy-und1) - 1:bksl-nl ipy-undbonuspy-und1.append(i)bksl-nl elif -delta > len(ipy-undbonuspy-und0) - 1:bksl-nl ipy-undbonuspy-und0.append(i)bksl-nl elif delta >= 0:bksl-nl if i - ipy-undbonuspy-und1[delta] > lpy-undmax:bksl-nl lpy-undmax = i - ipy-undbonuspy-und1[delta]bksl-nl else: # delta <= 0:bksl-nl if i - ipy-undbonuspy-und0[-delta] > lpy-undmax:bksl-nl lpy-undmax = i - ipy-undbonuspy-und0[-delta]bksl-nl return lpy-undmaxbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlassert lpy-undmaxpy-undequilibree([0, 0, 1, 0, 0, 0, 1, 1, 0, 0]) == 6bksl-nlbksl-nlassert lpy-undmaxpy-undequilibree([1, 1, 1, 1]) == 0bksl-nlbksl-nlassert lpy-undmaxpy-undequilibree([1, 0, 1, 0, 1]) == 4bksl-nlbksl-nl

A

Commentaires

{{ IDE('exo_corr') }}

Z

Indice 1

On pourra calculer pour chaque indice la différence delta entre le nombre de 1 et le nombre de 0 depuis le début de la liste.

Lorsqu'on rencontre à nouveau une même valeur de delta, on déduit une tranche équilibrée.

Indice 2

On va alors stocker le premier indice où l'on rencontre delta. On pourra noter i_bonus_1[k] le premier indice où delta est égal à +k, et i_bonus_0[k] le premier indice où delta est égal à -k.

On pourra utiliser un dictionnaire i_bonus, ou deux listes i_bonus_1 et i_bonus_0.

Indice 3

On pourra compléter le code

```python def l_max_equilibree(bits): i_bonus_1 = [0] i_bonus_0 = [0] l_max = 0 delta = 0 for i, x in enumerate(bits): if x == 1: delta = ... else: delta = ... if delta > len(i_bonus_1) - 1: i_bonus_1.append(...) elif ...: i_bonus_0.append(...) elif delta >= 0: if i - i_bonus_1[delta] > l_max: l_max = ... else: # delta <= 0: if ...: ... return ...

```