Discussion :

[IDAOUBAKRIMHASSAN]

Bonjour,

SVP, je dois réaliser ce sujet :
Ecrire une fonction nbsum qui prend comme argument un nombre n et qui renvoie le nombre de façons d'écrire une somme égale à n (on comptera une seule fois les commutations).


Ayant beaucoup de mal avec la récursivité , et après plusieurs tentatives je m'adresse à vous.

OU bien Ecrire une fct récursive partition(n,m) qui prend en entrée deux entiers positifs n et m , et rend le nombre de manières d'écrire n comme somme d'entiers supérieures ou égaux à m (sans ordre). par ex partition(6,2) rrendra 4 , car 6 peut s'écrire : 6,4+2, 3+3, 2+2+2

Pourriez vous m'aider a trouver une methode permettant de réaliser cette fonction, et m'expliquer les différentes étapes ?

Merci d'avance

[Fawn_noOb_wxPython]

Bonjour,

Je propose ceci :

Code :

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

1
2
3
4
5
6
7
8
# -*- coding: cp1252 -*-
def NbSum(n):
    i=0 #On met i à 0
    while i<n: 
        diff=n-i #On fait la différence
        if diff>=i:#On affiche une fois les commutations
            print str(diff)+"+"+str(i) #On affiche
        i+=1#on incrémente

ou

Code :

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

NbSum(6)

affichera

Code :

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

1
2
3
4
6+0
5+1
4+2
3+3

[IDAOUBAKRIMHASSAN]

Mais il faut considérer la possibilité d’écrire 6 comme 2+2+2 , avec 3 nombres ,4,5...etc

[wiztricks]

Salut,

Pourriez vous m'aider a trouver une methode permettant de réaliser cette fonction, et m'expliquer les différentes étapes ?

La première étape sera de définir/choisir un des algorithmes que vous allez trouver sur Internet ou dans le forum de la rubrique algorithmique. Sans çà, vous ne savez pas encore ce que vous voulez coder... Après, il va falloir traduire cela en Python et définir des jeux de tests qui permettront d'assurer que çà a été codé correctement.


- W

[fred1599]

Bonjour,

Ça ne répond pas à la question de la récursivité, mais comme je trouvais l'exercice intéressant, je m'y suis attelé à ma manière

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
from itertools import product
def partition(n, m, k):
    count = 0
    numbers = list(map(str, range(m, n))
    for i in product(numbers, repeat=k):
        my_sum = sum(map(int, i))
        if my_sum == n:
            print('+'.join(i))
            count += 1
    return count
 
MAX = 6
MIN = 2
 
possibilities = 0
for i in range(MIN, MAX-MIN):
    possibilities += partition(MAX, MIN, i)
print("Possibilités : {}".format(possibilities))

Avec le module itertools et sa fonction product, ça rend les choses beaucoup plus simples...

Plus simple sans l'affichage des opérations

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
def partition(n, m, k):
    count = 0
    numbers = range(m, n+1)
    for i in product(numbers, repeat=k):
        my_sum = sum(i)
        if my_sum == n:
            count += 1
    return count
 
MAX = 6
MIN = 2
 
possibilities = 0
for i in range(MIN, MAX-MIN):
    possibilities += partition(MAX, MIN, i)
print("Possibilités : {}".format(possibilities))

[IDAOUBAKRIMHASSAN]

Bonjour,

Ça ne répond pas à la question de la récursivité, mais comme je trouvais l'exercice intéressant, je m'y suis attelé à ma manière

Merci beaucoup Monsieur Fred ,mais, Avez vous une solution pour éviter de calculer les mêmes manières deux fois comme 4+2 , 2+4 ?

voici l'exercice



Merci d'avance

[IDAOUBAKRIMHASSAN]

Salut,



La première étape sera de définir/choisir un des algorithmes que vous allez trouver sur Internet ou dans le forum de la rubrique algorithmique. Sans çà, vous ne savez pas encore ce que vous voulez coder... Après, il va falloir traduire cela en Python et définir des jeux de tests qui permettront d'assurer que çà a été codé correctement.


- W

Salut , OK Merci beaucoup