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.
A voir également:
- Aidez moi svp ALGORITHME
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Algorithme application pc - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ajout rapide snap - Forum Snapchat
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 par sélection :
tri par insertion :
A+
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+
