Discussion :

[Attien]

Bonjour à tous.
je suis entrain de travailler la programmation dynamique car j'ai reçu un tp portant sur cette notion, et donc j'ai du mal avec un exercice que pourtant j'ai tracé l'algorithme avec l'aide de quelques manuels que j'ai.
Mais là il y a des cas pour lesquels mon programme ne fonctionne pas correctement, c'est vrai que je ne suis pas un habitué du langage python mais j'ai du mal à résoudre ces différentes cas. D'une part concernant la 2 question que j'ai implémenté mais le cas de la liste [1,1,1,4] ne marche pas(car je dois avoir 6 multiplications au lieu de 5 selon l'énoncé) pourtant le cas de la liste [30,35,15,5,10,20,25] donne le nombre de multiplications qu'il nous faut et j'obtiens le parenthésage qui convient mais pour le premier cas, il y a des messages d'erreur.
Pour le parenthésage, j'ai essayé de faire par récurrence car je ne sais pas comment travailler directement.
J'ai l'impression que mon algorithme ne considère pas vraiment le premier élément du tableau dans pour ce cas.
Je mets mes codes et les différentes photos
Merci d'avance pour votre aide.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
import math
A=[]
def ordre(p):
    n=len(p)-1
    m=[]
    s=[]
    c=[]
    d=[]
    for i in range(n+1):
        for j in range(n+1):
            c.append(0)
            d.append(0)
 
        m.append(c)
        s.append(d)
        c=[]
        d=[]
    for l in range(1,n):
        for i in range(1,n-l+1):
            j=i+l
            m[i][j]=+math.inf
            for k in range(i,j):
                q=m[i][k]+m[k+1][j]+(p[i-1]*p[k]*p[j])
                if q<m[i][j]:
                    m[i][j]=q
                    s[i][j]=k
    #r=s[1][n]
    #print(r)
 
 
 
    return (m[1][n],s)
 
 
x=ordre([1,1,1,4])
 
b=x[1]
 
def affichage(b,i,j):
    if j>i:
        x="("+str(affichage(b,i,b[i][j]))
        y=str(affichage(b,b[i][j]+1,j))+")"
        v=x+y
        return v
    else:
        s="A"+str(i)
        return s
 
o=print(affichage(b,1,4))

[Attien]

Bonjour désolé j'avais considéré le mauvais exemple, au lieu de [1,1,1,4] c'était plutôt [1,1,1,1,4]