Table des matières

TP7 : deques/tri par paquets/ Fibonacci

EXO1

Afin de manipuler correctement les deques il est demandé de programmer les différentes fonctions vues en TD dans l'exos sur les TODO listes.

1) Base de travail

Ecrire les fonctions de base de cette structure de données.

  • Ajout_en_tete
  • Ajout_en_fin
  • Retrait_en_tete
  • Retrait_en_fin

2) Fonctions de ma TODO liste

Nous avions énoncé quelques contraintes:

  • Je veux pouvoir mettre une action à réaliser en priorité absolue
  • Je veux pouvoir, quand je prends une action à réaliser, la comparer avec la suivante et choisir entre les deux et remettre celle qui je ne fais pas en tête de liste, ou si vraiment je ne me sens pas une envie débordante de la réaliser en fin de liste
  • Vérifier la dernière tâche ajoutée

Il faut donc se servir des fonctions définies au 1) pour écrire 

def ajout(toDoListe,action, priorite):
'''cette fonction ajoute l'action dans la toDoListe au bon endroit selon la priorite (0 ou 1)'''
def done(toDoListe,choix):
''' cette fonction permet de retirer une action de la toDoListe, soit systématiquement la première de la liste (choix=0), soit de choisir entre entre les deux premières (choix=1). Il faut alors afficher les actions et demander à l'utilisateur de choisir. Une fois son choix fait il doit dire si il veut mettre l'action qu'il ne choisit pas à sa place (au début de la liste) ou si vraiment il ne veut la faire rapidement et veut la mettre à la fin. Il faut bien sûr effectuer cette opération.
def  verif(toDoListe):
''' cette fonction permet d'aller voir la dernière action stockée et de la remettre après'''

faire un petit programme qui permet de vérifier toutes ces fonctions.

EXO2

Tri par Paquets (vu en TD7) Principe:soit une liste de nombres réels on va créer une liste de n listes (autant que de données dans la liste initiale , découpant l'intervalle des données en n intervalles) et répartir ces données dans les petites listes(paquets). On prendra ensuite un algorithme de tri à bulle pour trier chaque paquet puis les concaténer.

  • Le tri à bulles trie sur place
  • Le tri par paquets ne trie pas sur place
  • Qu'est-ce que cela engendre au niveau de la programmation?

Il faut donc deux fonctions 

def tri_bulle(T):
def tri_par_paquet(T):

On veut comparer les temps d'exécution des deux tris. Pour cela, ajoutez 

import time

et utiliser 

 t=time.time()

Pour générer la liste utiliser np.random.randn() et ajouter 

import numpy as np

EXO3

Programmer la fonction Fibonnaci de manière récursive et de manière itérative