aidez moi svp ALGORITHME Fermé

Question

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.

ProgMad · Answer

salut,

va voir du côté des algorithmes de tri (tri bulle , par sélection , par insertion ).

voici un exemple d'algo pour les trois .
tri bulle : 

tri_bulle(tableau T[], taille)
debut
       entier longueur, i;
       booleen permutation;
       longueur = taille;
       faire
            permutation = faux;
            pour i=0 à (longueur-1)
                  si T[i]>T[i+1] alors
                          permuter (T, i, i+1);
                          permutation = vrai;
                  fin si
            fin pour
       tantque inversion
fin


tri par sélection : 

tri_selection(tableau T[], taille)
debut
           entier longueur, indice_max, i;
           longueur = taille;
           tantque( longueur > 0) faire
                //recherche de la position du plus grand élément dans le tableau non encore trié
                indice_max = 0;
                pour i=1 à (longueur-1) faire
                      si T[i]>T[indice_max] alors
                            indice_max = i;
                      fin si
                fin pour
                //echange du plus grand élément avec le dernier
                permuter(T, indice_max, longueur-1);
                //traitement du reste du tableau
                longueur = longueur-1;
           fin tantque
fin



tri par insertion : 

tri_insertion(tableau T[], taille)
debut
       entier longueur, i, temp, compteur;
       booleen OnaDecale;
       longueur = taille;
       pour i=1 à (longueur-1) faire
              temp = T[i]; //valeur à insérer au tour i
              compteur = i-1;
              faire
                     OnaDecale = faux; //on n'a pas fait de décalage
                     si T[compteur] > temp alors
                            T[compteur+1] = T[compteur]; /*décalage des plus grandes valeurs du tableau*/
                            compteur = compteur-1;
                            OnaDecale = vrai; //on vient de faire un décalage
                     fin si
                     si (compteur < 0) alors //on a atteint la premiére valeur du tableau
                            OnaDecale = faux; //il n'y a plus de décalages possibles
                     fin si
              tantque OnaDecale

              T[compteur+1] = temp; /*affectation de la valeur à insérer dans la bonne case*/
       fin pour
fin
Q3


A+

Aidez moi svp ALGORITHME

1 réponse

Discussions similaires