Test 1 d’informatique 1 Nom_3 PDF
Document Details
Tags
Summary
This document contains questions about algorithms. It asks for pseudocode and analysis of time complexity. The questions involve finding algorithms for determining if all elements in a list of integers are distinct.
Full Transcript
--------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------...
--------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------- Question Ouverte 1 : (5 pts) Soit une liste L contenant N entiers avec N>0 1.1) Ecrire le pseudocode de l’algorithme Tous_Differents qui renvoie VRAI si tous les éléments de L sont différents entre eux. Par exemple l’algorithme renvoie VRAI pour L={4, 9, 12} tandis qu’il renvoie FAUX pour L={4, 9, 12, 11, 9, 22}. L’algorithme renvoie VRAi s’il n’y a qu’un seul élément dans L. Formulé d’une autre manière, on peut dire que cet algorithme doit renvoyer FAUX dès qu’il trouve deux éléments égaux. On demande une version itérative, sans récursivité, pour cette question Tous_Differents (faisable en 5 lignes) entrée : entier N > 0 , Liste L contenant N entiers sortie : booléen VRAI si tous les éléments sont différents entre eux (sinon renvoie FAUX) 1.2) Quelle est la complexité de votre algorithme en fonction de N ? Justifier votre réponse : 5 1.3) fournir une version récursive de votre algorithme (qu’on appellera TDR). Faire comme dans le cours sur le tri fusion pour la syntaxe du passage d’une sous-liste lors d’un appel récursif: après la taille de la sous-liste, indiquer le nom de la liste L avec, entre parenthèses, les indices du premier et du dernier élément transmis pour la sous-liste. Exemple : voici un appel récursif qui transmet la sous-liste contenant les deux derniers éléments de L : TDR( 2, L(N-1, N) ) TDR (faisable en 8 lignes) entrée : entier N > 0 , Liste L contenant N entiers sortie : booléen VRAI si tous les éléments sont différents entre eux (sinon renvoie FAUX) 1.4) Quelle est la complexité de votre algorithme en fonction de N ? Justifier votre réponse : 6
