Devoir commun Python: Exercices avec des listes
L'usage de la calculatrice n'est pas autorisé
Durée: 60 min
Exercice 1
Il y a fort longtemps, existait un continent où vivait une espèce rare : le Prolosaure. Ce continent était composé de N montagnes de différentes altitudes sur lesquelles les paisibles prolosaures vivaient en paix.
Un jour, une tempête se déchaîna et entraîna une montée globale du niveau de l’eau. Les prolosaures se demandent si une partie de leur foyer a disparu sous les eaux.
On vous donne une liste de nombres représentant les altitudes des différentes montagnes qui composent le continent ainsi que l’altitude globale atteinte par la montée des eaux.
Écrivez un programme qui indique si au moins une montagne a été submergée par les flots.
LA est la liste des attitudes.
NE est le niveau global atteint par les eaux.
for e in LA:
if e<=NE:
return True
return False
Exercice 2
On vous donne une liste de 0 et de 1. Écrire un programme qui détermine la position avant laquelle il faut couper cette liste pour que le nombre de 1 à gauche de cette coupure plus le nombre de 0 à droite soit le plus petit possible.
Les positions sont comptées à partir de 0. Pour couper tout à gauche, on coupe donc avant la position 0.
Soit T un tableau de 0 et de 1 (mélangés, aléatoires)
# une fonction qui compte le nombre de 1 jusqu'à une position n (non incluse)
def nb1gauche(T,n):
nb1=0
for i in range(n):
if T[i]==1:
nb1=nb1+1
return nb1
# une fonction qui compte le nombre de 0 à partir d'une position n (incluse)
def nb0droite(T,n):
for i in range(n,len(T)):
if T[i]==0:
nb0=nb0+1
return nb0
# On cherche le minimum de la somme de ces fonctions
val=nb0droite(T,0)
indmin=0
for i in range(len(Tab)):
if nb0droite(T,i)+nb1gauche(T,i)<val:
indmin=i
val=nb0droite(T,i)+nb1gauche(T,i)
print(indmin)
Exercice 3 : Hauteur des jetons dans une grille de puissance 4.
On donne une grille de Puissance 4 : un tableau de taille N par M, de 0 et de 1, où les 1 sont des jetons, de couleur indifférenciée, et les 0 les trous ; vous devez trouver la hauteur maximale atteinte par les jetons. Pour représenter un tel tableau, on utilise une liste de listes:
Par exemple, pour le tableau suivant:
T=[ [0,0,0,0,0,0],
[0,0,1,0,0,1],
[1,0,1,0,1,1],
[1,1,1,0,1,1]]
Un jeton se situe toujours au-dessus d'autres jetons. Dès que l'on trouve un 1 sur une ligne, on aura donc la plus haute colonne.
def detecte1(T):
for j in range(len(T)):
for i in range(len(T[0])):
if T[j][i]==1:
return len(T)-j
#On déduit la hauteur de la plus haute colonne de jetons en faisant
#la différence entre "l'étage" sur lequel on trouve un 1, et le
#nombre d'étages
Exercice 4 : bonus
Vous êtes l'élu, le maître de la Matriks. Cependant, comme vous le savez car vous êtes un fan incontestable de la trilogie des sœurs Wachowskis, il y a eu plusieurs versions de la matrice avant d'aboutir à celle dans laquelle ont vécu Neo, Morpheus et Trinity.
En effet, au lieu d'être dans la matrice (forme finale du cocon informatique dans lequel sont immergés les êtres humains), vous êtes dans une version plus primaire, une version Test. Cette pre-release de la matrice s'appelle la "Matriks". Pour en sortir et sauver Sion, la dernière ville des Hommes encore debout, vous devez trouver deux clés (des listes d'entiers). Ces deux clés sont cachées dans le code de la Matriks (une grosse liste d'entiers écrits en vert sur fond noir qui descend en colonnes de manière assez stylé).
Vous savez deux choses : le produit des sommes de ces deux clés est égal à un nombre magique \(X\), qui vous est donné. Et vous savez que les deux clés doivent être les plus longues possibles (maximiser la somme des longueurs des sous-listes). À vous de trouver ces clés !
Attention, l'ordre des clés importe, vous devez d'abord afficher la plus grande des deux listes, si elles sont de même taille, affichez d'abord celle dont la somme est la plus grande.
S'il n'y a pas de sous-liste qui respecte ces conditions, écrire "IMPOSSIBLE" (vous n'êtes alors peut-être pas l'élu ?).
Note : une sous-liste d'une liste L est une sous-partie contiguë de L. Par exemple si L = [1,2,3,4,5], alors [1,2,3] et [3,4] sont des sous-listes mais pas [1,3,4].
En entrée on a:
- un entier : \(X\), le nombre magique.
- un entier : \(N\), la longueur du code la Matriks.
- une liste de \(N\) entiers séparés par des virgules :
L, le code de la Matriks.
Votre programme doit renvoyer les deux clés ou le message "IMPOSSIBLE".