Résolution de problème

1) Énonce et formalisation

La suite d’immeubles sera modélisée par un tableau d’entiers strictement positifs représentants la hauteur d’un immeuble ou le nombre d’étages.

#représentation de la suite d'immeubles
suiteImmeubles=[5,1,8,2,7,6,10,3,9,11]

En détruisant les immeubles en gris nous avons une solution au problème posé pour cet exemple. Il faut donc extraire de la suite d’immeubles une plus grande sous suite croissante.

#représentation de la sous suite d'immeubles à conserver
sousSuiteImmeubles=[1,2,7,9,11]

Nous allons pas à pas vers une résolution naïve (force brute)  du problème

• rechercher le nombre de sous suites possibles .
• Énumérer toutes les sous suites
• Trouver une plus grande parmi celles qui sont croissantes
• Visualiser le résultat obtenu en option

2) une suite d’entier est elle croissante ?

Nous allons coder une fonction python : croissante()

Une liste de type list en entrée

Une valeur booléenne en sortie

def croissante(suite:list)->bool:
    """renvoi True si la liste est croissante False sinon"""
    for i in range(len(suite)-1):
        if suite[i]>=suite[i+1]:
            return False
    return True

La fonction est documentée avec les arguments de l’entrée et de la sortie

Un docsstring a été ajouté pour avoir une aide sur la fonction

Pour avoir une aide sur la fonction il suffit d’utiliser la fonction help()

3)Énumérons toutes les sous suites possibles d’une suite

2 choix possibles pour chacun des immeubles de la suite (conserver ou démolir)

donc 2ⁿ  choix possibles.

Un nombre binaire k de n bits (avec un bit à 1 pour conserver et à 0 pour démolir) peut représenter une sous suite.

Exemple avec la suite [1,2,6,5] on souhaite coder la sous suite [1,2]

On écrira 1100 pour conserver 1 et 2 et démolir 6 et 5.

La suite est constituée de 4 immeubles on donc 2⁴ sous suites au total soit 16

La sous suite obtenue après démolition est représentée par [1,2]

Nous allons coder une fonction sous_suite()

En entrée 2 arguments une suite (liste x) et un entier (k de type int) représentant une sous suite

En sortie une variable b de type list représentant la sous suite

def sous_suite(x:list,k:int)->list:
    """ n est la longueur de la suite x 
        l est le nombre de sous suites
        """      
    n=len(x)
    l=2**n
    a=list(np.binary_repr(k, width=n))
    b=[]
    for j in range(n):
        if a[j]=='1':
            b.append(int(x[j]))
    return b

Un test de la fonction

à vous de faire d’autres tests et de mieux documenter la fonction pour la comprendre

On peut maintenant exploiter notre fonction pour lister toutes les sous suites possibles

suiteImmeubles=[1,2,6,3]

for l in range(2**(len(suiteImmeubles))):
    b=sous_suite(suiteImmeubles,l)
    print(l,";",b)

Un test:

4)Trouver une plus grande sous suite parmi celles qui sont croissantes

à vous de jouer pour finaliser la résolution

corrigé

def une_plus_grande_sous_suite(x):
    n=len(x)
    l=2**n
    longest=0
    for k in range (l):  
        b=sous_suite(x,k)
        if croissante(b):
            if len(b)>longest:
                k_int=k
                longest=len(b)
    solution=sous_suite(x,k_int)
    return solution

On teste la fonction sur des listes aléatoires

import random
import time

debut=time.time()

T=list(range(10))
random.shuffle(T)
print(T)

t=une_plus_grande_sous_suite(T)
duree=-debut+time.time()
print(t)

print(duree,"s")

Correction progressive et explication du code

Les fonctions utilisées ne sont pas forcément codées de la même manière

Résolution et test de la méthode naïve utilisée