Somme, récursive

Le
raph14 offline Hors ligne
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
  • Partager ce contenu :
Vos réponses Page 1 / 2
Trier par : date / pertinence
Benoit Izac
Le #26572574
Bonjour,
Le 29/04/2021 Í  21:38, raph a écrit dans le message
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
Le #26572587
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
Le #26572613
Dominique
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
Le #26572628
Le 29/04/2021 Í  21:38, raph14 a écrit :
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


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 offline Hors ligne
Le #26572634
Le jeudi 29 Avril 2021 à 22:38 par Benoit Izac :
Bonjour,

Le 29/04/2021 Í  21:38, raph a écrit dans le message
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


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 offline Hors ligne
Le #26572635
Le jeudi 29 Avril 2021 à 22:38 par Benoit Izac :
Bonjour,

Le 29/04/2021 Í  21:38, raph a écrit dans le message
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


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
Le #26572637
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
Alain Ketterlin
Le #26572641
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.
raph14 offline Hors ligne
Le #26572644
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
Le #26572648
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 :-)
--
Dominique
Courriel : dominique point sextant ate orange en France
Esto quod es
Poster une réponse
Anonyme