Aller au contenu


Photo

02 complexite des algorithme recursif


  • Veuillez vous connecter pour répondre
3 réponses à ce sujet

#1 Nicolas Maurice PARMANTIER

Nicolas Maurice PARMANTIER

    Member

  • Members
  • PipPip
  • 34 messages

Posté 27 mai 2016 - 05:29

bonjour slide 13  je ne comprend pas ou et comment trouver t(n)=1+2n a quoi sa correspond ?



#2 Nicolas Maurice PARMANTIER

Nicolas Maurice PARMANTIER

    Member

  • Members
  • PipPip
  • 34 messages

Posté 27 mai 2016 - 08:24

slide 52
 
probleme tri a fusion execution pas a pas 
 
question -first last middle sont des indices ?
-pro.append sa ajoute au debut ou a la fin ?
 a la fin de cet algo je n'arrive pas a trouver un tableau trie
 
 
7 5 14 4 10 2 8
0 1 2  3  4 5 6
 
def fusion(l,first,middle,last):
    i,j = first,middle+1
    pro = []
    while (i<=middle) and (j<=last):
        if l[i]<=l[j]:
            pro.append(l[i])
            i+=1
        else:
            pro.append(l[j])
            j+=1
    while i<=middle:
        pro.append(l[i])
        i+=1
    while j<=last:
        pro.append(l[j])
        j+=1
    for k in range(last-first+1):
        l[first+k] = pro[k]
 
 
 
 
first=0 middle=3 last=6
i=first=0 j=middle+1=4
 
i=0 <= middle=3 vraie et j=4 <=last=6 vraie donc vraie
l[i=0]=7 <= l[j=4]=10 vraie
pro[]=[7] i+=1=1
 
i=1 <= middle=3 vraie et j=4 <= last=6 vraie donc vraie
l[i=1]=5 <= l[j=4]=10 vraie
pro[]=[5,7] i+=1=2
 
i=2 <= middle=3 vraie et j=4 <= last=6 vraie donc vraie
l[i=2]=14 <= l[j=4]=10 faux
pro[] = [10,5,7] j+=1=5
 
i=2 <= middle=3 vraie et j=5 <= last=6 vraie donc vraie
l[i=2]=14 <= l[j=5]= 2 faux
pro[] = [2,10,5,7] j+=1=6
 
i=2 <= middle=3 vraie et j=6 <= last=6 vraie donc vraie
l[i=2]=14 <= l[j=6]=8 faux
pro[] = [8,2,10,5,7] j+=1=7
 
i=2 <= middle=3 vraie et j=7 <= last=6 faux donc faux
i=2 <= middle=3 vraie
l[i=2]=14
pro[] = [14,8,2,10,5,7] i+=1=3
 
i=3 <= middle=3 vraie
l[i=3]= 4
pro[] = [4,14,8,2,10,5,7] i+=1=4
 
i=4 <= middle=3 faux
last=6 - first=0 + 1 = 7 range (0,7) 7 non inclus
l[first=0+k=0]=7 =pro[k=0]=4
l[0] = [4]
 
k=1
l[first=0+k=1]=5 =pro[k=1]=14
l[1] = [4,14]
 
k=2
l[first=0+k=2]=14 = pro[k=2]=8
l[2] = [4,14,8]
 
k=3
l[first=0+k=3]=4 = pro[k=3]=2
l[3] = [4,14,8,2]
 
k=4
l[first=0+k=4]=10 =pro[k=4]=10
l[4] = [4,14,8,2,10]
 
k=5
l[first=0+k=5]=2 = pro[k=5]=5
l[5] = [4,14,8,2,10,5]
 
k=6
l[first=0+k=6]=8 = pro[k=6]=7
l[6] = [4,14,8,2,10,5,7]


#3 Laurent GODEFROY

Laurent GODEFROY

    Member

  • Full Professors
  • 283 messages
  • LocationTours (37)

Posté 27 mai 2016 - 09:31

Bonjour Nicolas,

 

La conclusion du slide 13 provient du résultat sur les suites arithmétiques présenté au slide 10.

 

La procédure de fusion en elle même ne réalise pas le tri des valeurs de la liste, elle sert juste à fusionner deux listes déjà triées en une liste triée. C'est pour cela qu'avant d'être utilisée il y a deux appels récursifs à la procédure de tri (slide 53).



#4 Nicolas Maurice PARMANTIER

Nicolas Maurice PARMANTIER

    Member

  • Members
  • PipPip
  • 34 messages

Posté 30 mai 2016 - 12:17

bonjour slide 53 je n'arrive pas executer pas a pas l'algorithme recursif j ais essayer:

 

 

 

triFusionRec(l,first,last)
 
first=0 < last=6 vraie
 
triFusionRec(l,first=0,(first=0+last=6)=6//2=3) 1er fonction recursive
first=0 < last=3 vraie
triFusionRec(l,first=0,3//2=1) 1er fonction recursive
first=0 < last=3//2=1 vraie
triFusionRec(l,first=0,(3//2)//2=3//4=0.75=0) 1er fonction recursive
first=0 < last=0.75=0 faux
 
triFusionRec(l,((first=0+last=6)//2)=3+1=4,last=6) 2eme fonction recursive
first=4 < last=6 vraie
triFusionRec(l,first=4, (first=4+last=6)=10//2=5) 1er fonction recursive
first=4 < last=5 vraie
triFusionRec(l,first=4, (first=4+last=5)=9//2=4) 1er fonction recursive
first=4 < last=4 faux
 
 
triFusionRec(l,((first=4+last=4)=8//2+1=5,last=? je suis perdu
a faut peut etre rentrer les parametre des 2 fonction recursive a la suite ??
a chaque fois first < last est vraie on execute les 3 lignes suivante ??

triFusionRec(l,first,(first+last)//2)

triFusionRec(l,((first+last)//2)+1,last)

fusion(l,first,(first+last)//2,last)






1 utilisateur(s) li(sen)t ce sujet

0 membre(s), 1 invité(s), 0 utilisateur(s) anonyme(s)