Listes

Rangs impairs.

Écrire une fonction python prenant en paramètre une liste et affichant les éléments d'indices impairs de cette liste.

Max d'une liste.

L étant une liste de nombres, le code python max(L) renvoie la valeur maximale contenue dans la liste.

Écrire une fonction python prenant en paramètre une liste de nombres et renvoyant la valeur maximale des éléments de la liste.

En d'autres termes, il s'agit d'écrire votre propre version de la fonction python max() (vous n'avez donc pas le droit de vous en servir !)

Insertion dans une liste.

L étant une liste de nombres, le code python L.insert(position, element) insère l'élément 'element' en position 'position' dans la liste (exemples dans le cours).

Écrire une fonction python ayant le même effet. On n'aura donc pas le droit de se servir de la méthode python insert(). On pourra, si besoin, utiliser la méthode append().

Réécriture des méthodes des listes.

Les fonctions append, insert, extend, pop et remove s'appellent comme des suffixes d'une liste et la modifient directement - on parle de méthodes des objets listes.

Écrire les fonctions monappend, moninsert, monextend, monpop et monremove qui miment leurs effet mais renvoient une nouvelle liste, sans modifier la liste de départ L. Ainsi :

• L = monextend(L,M) agit comme L.extend(M) (mais A = monextend(L,M) ne modifie pas L).
• L = monappend(L,elt) agit comme L.append(elt)
• monremove(L, elt) renvoie une liste où tous les éléments elt ont été retiré, et une copie de L s'il n'y en a pas.
• (L,a) = monpop(L,pos) agit comme a = L.pop(pos)
• L = moninsert(L, pos, elt) agit comme L.insert(pos, elt)

On ne se préoccupera pas des difficultés posées par la gestion des listes de listes.

Journée pancake.

On considère le programme suivant :

import random as rd

def retourne(L,n) :
	""" retourne l'ordre des éléments en queue de liste L
	à partir de l'élément d'indice n."""
	queue = L[n:]
	queue.reverse()	 
	return L[:n] + queue
	

def plusGrand(L,n) :
	""" retourne le rang du plus grand élément 
	de la queue de liste L (queue considérée à partir de 
	l'élément d'indice n)."""
	 
	return L.index( max(L[n:]),n )	



def mystere(L) :
	for i in range(len(L)) :
		k = plusGrand(L,i)
		L = retourne(L,k)
		L = retourne(L, i)

	return L
	

 
 
L = [ rd.randint(0,100) for i in range(20) ]
 
L = mystere(L)
print(L)

Sans le tester, devinez l'effet sur les listes L testées.

Si vous ne trouvez pas, testez et essayez de comprendre le fonctionnement.

Tri d'une liste.

L'exercice précédent a montré un exemple de programme permettant de trier une liste.

De façon générale, le tri est important en informatique.

Il existe bien entendu des fonctions prédéfinies en python qui permettent de trier efficacement une liste.

Vérifier par exemple que L est triée dans le second affichage ci-dessous :

L = [ 2, 5, 1, 8, 2, 9 , -5 ]
print(L)
L.sort()
print(L)

Votre mission est maintenant d'écrire une fonction de tri d'une liste. Interdiction évidemment de se servir de la méthode sort() prédéfinie ! Et le principe utilisé devra être différent du principe du pancake sorting de l'exercice précédent.

Mélanger un paquet de cartes.

Dans cet exercice, on va chercher à mélanger les éléments d'une liste.

1. Commencer par définir une liste vide nommée paquet (représentant un paquet de cartes).
2. Écrire une fonction python remplir prenant en entrée une liste et un nombre n et ayant pour effet d'initialiser la liste avec les entiers 1, 2, 3, ..., n (dans cet ordre).
   Exemple : dans le programme, après l'appel remplir(paquet, 5), paquet sera égal à [1,2,3,4,5].
3. Écrire une fonction python afficher qui prend en paramètres une liste et un entier n et qui affiche les éléments de la liste, à raison de n éléments par ligne.
   L'utilisateur doit pouvoir ne pas préciser de valeur pour n, n prendra dans ce cas la valeur 6 par défaut.
4. Écrire une fonction python echanger prenant en paramètres une liste et deux indices d'éléments de la liste et qui a pour effet d'échanger les contenus de ces deux éléments.
   Exemple : si paquet = [1,2,3,4,5,6,7], après l'appel echanger(paquet,2,5), paquet sera égal à la liste [1,2, 6, 4,5, 3, 7].
5. Écrire une fonction inverser prenant en paramètres une liste et deux indices i et j (i < j) d'éléments de la liste et qui a pour effet d'inverser l'ordre des éléments de la liste, d'indices entre i et j.
   Exemple : si la liste est paquet = [1,2,3,4,5,6,7,8], alors après l'appel inverser(paquet, 3,6), paquet sera égal à la liste [1,2,3,7,6,5,4, 8].
6. Écrire une fonction circulaire_gauche qui prend en paramètre une liste et a pour effet de faire subir une permutation circulaire gauche de un rang aux éléments de la liste, c'est à dire de décaler d'un rang vers la gauche tout élément de la liste, le premier élément passant en queue de liste.
   Exemple : si paquet = [1,2,3,4], après l'appel circulaire_gauche(paquet), paquet est égal à la liste [2,3,4,1].
7. Écrire une fonction circulaire_gauche_n qui prend en paramètres une liste et un entier naturel n et a pour effet de faire une parmutation circulaire gauche de n rangs aux éléments de la liste, c'est à dire de décaler de n rangs vers la gauche tout élément de la liste.
8. On utilise maintenant les fonctions précédentes pour mélanger le paquet. Pour cela, on va choisir au hasard les opérations suivantes :
   • Opération 1 : on échange les contenus de deux cases différentes de paquet, cases choisies au hasard.
   • Opération 2 : on choisit un entier n au hasard ( \( 1 < n \leqslant \text{longueur de la liste} \) ) et on fait subir une permutation circulaire de n cases à notre liste paquet.
   • Opération 3 : on inverse l'ordre des cartes de paquet entre l'indice m et l'indice m+n où n et m sont choisis au hasard (avec \( 2 \leqslant n < \text{longueur de la liste}//2 \) et \( 0 \leqslant m < \text{longueur de la liste}//2 \) )

   L'opération 1 sera choisie avec une probabilité de \( \frac{1}{6} \), l'opération 2 avec une probabilité de \( \frac{1}{3} \) et l'opération 3 avec une probabilité \( \frac{1}{2} \).

   L'ensemble (choix d'une opération au hasard et application de cette opération) sera répété autant de fois qu'il y a de cartes dans le paquet.