Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Devoir surveille algorithmique et complexite

DEVOIR SURVEILLE Module RO -Complexité Documents Non autorisés Enseignants I Denden R Fre ?ta R Guetari et S Mesfar Exercice- points Niveau Arctic- Sim- GL Durée h Date Octobre Considérons la fonction traiterChaine présentée ci-dessous void traiterChaine char str str est une chaine de caractères int i int j int len strlen str strlen retourne la longueur de la chaine str while i len ?? if str i ' ' str i ' ' for j i j len ?? j str j str j str len ?? ' ' else i Expliquer ce que fait la fonction traiterChaine Soit str une chaine de longueur n donner le contenu de str qui maximise le nombre d ? opérations exécutées par ce programme En déduire la complexité de ce programme au pire des cas à un O près Exercice- points Considérons les programmes illustrés ci-dessous void P int n void P int n int s int s WHILE n n n s s FOR i i n i FOR j i j n n j s s void P int n int s FOR i i n i FOR j j i i j FOR k k Donner la complexité à un O près des programmes P P et P présentées ci-dessus Exercice- points Considérons deux réels a et b tels que a b Etant donné une fonction f dont les valeurs f a f a f a ? f b sont connues Une intégrale approchée de f entre deux entiers a et b est égale à la somme des valeurs f a f a f a ? f b- et f b Ecrire une fonction récursive oat Integf oat tab int n ? Cette fonction prend comme paramètres le nombre de valeurs n de f ainsi que l ? ensemble des valeurs de f stockées dans un tableau nommé tab La fonction retourne comme résultat l ? intégrale de f Donner le type de récursivité de cet algorithme terminale ou non Justi ?er Donner l ? équation récurrente de la complexité en termes de nombre d ? opérations pour la fonction Integf avec explication Ecrire une fonction itérative oat iterIntegf oat tab int n issue de la dérécursivation de la fonction Integf Page C