close

Se connecter

Se connecter avec OpenID

Boucles while

IntégréTéléchargement
IPT_Exercices_PCSI
10.
Ecrire une fonction prenant en argument une liste d'entiers et qui retourne la longueur de la plus longue suite strictement
croissante à partir du premier terme.
11.
Ecrire une fonction qui prend en argument deux chaînes de caractères ch et ss_ch et qui détermine si ss_ch est une souchaîne de la chaîne ch et retourne alors la position de la première occurrence de ss_ch dans ch.
12.
Tri bulles
Etant donné une liste L composée d'entiers, le tri bulles est une des méthode pour trier L par ordre croissant. On donne
l'algorithme ci-dessous. Etudier le code et prouver qu'il trie effectivement la liste L.
(le tri se fait "sur place", c.a.d que c'est la liste qui est passée en paramètre qui est elle-même modifiée, ce qui explique
qu'il n'y ait pas de return dans la fonction).
1 def tri_bulles(L):
2 |
n = len(L)
3 |
for i in range(n − 1, 0 , −1):
4 |
|
for j in range(i):
5 |
|
|
if L[j] > L[j+1]:
6 |
|
|
|
L[j] , L[j+1] = L[j+1] , L[j]
Prouver que le nombre d'échanges est égal au nombre d'inversions dans la liste initiale (une inversion est un couple (i, j)
avec i < j et L[i] > L[j]). Quelle est la complexité maximale en nombre d'échanges ? la complexité minimale.
Sachant qu'une permutation aléatoire de ’1,n÷ a en moyenne n(n − 1)/4 inversions, quelle est la complexité moyenne du
tri bulles ?
13.
La méthode de Hörner : pour calculer P(x) où P = anX n + an − 1 X n − 1 + … + a1X + a0 , la méthode naïve consisterait
d'abord à calculer les puissances successives de x , à les multiplier ensuite par leurs coefficients respectifs et enfin à en
faire la somme. La méthode de Hörner consiste à effectuer :
P(x) = (( … ((anx + an − 1)x + an − 2)x + … + a1)x + a0
Ecrire une fonction Horner(P,x) qui calcule P(x) par la méthode de Hörner.
Déterminer un invariant de boucle permettant de prouver que la fonction fonctionne correctement.
14.
Si n est un entier naturel, on note prod(n) le produit de ses chiffres en base 10. Par exemple prod(153) = 1.5.3 = 15. On
applique alors successivement la fonction prod jusqu’à ce que le résultat soit compris entre 0 et 9. Le nombre minimal
de fois où l’on doit appliquer prod pour arriver à un tel résultat s’appelle la persistance de n.
Par exemple :
prod(prod(153)) = prod(15) = 5 donc la persistance de 153 est 2.
Quel est le plus petit entier naturel de persistance 5
15.
Ecrire une fonction fibo(tab) qui prend en argument une liste croissante d'entiers ≥ 0 (on autorise plusieurs entiers
consécutifs identiques) et qui retourne la liste des nombres de Fibonacci Fn pour n dans tab. On demande de ne pas
stocker les Fk intermédiaires entre deux Fn à calculer.
- page 2 -
Auteur
Документ
Catégorie
Без категории
Affichages
4
Taille du fichier
22 Кб
Étiquettes
1/--Pages
signaler