Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Somme, récursive

7 views
Skip to first unread message

raph14

unread,
Apr 29, 2021, 3:38:34 PM4/29/21
to
Bonjour,
J'essaie de faire une question de mon DM de NSI mais problème, je bloque. Aider
moi svp :,)
Il faut faire la somme de (4,7,5,5,2,6,9,3,8,4) en utilisant une récursivité.
Voici la question:
"Implémenter une fonction récursive max_pyr(pyramide) retournant la somme
maximale de la
pyramide."

Je n'y arrive pas j'ai essayé en créent cela:
def max_pyr(liste):
somme=0
if len(liste)<=0:
return somme
else:
somme+=liste[0]
liste.del[0]
return (max_pyr(liste),somme)
Mais rien cela ne marche pas...
Aider moi svp

Benoit Izac

unread,
Apr 29, 2021, 4:38:51 PM4/29/21
to
Bonjour,

Le 29/04/2021 à 21:38, raph a écrit dans le message
<48-dnbOA4f2klhb9...@giganews.com> :

> J'essaie de faire une question de mon DM de NSI mais problème, je
> bloque. Aider moi svp :,)
> Il faut faire la somme de (4,7,5,5,2,6,9,3,8,4) en utilisant une
> récursivité.
> Voici la question:
> "Implémenter une fonction récursive max_pyr(pyramide) retournant la
> somme maximale de la pyramide."
>
> Je n'y arrive pas j'ai essayé en créent cela:
> def max_pyr(liste):
> somme=0
> if len(liste)<=0:
> return somme
> else:
> somme+=liste[0]
> liste.del[0]
> return (max_pyr(liste),somme)

Quand une liste n'a aucun élément, la somme vaut 0 (ou None, ou
n'importe quoi que l'on décide).
Quand une liste n'a qu'un élément, la somme vaut la valeur de cet
élément.
Quand une liste a N éléments, la somme vaut la valeur du premier élément
+ la somme des N-1 suivants (ou la valeur du dernier élément + la somme
des les N-1 précédents, au choix).

Après, la « somme maximale », ça n'a pas vraiment de sens. Est-ce la
somme ou bien la valeur maximale que l'on cherche ? Vu le nom de la
fonction « max_pyr », je dirais plutôt la valeur maximale…

La valeur maximale d'une liste c'est la plus grande valeur entre le
premier élément et la valeur maximale des éléments suivants.

NB : Tu me diras combien j'ai eu.
--
Benoit Izac

Dominique

unread,
Apr 30, 2021, 1:02:16 AM4/30/21
to
Le 29/04/2021 à 22:38, Benoit Izac a écrit :

> La valeur maximale d'une liste c'est la plus grande valeur entre le
> premier élément et la valeur maximale des éléments suivants.

Bonjour,

Je comprends mal quelle peut-être cette plus grande valeur que tu évoques.

Si liste=[4,7,5,5,2,6,9,3,8,4], je serais tenté d'isoler liste[0] avec
deb=liste[0], le retirer de liste, puis de faire
liste.sort(revere=)True) et prendre liste[0] et faire deb+liste[0]

Mais c'est si simple que ça ne doit pas être ça


--
Dominique
Courriel : dominique point sextant ate orange en France
Esto quod es

Alain Ketterlin

unread,
Apr 30, 2021, 6:07:43 AM4/30/21
to
Dominique <z...@aol.com.invalid> writes:

> Le 29/04/2021 à 22:38, Benoit Izac a écrit :
>
>> La valeur maximale d'une liste c'est la plus grande valeur entre le
>> premier élément et la valeur maximale des éléments suivants.
>
> Bonjour,
>
> Je comprends mal quelle peut-être cette plus grande valeur que tu évoques.
>
> Si liste=[4,7,5,5,2,6,9,3,8,4], je serais tenté d'isoler liste[0] avec
> deb=liste[0], le retirer de liste, puis de faire
> liste.sort(revere=)True) et prendre liste[0] et faire deb+liste[0]
>
> Mais c'est si simple que ça ne doit pas être ça

Ce n'est pas un problème de simplicité, c'est un problème de complexité
(au passage, il est inutile d'enlever le premier élément, tu peux trier
et prendre le premier/dernier selon que tu veux le min/max -- ou
l'inverse avec reverse ; en fait je ne comprends pas ton idée avec le
premier élément).

Le problème de complexité est : trier une liste de n élements coûte
environ n*log(n) comparaisons, alors que trouver le min/max ne devrait
coûter que environ n opérations (comparer un nouvel élément avec le
min/max déjà connu des éléments déjà consultés).

Ce qu'explique Benoît, c'est comment déterminer le min/max sans utiliser
une opération qui coûte plus cher que cette recherche, en utilisant
uniquement les opérations de base sur les listes. C'est un algorithme,
qui doit être récursif (pour ce qu'on comprend de la question initiale).

(En Python, il y a aussi les fonctions min()/max(), mais manifestement
ici il faut l'écrire soi-même.)

Enfin, je ne vois pas pourquoi trouver le min/max d'une liste devrait
détruire la liste à grands coups de del...

-- Alain.

debimax

unread,
Apr 30, 2021, 9:04:01 AM4/30/21
to
Bonjour

Comme le texte donne pour variable le mot pyramide es tu certain que ce
n'est pas une liste de liste (donc sous forme de pyramide) comme
0
1 2 3
4 5 6 7

ici pyramide = [[0], [1,2,3], [4,5,6,7]]

bref je verrai bien ton exercice comme le maximum d'une somme 'des
branches d'une pyramide par la programmation dynamique.


raph14

unread,
Apr 30, 2021, 10:56:08 AM4/30/21
to
Le jeudi 29 Avril 2021 à 22:38 par Benoit Izac :
> Bonjour,
>
> Le 29/04/2021 Í  21:38, raph a écrit dans le message
> Après, la «Â somme maximale »,
> ça n'a pas vraiment de sens. Est-ce la
> somme ou bien la valeur maximale que l'on cherche ? Vu le nom de la
> fonction «Â max_pyr », je dirais
> plutÍ´t la valeur maximale…
>
> La valeur maximale d'une liste c'est la plus grande valeur entre le
> premier élément et la valeur maximale des éléments
> suivants.
>
> NB : Tu me diras combien j'ai eu.
> --
> Benoit Izac
Bonjour,
Pour vous répondre il faut faire la somme maximale possible.
Donc 53.
J'avais réussi à trouver le nombre max de la liste mais il ne fallait pas faire
cela.

raph14

unread,
Apr 30, 2021, 10:57:45 AM4/30/21
to
Le jeudi 29 Avril 2021 à 22:38 par Benoit Izac :
> Bonjour,
>
> Le 29/04/2021 Í  21:38, raph a écrit dans le message
> Après, la «Â somme maximale »,
> ça n'a pas vraiment de sens. Est-ce la
> somme ou bien la valeur maximale que l'on cherche ? Vu le nom de la
> fonction «Â max_pyr », je dirais
> plutÍ´t la valeur maximale…
>
> La valeur maximale d'une liste c'est la plus grande valeur entre le
> premier élément et la valeur maximale des éléments
> suivants.
>
> NB : Tu me diras combien j'ai eu.
> --
> Benoit Izac
Bonjour,
Il faut trouver la somme maximale possible.
Donc 53.
J'avais déjà fait le code avec le nombre le plus grand de la liste mais il ne
fallait pas faire cela.

Olivier Miakinen

unread,
Apr 30, 2021, 11:06:44 AM4/30/21
to
Le 29/04/2021 22:38, Benoit Izac a écrit :
>
> Après, la « somme maximale », ça n'a pas vraiment de sens. Est-ce la
> somme ou bien la valeur maximale que l'on cherche ? Vu le nom de la
> fonction « max_pyr », je dirais plutôt la valeur maximale…

Et vu la réponse de raph14 c'est la somme.

Noter que je ne peux pas lui répondre parce que le « PEAR::Net_NNTP v1.5.0
(stable) » de Giganews met du 8-bits dans la champ Subject et que ça fait
buguer mon SeaMonkey.


--
Olivier Miakinen

Olivier Miakinen

unread,
Apr 30, 2021, 11:17:51 AM4/30/21
to
Le 30/04/2021 17:06, je répondais à Benoit Izac :
>
> Et vu la réponse de raph14 c'est la somme.
>
> Noter que je ne peux pas lui répondre parce que le « PEAR::Net_NNTP v1.5.0
> (stable) » de Giganews met du 8-bits dans la champ Subject et que ça fait
> buguer mon SeaMonkey.

En tout cas, si c'est bien la somme, et vu que je suis moi-même débutant
(un mois à peu près ?) je me permets de divulgacher la solution.

Première méthode :
========================================
def somme(liste):
return sum(liste)
========================================

Méthode récursive :
========================================
def somme(liste):
if len(liste) == 0:
return 0
return liste[0] + somme(liste[1:])
========================================


--
Olivier Miakinen

Alain Ketterlin

unread,
Apr 30, 2021, 12:14:04 PM4/30/21
to
Olivier Miakinen <om+...@miakinen.net> writes:

> Le 30/04/2021 17:06, je répondais à Benoit Izac :
>>
>> Et vu la réponse de raph14 c'est la somme.
>>
>> Noter que je ne peux pas lui répondre parce que le « PEAR::Net_NNTP v1.5.0
>> (stable) » de Giganews met du 8-bits dans la champ Subject et que ça fait
>> buguer mon SeaMonkey.
>
> En tout cas, si c'est bien la somme, et vu que je suis moi-même débutant
> (un mois à peu près ?) je me permets de divulgacher la solution.
>
> ========================================
> def somme(liste):
> return sum(liste)
> ========================================

Ou simplement :

somme = sum

> ========================================
> def somme(liste):
> if len(liste) == 0:
> return 0
> return liste[0] + somme(liste[1:])
> ========================================

Pour éviter la construction d'une nouvelle liste à chaque appel :

def somme (liste, i=0):
if i < len (liste):
return liste[i] + somme (liste, i+1)
else:
return 0

ou encore, pour faire le malin :

def somme (liste, i=0):
return liste[i] + somme (liste, i+1) if i < len (liste) else 0

mais clairement, les listes de Python ne sont pas vraiment faites pour
l'algorithmique récursive classique.

-- Alain.

raph14

unread,
Apr 30, 2021, 12:46:18 PM4/30/21
to
Le vendredi 30 Avril 2021 à 18:14 par Alain Ketterlin :
> Olivier Miakinen
>
>> Le 30/04/2021 17:06, je répondais Í  Benoit Izac :
>>>
>>> Et vu la réponse de raph14 c'est la somme.
>>>
>>> Noter que je ne peux pas lui répondre parce que le «
>>> PEAR::Net_NNTP v1.5.0
>>> (stable) » de Giganews met du 8-bits dans la champ Subject et que
>>> ça fait
>>> buguer mon SeaMonkey.
>>>
>>
>> En tout cas, si c'est bien la somme, et vu que je suis moi-même
>> débutant
>> (un mois Í  peu près ?) je me permets de divulgacher la
>> solution.
>>
>> ======================================= > def somme(liste):
>> return sum(liste)
>> =======================================
>>
> Ou simplement :
>
> somme = sum
>
>> ======================================= > def somme(liste):
>> if len(liste) == 0:
>> return 0
>> return liste[0] + somme(liste[1:])
>> =======================================
>>
> Pour éviter la construction d'une nouvelle liste Í  chaque
> appel :
>
> def somme (liste, i=0):
> if i < len (liste):
> return liste[i] + somme (liste, i+1)
> else:
> return 0
>
> ou encore, pour faire le malin :
>
> def somme (liste, i=0):
> return liste[i] + somme (liste, i+1) if i < len (liste) else 0
>
> mais clairement, les listes de Python ne sont pas vraiment faites pour
> l'algorithmique récursive classique.
>
> -- Alain.
Bonjour,
Je suis d'accord mais mon prof de terminale ne veut rien entendre ^^

Dominique

unread,
Apr 30, 2021, 12:46:21 PM4/30/21
to
Le 30/04/2021 à 15:03, debimax a écrit :

> bref je verrai bien ton exercice comme le maximum d'une somme 'des
> branches d'une pyramide par la programmation dynamique.

Bon, ben c'est décidé. Avec mes 6 mois de Python, mes 63 ans et mon BEPC
comme valeur maximale de mes diplômes, je confesse n'avoir rien compris :-)

Benoit Izac

unread,
Apr 30, 2021, 2:09:47 PM4/30/21
to
Bonjour,

Le 30/04/2021 à 17:17, Olivier Miakinen a écrit dans le message
<s6h72u$mo6$1...@cabale.usenet-fr.net> :

> Méthode récursive :
> ========================================
> def somme(liste):
> if len(liste) == 0:
> return 0
> return liste[0] + somme(liste[1:])
> ========================================

C'est exactement ce que j'aurais fait. Je suis d'accord que c'est pourri
de créer une nouvelle liste à chaque fois mais, vu que c'est déjà pourri
de le faire en recursif en Python, on n'est pas à ça près.

--
Benoit Izac

raph14

unread,
Apr 30, 2021, 3:04:39 PM4/30/21
to
Le vendredi 30 Avril 2021 à 20:09 par Benoit Izac :
> Bonjour,
>
> Le 30/04/2021 Í  17:17, Olivier Miakinen a écrit dans le
> message
>
>
>> Méthode récursive :
>> =======================================> def somme(liste):
>> if len(liste) == 0:
>> return 0
>> return liste[0] + somme(liste[1:])
>> ====================================== C'est exactement ce que j'aurais
fait.
>> Je suis d'accord que c'est pourri
>>
> de créer une nouvelle liste Í  chaque fois mais, vu que
> c'est déjÍ  pourri
> de le faire en recursif en Python, on n'est pas Í  ça
> près.
>
> --
> Benoit Izac
J'ai finis par réussir, voici le code pour ceux qu'ils le veulent :)
Et merci encore pour votre aide.
T = [4,7,5,5,2,6,9,3,8,4]
def somme(liste,result=0):
if len(liste)<=0:
return result
else:
result+=liste[0]
del liste[0]
return somme(liste, result)

Pour une pyramide contenant "4,7,5,5,2,6,9,3,8,4"

Benoit Izac

unread,
Apr 30, 2021, 3:15:49 PM4/30/21
to
Bonjour,

Le 30/04/2021 à 21:04, raph a écrit dans le message
<bPmdnVxpYv1byRH9...@giganews.com> :

> J'ai finis par réussir, voici le code pour ceux qu'ils le veulent :)
> Et merci encore pour votre aide.
> T = [4,7,5,5,2,6,9,3,8,4]
> def somme(liste,result=0):
> if len(liste)<=0:
> return result
> else:
> result+=liste[0]
> del liste[0]
> return somme(liste, result)

Mouais…

>>> T = [4,7,5,5,2,6,9,3,8,4]
>>> def somme(liste,result=0):
... if len(liste)<=0:
... return result
... else:
... result+=liste[0]
... del liste[0]
... return somme(liste, result)
...
>>> somme(T)
53
>>> T
[]

Oups !

--
Benoit Izac

debimax

unread,
Apr 30, 2021, 4:05:58 PM4/30/21
to
Le 30/04/2021 à 18:46, Dominique a écrit :
> Le 30/04/2021 à 15:03, debimax a écrit :
>
>> bref je verrai bien ton exercice comme le maximum d'une  somme 'des
>> branches d'une pyramide  par la programmation dynamique.
>
> Bon, ben c'est décidé. Avec mes 6 mois de Python, mes 63 ans et mon BEPC
> comme valeur maximale de mes diplômes, je confesse n'avoir rien compris :-)
>
>
Bonsoir dominique

https://fr.wikipedia.org/wiki/Programmation_dynamique?Pyramide%20de%20nombres#Pyramide_de_nombres


ce qui fait un truc comme ça

```python
p=[[3],[2,4],[2,7,5],[9,5,4,6]]


def sommeMaxR(p,i=0,j=0):
assert 0<=j<=i, 'Attention j doit être inférieur à i'
if i==len(p)-1:
return p[i][j]
else:
return p[i][j]+max(sommeMaxR(p,i+1,j), sommeMaxR(p,i+1,j+1))
sommeMaxR(p)
```

jean claude

Dominique

unread,
Apr 30, 2021, 10:39:15 PM4/30/21
to
Le 30/04/2021 à 22:05, debimax a écrit :

> Bonsoir dominique

Bonjour Jean-Claude,



>
> https://fr.wikipedia.org/wiki/Programmation_dynamique?Pyramide%20de%20nombres#Pyramide_de_nombres

Merci pour ce lien. C'est un niveau mathématique qui dépasse largement
le mien.

>
>
> ce qui fait un truc comme ça
>
> ```python
> p=[[3],[2,4],[2,7,5],[9,5,4,6]]
>
>
> def sommeMaxR(p,i=0,j=0):
> assert 0<=j<=i, 'Attention j doit être inférieur à i'
> if i==len(p)-1:
> return p[i][j]
> else:
> return p[i][j]+max(sommeMaxR(p,i+1,j), sommeMaxR(p,i+1,j+1))
> sommeMaxR(p)


Dès que je suis dans le TGV (dans 1 semaine), je dépouille ton script
ligne à ligne. Je comprendrai mieux.

Bien à toi,
0 new messages