Forum de Mathématiques: Maths-Forum

aucune réponse?

ampholyte a écrit:Lorsque tu montres du code utilise les balises CODE se sera plus lisible.

Pour chaque algorithme combien d'opération effectues-tu ?

oui désolé
j'utilise pour n=2^p

pour n=2^p

Bonjour, As-tu écrit tes algorithmes et calculer le nombre d'opération que l'algorithme effectue ? oui voila pour le tri par bulles : //tri par bulles void tri_bulles(int t[30],int n){ int i,j; int aide; for(i=0;ii;j--){ if (t[j] > t[j-1]){ aide=t[j-1]; t[j-1]=t[j]; t[j]=aide; } } } for(i=0;i=p;i--...

Bonjour, Une solution théorique pour la première question : Si on pose n=2^p, on a : t(2^p)=2*t(2^(p-1))+5*2^p On divise le tout par 2^p et on pose U(p)=t(2^p)/2^p On obtient directement que U est arithmétique de raison 5 Donc U(p)=5p et on obtient exactement le même résultat que XENSECP. ce n'est ...

XENSECP a écrit:Il semble manquer des données non ?

c'est le suivi de la question

t(1)=0
t(n)=t(n/2)+5n-3

calculer la complexité de tri par fusion dans le cas ou n=2^p
la meme chose pour le
tri par bulles et tri rapide et tri par insertion

et merci

sayez sa marche merci :D
et pour la 3eme Question est ce ue vous connnaissez une réponse?

Pour la deuxième c'est plus mathématique : t(n) - t\left(\frac{n}{2}\right) = 5n-3 \\ t\left(\frac{n}{2}\right) - t\left(\frac{n}{4}\right) = 5\frac{n}{2}-3 \\ \dots \\ t(2) - t(1) = 5 \times 2 - 3 Soit t(n) = \sum_{k=1}^{\log_2{n}}{5\times 2^...

Bon c'est pas une intuition naturelle. J'ai essayé de voir comment ça pouvait "récurrer" avant d'arriver à ça : http://img16.imageshack.us/img16/8519/recurrence20130512.png J'ai constaté qu'il y avait toujours un facteur 5... Puis que ça dépendait de n et enfin de k en posant n=2^k . Je s...

XENSECP a écrit:Aah les maths... Moi j'ai une solution basée sur de l'empirique pour aboutir à une hypothèse de récurrence. Si ça te va, je peux te la présenter ...

oui pas de problème

Salut, J'ai un peu cherché et j'ai trouvé ta première. Par contre je sais pas si tu cherches une solution "théorique" ou si une "empirique" te convient (sachant qu'il faut le prouver par récurrence évidemment). Tiens moi au courant. ui la solution mathématique s'il vous plait co...

bonjour j'ai un problème de résoudre cette fonction dans le cas ou n est une puissance de 2 t(1)=0 t(n)=2t(n/2)+5n et aussi t(1)=0 t(n)=t(n/2)+5n-3 enfin un 3eme on a C1 ,C2 >0 tel que n>P montrez que C1*f(n) <= g(n)=n^3 -2n^2 -5n <= C2*f(n) en déduire la compléxité asymptotique de g(n) merci beaucoup