Aidez moi svp ALGORITHME
LA PAS DOUÉ EN INFO
-
ProgMad Messages postés 90 Statut Membre -
ProgMad Messages postés 90 Statut Membre -
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.
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.
Configuration: Windows XP Internet Explorer 6.0
1 réponse
-
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+
