{"id":253,"date":"2021-11-22T22:23:51","date_gmt":"2021-11-22T21:23:51","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/?p=253"},"modified":"2021-12-06T22:45:18","modified_gmt":"2021-12-06T21:45:18","slug":"resolution-de-probleme","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/?p=253","title":{"rendered":"R\u00e9solution de probl\u00e8me"},"content":{"rendered":"

<\/p>\n\n\n

1) \u00c9nonce et formalisation<\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n

La suite d\u2019immeubles sera mod\u00e9lis\u00e9e par un tableau d\u2019entiers strictement positifs repr\u00e9sentants la hauteur d\u2019un immeuble ou le nombre d’\u00e9tages.<\/p>\n\n\n\n

#repr\u00e9sentation de la suite d'immeubles\nsuiteImmeubles=[5,1,8,2,7,6,10,3,9,11]<\/pre>\n\n\n\n
En d\u00e9truisant les immeubles en gris nous avons une solution au probl\u00e8me pos\u00e9 pour cet exemple. Il faut donc extraire de la suite d’immeubles une<\/strong> plus grande sous suite croissante.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
#repr\u00e9sentation de la sous suite d'immeubles \u00e0 conserver\nsousSuiteImmeubles=[1,2,7,9,11]<\/pre>\n\n\n
Nous allons pas \u00e0 pas vers une r\u00e9solution na\u00efve (force brute)  du probl\u00e8me<\/b><\/p>\n
    \n
  • rechercher le nombre de sous suites possibles .<\/li>\n
  • \u00c9num\u00e9rer toutes les sous suites<\/li>\n
  • Trouver une plus grande parmi celles qui sont croissantes<\/li>\n
  • Visualiser le r\u00e9sultat obtenu en option<\/li>\n<\/ul>\n\n\n
    2) une suite d’entier est elle croissante<\/strong> ?<\/p>\n\n\n\n
    Nous allons coder une fonction python : croissante()<\/strong><\/p>\n\n\n\n
    Une liste de type list en entr\u00e9e<\/p>\n\n\n\n
    Une valeur bool\u00e9enne en sortie<\/p>\n\n\n\n
    def croissante(suite:list)->bool:\n    \"\"\"renvoi True si la liste est croissante False sinon\"\"\"\n    for i in range(len(suite)-1):\n        if suite[i]>=suite[i+1]:\n            return False\n    return True<\/pre>\n\n\n\n
    La fonction est document\u00e9e avec les arguments de l’entr\u00e9e et de la sortie<\/p>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    Un docsstring a \u00e9t\u00e9 ajout\u00e9 pour avoir une aide sur la fonction<\/p>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    Pour avoir une aide sur la fonction il suffit d’utiliser la fonction help()<\/p>\n\n\n\n
    \"\"
    quelques tests sur la fonction:<\/figcaption><\/figure>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    3)\u00c9num\u00e9rons toutes les sous suites possibles d’une suite<\/strong><\/p>\n\n\n\n
    2 choix possibles pour chacun des immeubles de la suite (conserver ou d\u00e9molir)<\/p>\n\n\n\n
    donc 2n<\/sup>  choix possibles.<\/p>\n\n\n\n
    Un nombre binaire k de n bits (avec un bit \u00e0 1 pour conserver et \u00e0 0 pour d\u00e9molir) peut repr\u00e9senter une sous suite.<\/p>\n\n\n\n
    Exemple avec la suite [1,2,6,5] on souhaite coder la sous suite [1,2]<\/p>\n\n\n\n
    On \u00e9crira 1100   pour conserver 1 et 2 et d\u00e9molir 6 et 5.<\/p>\n\n\n\n
    La suite est constitu\u00e9e de 4 immeubles on donc 24<\/sup> sous suites au total soit 16<\/p>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    La sous suite obtenue apr\u00e8s d\u00e9molition est repr\u00e9sent\u00e9e par [1,2]<\/p>\n\n\n\n
    Nous allons coder une fonction sous_suite()<\/p>\n\n\n\n
    En entr\u00e9e 2 arguments une suite (liste x)  et un entier (k de type int)  repr\u00e9sentant une sous suite<\/p>\n\n\n\n
    En sortie une variable b de type list repr\u00e9sentant la sous suite<\/p>\n\n\n\n
    def sous_suite(x:list,k:int)->list:\n    \"\"\" n est la longueur de la suite x \n        l est le nombre de sous suites\n        \"\"\"      \n    n=len(x)\n    l=2**n\n    a=list(np.binary_repr(k, width=n))\n    b=[]\n    for j in range(n):\n        if a[j]=='1':\n            b.append(int(x[j]))\n    return b<\/pre>\n\n\n\n
    Un test de la fonction<\/p>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    \u00e0 vous de faire d’autres tests et de mieux documenter la fonction pour la comprendre<\/p>\n\n\n\n
    On peut maintenant exploiter notre fonction pour lister toutes les sous suites possibles<\/p>\n\n\n\n
    suiteImmeubles=[1,2,6,3]\n\nfor l in range(2**(len(suiteImmeubles))):\n    b=sous_suite(suiteImmeubles,l)\n    print(l,\";\",b)<\/pre>\n\n\n\n
    Un test:<\/p>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    4)Trouver une plus grande sous suite parmi celles qui sont croissantes<\/p>\n\n\n\n
    \u00e0 vous de jouer pour finaliser la r\u00e9solution <\/p>\n\n\n\n
    corrig\u00e9<\/p>\n\n\n\n
    def une_plus_grande_sous_suite(x):\n    n=len(x)\n    l=2**n\n    longest=0\n    for k in range (l):  \n        b=sous_suite(x,k)\n        if croissante(b):\n            if len(b)>longest:\n                k_int=k\n                longest=len(b)\n    solution=sous_suite(x,k_int)\n    return solution<\/pre>\n\n\n\n
    On teste la fonction sur des listes al\u00e9atoires<\/p>\n\n\n\n
    import random\nimport time\n\ndebut=time.time()\n\nT=list(range(10))\nrandom.shuffle(T)\nprint(T)\n\nt=une_plus_grande_sous_suite(T)\nduree=-debut+time.time()\nprint(t)\n\nprint(duree,\"s\")<\/pre>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    Correction progressive et explication du code<\/p>\n\n\n\n
    Les fonctions utilis\u00e9es ne sont pas forc\u00e9ment cod\u00e9es de la m\u00eame mani\u00e8re<\/p>\n\n\n\n
    R\u00e9solution et test de la m\u00e9thode na\u00efve utilis\u00e9e<\/p>\n\n\n\n