 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
BuG
Guest
|
 Posted: Mon May 17, 2004 8:11 am Post subject: Complexité C++ |
 |
|
Voici l'algorithme du Tri Bulle :
Tri_bulle (t[1....n]) :
1: i <- 1
2: tant que i <- n-1 faire
3: j <- n
4: tant que j -> i+1 faire
5: si t[j] < t[j -1] alors
6: valeur <- t[j]
7: t[j] <- t[j -1]
8: t[j -1] <- valeur
9: j <- j-1
10:i <- i+1
La question etant :
Soit n la taille du tableau à trier et k la valeur de la variable i à
l'entrée dans la deuxième boucle "tant que". Soit C(n,k) le nombre de fois
où la comparaison de la ligne 5 est effectuée. Exprimez C(n,k) en fonction
de n et k.
La réponse etant;
"C(n,k) = n - (k +1) +1"
"C(n,k) = n-1 "
*********************
Ma question :
En regardant des exemples de tri bulle, on s'aperçoit facilement que si n
reprénsente la taille du tableau, alors le nombre de comparaison est égal à
n- 1 à chaque passage dans le tableau. On compare un element avec les autres
element.... excepté lui même . Mais mon problème etant que je ne comprends
pas ce raisonnement.
Qqun peut m'aider ?
Merci
Gib
----
[email]bug (AT) asrun (DOT) org[/email]
|
|
| Back to top |
|
 |
Horst Kraemer
Guest
|
| Posted: Mon May 17, 2004 9:17 am Post subject: Re: Complexité C++ |
|
|
On Mon, 17 May 2004 12:11:53 +0400, "BuG" <bug (AT) asrun (DOT) org> wrote:
| Quote: | Voici l'algorithme du Tri Bulle :
Tri_bulle (t[1....n]) :
1: i <- 1
2: tant que i <- n-1 faire
|
2: tant que i <= n-1 faire
| Quote: | 3: j <- n
4: tant que j -> i+1 faire
|
4: tant que j >= i+1 faire
| Quote: | 5: si t[j] < t[j -1] alors
6: valeur <- t[j]
7: t[j] <- t[j -1]
8: t[j -1] <- valeur
9: j <- j-1
10:i <- i+1
La question etant :
Soit n la taille du tableau à trier et k la valeur de la variable i à
l'entrée dans la deuxième boucle "tant que". Soit C(n,k) le nombre de fois
où la comparaison de la ligne 5 est effectuée. Exprimez C(n,k) en fonction
de n et k.
La réponse etant;
"C(n,k) = n - (k +1) +1"
"C(n,k) = n-1 "
|
Deux réponses?. Èvidemment C(n,k) = n-k, c.a.d C(n.1) = n-1.
*********************
| Quote: |
Ma question :
En regardant des exemples de tri bulle, on s'aperçoit facilement que si n
reprénsente la taille du tableau, alors le nombre de comparaison est égal à
n- 1 à chaque passage dans le tableau. On compare un element avec les autres
element.... excepté lui même . Mais mon problème etant que je ne comprends
pas ce raisonnement.
|
Je ne comprends pas ce que veut dire "en regardant des exemples...".
Dans l'algorithme que tu as décrit il y a n-1 comparaisons dans la
premiere boucle i (i=1) n-2 dans la seconde (i=2),..., et une dans la
derniere (i=n-1). Donc il y un nombre total de
1 + 2 + ... + n-1 = n(n-1)/2
comparaisons dans l'algorithe ci-dessus. Toujours.
--
Horst
|
|
| Back to top |
|
|
BuG
Guest
|
| Posted: Mon May 17, 2004 9:39 am Post subject: Re: Complexité C++ |
|
|
En faite ma
question etait de savoir comment raisonner sur l'algo pour trouver que
C(n,k) = n - (k +1) - 1 = n-k
Je comprend pas comment on arrive à ce résultat...Le "n" s'est la taille du
tableau mais le "k+1" et le "+1". D'ou sortent il ??? :-)
Merci de ton aide
"Horst Kraemer" <horst.kraemer (AT) epost (DOT) de> a écrit dans le message de news:
[email]7a0ha0pkau39qrgfdm384dqal1gmjdnne0 (AT) 4ax (DOT) com[/email]...
| Quote: | On Mon, 17 May 2004 12:11:53 +0400, "BuG" <bug (AT) asrun (DOT) org> wrote:
Voici l'algorithme du Tri Bulle :
Tri_bulle (t[1....n]) :
1: i <- 1
2: tant que i <- n-1 faire
2: tant que i <= n-1 faire
3: j <- n
4: tant que j -> i+1 faire
4: tant que j >= i+1 faire
5: si t[j] < t[j -1] alors
6: valeur <- t[j]
7: t[j] <- t[j -1]
8: t[j -1] <- valeur
9: j <- j-1
10:i <- i+1
La question etant :
Soit n la taille du tableau à trier et k la valeur de la variable i à
l'entrée dans la deuxième boucle "tant que". Soit C(n,k) le nombre de
fois
où la comparaison de la ligne 5 est effectuée. Exprimez C(n,k) en
fonction
de n et k.
La réponse etant;
"C(n,k) = n - (k +1) +1"
"C(n,k) = n-1 "
Deux réponses?. Èvidemment C(n,k) = n-k, c.a.d C(n.1) = n-1.
*********************
Ma question :
En regardant des exemples de tri bulle, on s'aperçoit facilement que si
n
reprénsente la taille du tableau, alors le nombre de comparaison est
égal à
n- 1 à chaque passage dans le tableau. On compare un element avec les
autres
element.... excepté lui même . Mais mon problème etant que je ne
comprends
pas ce raisonnement.
Je ne comprends pas ce que veut dire "en regardant des exemples...".
Dans l'algorithme que tu as décrit il y a n-1 comparaisons dans la
premiere boucle i (i=1) n-2 dans la seconde (i=2),..., et une dans la
derniere (i=n-1). Donc il y un nombre total de
1 + 2 + ... + n-1 = n(n-1)/2
comparaisons dans l'algorithe ci-dessus. Toujours.
--
Horst
|
|
|
| Back to top |
|
|
Horst Kraemer
Guest
|
| Posted: Mon May 17, 2004 11:05 am Post subject: Re: Complexité C++ |
|
|
On Mon, 17 May 2004 13:39:00 +0400, "BuG" <bug (AT) asrun (DOT) org> wrote:
| Quote: | En faite ma
question etait de savoir comment raisonner sur l'algo pour trouver que
C(n,k) = n - (k +1) - 1 = n-k
Je comprend pas comment on arrive à ce résultat...Le "n" s'est la taille du
tableau mais le "k+1" et le "+1". D'ou sortent il ??? 
|
Tu as n éleménts numérotés de 1 à n. Et i a une valeur entre 1 et n-1.
1 2 3 4 .... i i+1 ....... n
maintenant tu compares à partir de j=n et descendant jusqu'à j=i+1
l'élément numéro j avec son prédésesseur numéro j-1. Il faut donc
compter les entiers de i+1 à n. Ce nombre est n-i. Formule générale:
Le nombre des entier de X à Y est Y-X+1 si X<=Y. Ici donc
n - (i+1) - 1 = n - i
--
Horst
|
|
| Back to top |
|
|
BuG
Guest
|
| Posted: Mon May 17, 2004 11:48 am Post subject: Re: Complexité C++ |
|
|
"Horst Kraemer" <horst.kraemer (AT) epost (DOT) de> a écrit dans le message de news:
[email]nc6ha0laofhn74vresqe6peofss3hru4fd (AT) 4ax (DOT) com[/email]...
| Quote: | On Mon, 17 May 2004 13:39:00 +0400, "BuG" <bug (AT) asrun (DOT) org> wrote:
En faite ma
question etait de savoir comment raisonner sur l'algo pour trouver que
C(n,k) = n - (k +1) - 1 = n-k
Je comprend pas comment on arrive à ce résultat...Le "n" s'est la taille
du
tableau mais le "k+1" et le "+1". D'ou sortent il ??? :-)
Tu as n éleménts numérotés de 1 à n. Et i a une valeur entre 1 et n-1.
1 2 3 4 .... i i+1 ....... n
| <- j
maintenant tu compares à partir de j=n et descendant jusqu'à j=i+1
l'élément numéro j avec son prédésesseur numéro j-1. Il faut donc
compter les entiers de i+1 à n. Ce nombre est n-i. Formule générale:
Le nombre des entier de X à Y est Y-X+1 si X<=Y. Ici donc
n - (i+1) - 1 = n - i
|
n - (i+1) + 1 = n - i
Ok je pense avoir compris, je vais essayer avec d'autre exemple, Merci en
tout cas de ton aide
Gib
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
