Bonjour ,

J'ai ce devoir pour ce lundi à faire en info mais malgré tout mes efforts je n'arrive meme pas à commencer
J'adore les mathematiques, et j'adore aider les internautes qui sèchent devant des chiffres mais en Info, c'est à moi de demander de l'aide. je m'adresse donc à tous les doués en info pour ne pas avoir un gros "0" à mon devoirs.

merci par avance à ceux qui pourrons me venir en aide


DANS CE DEVOIR, il n'est nulle part question d'un language de programmation en particulier. Tous les tableaux sont indexés à partir de 1.


On dispose de deux tableaux A et B d'entiers triés en ordre croissant. Chacun contient n éléments. Les 2n entoers ainsi mis en jeu sont deux à deux distincs.

1. on veut fusionner ces deux tableaus en un unique tableau C à 2n éléments triés en ordre croissant qui contiendra les valeurs représentées dans A et B.

a) Ecrire un algorithme qui réalise cette fusion.l'algorithme consistera essentiellement en une boucle while.
b) Justifier le bon fonctionnement de votre algorithme ( on peut par exemple prouver la correction d'un algorithme en exhibant un " invariant de boucle " convenable).
C) Encadrer le nombre de comparaisons effectuées par votre algorithme pa deux fonctions de n.


2. Dans cette question, on ne dispose a priori pas du tableau C.
On veut trouver l'emplacement dans A ou B, de l'entier mA,B qui serait égal à C[n] si on disposait de C ( on veut déterminer si cet entier appartient à A ou B, et quelle est sa position dans A ou B).

Dans l'ensemble des valeurs représentées dans A et B, n - 1 doivent être inférieurs à mA,B, n supérieures à mA,B et égale à mA,B.

a) Proposer un algorithme simple qui détermine la posoition de mA,B à l'aide d'un nombre de comparaisons proportionnel à n.
b) Que peut-on dire de l'emplacement de mA,B dans A ou B si A _n/2_ < B _n/2_ ?
Remarque : La notation [_x_] désigne la partie entiére du réel x, c'est à dire le plus grand entier qui est plus petit ou égal à x.

C) Proposer un algorithme de localisation de mA,B dans A ou B à l'aide d'un nombre de comparaison proportionnel à log(2n) (log(x) = ln(x) / ln(2)).
*Algorithme + preuve de la correction.