Bonjour, je suis bloqué sur mon exo d'algorithmique (j'ai un peu de mal...) pourrix vous m'aider svp
Soit un tableau a[1...n]
on veut écrire un algorithme qui retourne le tableau r [1...n] tel que pour tout 1<ou= i <ou= n; r[ i] est le nombre de fois que a[ i] apparait ds a....
Ex: a = [23225] ; on veut r = [3,1,3,3,1]
¨pour cela, on suppose que tous les éléments de a sont compris entre 1 et m (entier fixé). On considére le tableau t[1...m] dont tous les éléments sont initialmeent mis à 0 et incrémentés (d'une facon à préciser) par un passage ds une boucle.
Former le tableau t et s'en servir pour former r
(jai un peu de mal la dessus et je suis bloqué sur la suite qui est INDEPENDANT de cela)
On suppose le tableau trié par ordre croissant, on aurait ds notre exemple : a = [2,2,2,3,5]
On veut remplir efficacement r en se servant de la particularité de a. Si a[i-1]<a[ i]==a[k]=a[j]<a[j+1]
on dit que le sous tableau a[i...j] est un plateau; on peut remplir efficacement le sous tableau r[i...j]
Ecrire un algorithme formant le tableau r. On fera intervenir deux entiers i et j dont on précisera les évolutions.
Merci d'avance vous me serez d'un très grand secours
salut,
je ferme la balise italique pour commencer
il faut parcourir le tableau a.
Si on considère qu'il y a n cases dans le tableau a :
for (i in 1 .. n) {
// dès que tu rencontres un nombre, tu l'incrémentes dans le tableau t :
t[ i]++;
}
// et ensuite tu construits ton tableau a en vérifiant le nombre d'occurences de chaque case du tableau a dans le tableau t.
for (i in 1 ..n){
r[ i] = t[a[ i]];
}
Tu as compris ?
Pookette
[/i] tiens pourquoi la balise de fermeture d'italique n'a pas fonctionné ...
n'hésite pas à poser des questions si tu ne comprends pas
oui pour le premier c'est ce uqe j 'avais pensé
r<--[]
Pour i de 1 à n fais k<--a[ i], t[k] <-- t[k] + 1 Fait.
Pour j de 1 à n fait r[j]<--t[j] fait
est ce que c'est ca?
mais en fait je suis bloqué ds le dernier algorithme parce que je ne sais pas comment utiliser les histoires de plateau...?
Merci d'avance et déja merci pour ton explication
pas exactement pour le 1er
la boucle qui forme t est correct (la variable k est pas vraiment neccesaire, disont que sa depend si tu cherche a faire un code clair ou rapide)
l'autre boucle a un serieux defaut... si tu laisse sa comme sa tu va te contenter de recopier bettement t dans r et en plus tu va avoir une erreur de dimension (t[j], j ne peut aller que de 1 a m donc si m<n c'est pas bien ^^)
il faut remplacer le r[j]<--t[j] par r[j]<--t[a[j]]
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :