Jump to content
Sign in to follow this  
Nicolas Maurice PARMANTIER

02 complexite des algorithme recursif

Recommended Posts

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<=l[j]:

            pro.append(l)

            i+=1

        else:

            pro.append(l[j])

            j+=1

    while i<=middle:

        pro.append(l)

        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=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]

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
Sign in to follow this  

×