Résultat d'un code incompris

**ZhaoZhao** · 21/12/2019, 10h16

Bonjour,

J'ai écris une fonction en Python dont le but est de, à partir une liste ordonnée d'entier positifs, construire un entier positif à partir d'additions d'une manière optimale, mais je ne comprends pas du tout le résultat que j'obtiens. Le problème n'est même pas s'il me donne un résultat exact ou non.
Le code est :

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
 
def choix_elements(liste,max):
    n=len(liste)
    l=[-float('inf')]*(n+1)
    for i in range(n):
        l[i+1]=liste[i]
    matrice=[[0]*(max+1) for i in range(n+1)]
    matrice_des_elements=[[[0]*n]*(max+1) for i in range(n+1)]
    for i in range(n+1):
        for j in range(max+1):
            if j==0:
                matrice[i][j]=0
            elif i==0:
                matrice[i][j]=float('inf')
            else:
                x=0
                y=0
                if j-l[i]>=0:
                    y=1+matrice[i][j-l[i]]
                else:
                    y=float('inf')
                if i>=1:
                    x=matrice[i-1][j]
                else:
                    x=float('inf')
                if min(x,y)==y:
                    matrice_des_elements[i][j]=matrice_des_elements[i][j-l[i]]
                    matrice_des_elements[i][j][i-1]+=1
                if min(x,y)==x:
                    matrice_pieces[i][j]=matrice_pieces[i-1][j]
                matrice[i][j]=min(x,y)
      return matrice_des_elements

Alors, le but du code final du code est de trouver le nombre minimal d'éléments dans la liste liste pour construire max à partir d'additions, et de donner ces éléments. Alors pour ce faire, il va trouver ce nombre minimal pour tout élément j inférieur ou égal à max en partant de 0 (max est un entier strictement positif), et à chaque fois avec un seul élément de la liste des éléments. Ainsi, à chaque fois pour construire j on va voir j-l[i] (on a dit qu'on travaillait avec un seul élément dans la ligne i), car si on construit de manière optimale j-l[i] alors il ne resterait qu'à rajouter l[i] comme élément pour trouver j. Mais, il faut comparer avec la manière dont on a obtenu j en ayant utilisé que les éléments de l[:i].

Le résultat que j'obtiens est le suivant pour choix_elements([1,7,23],28) :

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
[[[0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]],
 [[28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4]],
 [[0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0]],
 [[0, 0, 1],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [0, 0, 1],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0]]]

Ce que je trouve bizarre. Car déjà si j==0 alors je devrais avoir des [0,0,0]. Car si j==0 je ne fais que modifier matrice (dont j'en aurais besoin plus tard).

J'espère que vous pourrez m'aider à comprendre d'où vient le problème. J'ai analysé et re-analysé le code mais je ne trouve vraiment pas d'où la première colonne n'est pas que des [0,0,0].

Merci d'avance.

**marco056** · 21/12/2019, 12h57

Code trop compliqué pour moi, désolé. Pas de commentaires, ...
Par contre, prendre max comme nom de variable, comment dire ?
pour min, c'est kifkif.

**wiztricks** · 21/12/2019, 13h56

Salut,

Envoyé par ZhaoZhao

J'ai écris une fonction en Python dont le but est de, à partir une liste ordonnée d'entier positifs, construire un entier positif à partir d'additions d'une manière optimale, mais je ne comprends pas du tout le résultat que j'obtiens. Le problème n'est même pas s'il me donne un résultat exact ou non.

Si vous ne commencez pas par décrire l'algorithme utilisé ou renvoyer à une page Web qui... on ne saura pas ce que vous essayez de coder ni si les résultats sont attendus ou pas.
Et sans ce point de départ, inutile d'essayer de comprendre votre code.

- W

**ZhaoZhao** · 21/12/2019, 17h04

Bonjour,

Excusez-moi pour ne pas avoir commenté mon code. Je pensais que l'explication que j'avais fourni serait suffisante.

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
 
def choix_elements(liste,max):
    n=len(liste)
 
    #Construction d'une liste vide qui contiendra -inf à l'indice 0 puis les éléments de liste
    l=[-float('inf')]*(n+1)
    for i in range(n):
        l[i+1]=liste[i]
    #Nous mettrons dans matrice le nombre minimal d'éléments de liste nécessaire pour faire un j<=max
    matrice=[[0]*(max+1) for i in range(n+1)]
    #Nous mettrons dans matrice_des_elements les éléments de liste pour faire un j<=max de manière optimale
    matrice_des_elements=[[[0]*n]*(max+1) for i in range(n+1)]
    #Nous allons parcourir tous les éléments de l et ceux de [0,1,...,max] pour à chaque fois construire
    #le j dans [0,1,...,max] de manière optimale à partir de l[i]
    for i in range(n+1):
        for j in range(max+1):
            if j==0: #Si j==0 alors on ne peut l'avoir qu'avec un 0...
                matrice[i][j]=0
            elif i==0: #Si i==0 alors on ne peut en faire aucun élément d'où l'infini, c'est symbolique
                matrice[i][j]=float('inf')
            else: #Sinon j!=0 et i!=0
                x=0
                y=0
                if j-l[i]>=0: 
                    y=1+matrice[i][j-l[i]] #Ici y est le nombre d'éléments qu'il a fallut pour construire
                    #j-l[i] à partir de l[i], et on rajoute 1 car dans ce cas pour obtenir j il faut
                    #rajouter l[i]
                else:
                    y=float('inf') #Ici aussi l'infini est symbolique
                if i>=1:
                    x=matrice[i-1][j] #Ca, c'est le nombre d'éléments qu'il a fallut pour construire j
                    #à partir de l[i-1]
                else:
                    x=float('inf')
                #On va comparer quelle méthdoe de construction de j donne le minimum d'éléments à choisir
                #dans l
                if min(x,y)==y:#Si il est mieux de choisir autant d'éléments pour j-l[i] et on rajoute l[i]
                    #alors les éléments en questions sont ceux avec lesquels on a construit j-l[i]
                    #et on rajoute l[i]. Rappelons que matrice_ces_elements[k][p] est une liste 
                    #de même taille que liste d'où le i-1.
                    matrice_des_elements[i][j]=matrice_des_elements[i][j-l[i]]
                    matrice_des_elements[i][j][i-1]+=1
                if min(x,y)==x:#S'il est mieux de choisir la construction de j avec l[i-1], alors on garde
                    #les mêmes éléments.
                    matrice_pieces[i][j]=matrice_pieces[i-1][j]
                #On rajoute le nombre minimal dans la matrice qui est consacré à cela
                matrice[i][j]=min(x,y)
      return matrice_des_elements

Comme je l'avais dit. On cherche à connaître à partir des éléments d'une liste liste le nombre minimal des éléments à choisir et lesquels, pour avoir un entier positif max. L'algorithme consiste en le fait suivant: disons que x=max(liste) si je sais comment construire de manière optimale max-x, alors il suffirait de rajouter à ces éléments x et au nombre minimal 1. Sauf que il se peut que la façon la plus optimale d'avoir max avec les éléments de liste ne soit pas celui-ci, si notamment x>max. Dans ce cas on choisis la méthode pour avoir max avec liste[:len(liste)-1].

Je remets le résultat de : choix_elements([1,7,23],28)

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
[[[0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]],
 [[28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4]],
 [[0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0]],
 [[0, 0, 1],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [0, 0, 1],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0]]]

Je comprends vraiment pas ce résultat. Par exemple à la ligne 2 de la matrice, colonne 1. J'avais bien écris que si j==0, alors on ne peut pas le construire avec des éléments de liste qui ne contient que des éléments strictement positif. Y'a bien ce if j==0: instruction qui ne change pas matrice_des_elements. Donc elle ne devrait pas changer non ?

Sinon, pour la question du nom de max c'est juste parce qu'après je travaille sur tous les éléments qui sont inférieurs donc c'est leur max... Il aurait été bizarre de choisir min comme nom alors que je prends des j dans [0,min].

J'espère que vous pourrez m'aider à comprendre le résultat.

Merci par avance.

**wiztricks** · 21/12/2019, 18h09

Salut,

Envoyé par ZhaoZhao

On cherche à connaître à partir des éléments d'une liste liste le nombre minimal des éléments à choisir et lesquels, pour avoir un entier positif max.

Mouais. Déjà on ne sait pas ce que sont les éléments de la liste: des patates, des entiers, des nombres réels? Puis admettons qu'on trouve un sous ensemble minimal, quelle est la relation entre ce sous ensemble et max: le produit, l'addition, la concaténation?

Si raconter çà en français vous pose des difficultés vous pouvez toujours expliquer comment çà fonctionne avec un exemple.

Envoyé par ZhaoZhao;11291391E

L'algorithme consiste en le fait suivant: disons que x=max(liste) si je sais comment construire de manière optimale max-x, alors il suffirait de rajouter à ces éléments x et au nombre minimal 1.

Un algorithme c'est pas "disons", c'est posons x = max(liste).
On se retrouve avec un "max" terme mal défini précédemment qui devient le plus grand nombre contenu dans la liste et si max est égal à x, max - x vaut juste 0.
A moins que vous vouliez dire autre chose...

Et là j'arrête car, si vous n'arrivez pas à écrire ce que vous voulez plus clairement (en français), je ne comprends pas ce que vous voulez faire (et inutile de regarder le code).

- W

olivier50 · 21/12/2019, 18h13

Bonsoir,

Je crois qu'il veut faire ça: choix_elements([1,7,23],28)

1. Il veut obtenir 28 avec des éléments de la liste de façon optimale (=en utilisant le moins d'éléments de la liste) par des additions.
2. Comme algo de base, il dit que d'abord on prend le max de la liste sous réserve qu'il soit inférieur ou égal au résultat désiré: donc ici 23 est le max.
3. Il nous reste à définir de façon optimale comment on peut calculer le reste 5 en utilisant les éléments de la liste. Bien sûr pour obtenir 5 avec des additions, ne restant que 1 et 7 dans la liste exploitables, on ne pourra utiliser que 5 fois 1.

Pour le max, si le max de la liste est supérieur au résultat souhaité, rien ne nous dit que [len-1] càd le prédécesseur dans la liste ordonnée soit lui-même inférieur au résultat cible donc j'imagine qu'on descend encore dans la liste ordonnée jusqu'à trouver l'entier le plus proche de la cible souhaitée.

Cordialement.

**ZhaoZhao** · 21/12/2019, 18h41

Excusez-moi @wiztricks mais je trouve votre language déplacé. Je vous cite :

là partir une liste ordonnée d'entier positifs, construire un entier positif à partir d'additions d'une manière optimale

dans mon premier message juste après le bonjour.
Sauf si vous voulez jouer l'idiot, vous voyez bien que le

x=max(liste)

veut dire que x est le maximum de la liste. Ce n'est en rien l'entier max. Alors supposons que vous n'ayez réellement pas compris et que vous avez confondu max dans max(liste) avec max l'entier. J'essaie de comprendre ce que voudrait dire max(liste) avec liste un objet de type list, et max un objet de type int. Est-ce qu'en terme de syntaxe Python, vous avez cru qu'il y'a un attribut de type list pour les int ? Mais max est déjà une instanciation. Est-ce que mathématiquement vous avez construit une action d'un groupe des listes (très bizarre à construire ? vous n'y avez mis des éléments dans un autre groupe H et vous avez construit une loi sur votre groupe des listes "comme" une loi produit ? Je serais ravi de voir comment vous vous y êtes pris) et ce groupe opère sur l'ensemble des entiers avec une action que vous n'avez pas noté (comme traditionnellement . ) mais comme des ( ) ?
Deuxièmement, c'est ma liste qui prend des patates ou je ne sais pas quoi. Si vous ne savez pas que le maximum est défini sur des ensembles ORDONNES qui sont en général soit des ensembles très abstraits avec lesquels on ne travailleraient pas en Python, soit des ensembles pas très abstraits mais avec des relations d'ordre tordus et avec lesquelles on ne travailleraient pas en Python, bah je n'y peux rien aussi... On pourrait dans notre cas aussi, rester calme, et dire que vous avez construit un ensemble de patate avec une relation d'ordre qui serait le volume de ces patates ou la masse de celles-ci, mais est-ce que c'est usuel ?
Et là j'arrête, la réaction à un sarcasme est bien un sarcasme, j'espère que vous le comprendrez.

Sinon, merci pour votre explication olivier50, c'était exactement le but du code. Le code est commenté en fait, seulement, certaines personnes n'ont pas voulu y jeter un coup d'oeil. Si vous voulez, je pourrais vous écrire l'algorithme en terme mathématique avec des opérateurs, mais est-ce que cela sera plus compréhensible que de dire

Alors pour ce faire, il va trouver ce nombre minimal pour tout élément j inférieur ou égal à max en partant de 0 (max est un entier strictement positif), et à chaque fois avec un seul élément de la liste des éléments. Ainsi, à chaque fois pour construire j on va voir j-l[i] (on a dit qu'on travaillait avec un seul élément dans la ligne i), car si on construit de manière optimale j-l[i] alors il ne resterait qu'à rajouter l[i] comme élément pour trouver j. Mais, il faut comparer avec la manière dont on a obtenu j en ayant utilisé que les éléments de l[:i].

???

J'espère que mon message ne vous heurtera pas @wiztricks , si vous sentez un quelconque vouloir d'une certaine réaciton, sachez que j'ai senti la même chose.

Résultat d'un code incompris

Python

Vue hybride

Discussions similaires

Partager

Partager