Nombre de facon d'écrire une somme

Version imprimable

15/08/2017, 13h27
IDAOUBAKRIMHASSAN

Nombre de facon d'écrire une somme

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é :( 8O :( , 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
:) :) :)

Bonjour,

Je propose ceci :

Code:

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

Code:

NbSum(6)

affichera

Code:

:mouarf:

15/08/2017, 16h54
IDAOUBAKRIMHASSAN

Mais il faut considérer la possibilité d’écrire 6 comme 2+2+2 , avec 3 nombres ,4,5...etc
15/08/2017, 17h41
wiztricks

Salut,

Citation:

Envoyé par IDAOUBAKRIMHASSAN

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

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:

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:

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))

15/08/2017, 19h58
IDAOUBAKRIMHASSAN

Citation:

Envoyé par wiztricks

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 :D:D:D:D:D:D :) :) :) :)
15/08/2017, 20h11
IDAOUBAKRIMHASSAN

1 pièce(s) jointe(s)

Citation:

Envoyé par 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

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

Pièce jointe 303157

Merci d'avance :)
15/08/2017, 20h53
wiztricks

Citation:

Envoyé par IDAOUBAKRIMHASSAN

voici l'exercice

Pièce jointe 303157

Postez le code que vous avez fait, racontez ce que vous n'arrivez pas à faire fonctionner,...
L'intérêt d'un exercice est dans tout ce que vous allez découvrir en essayant de le faire. Le faire à votre place n'a aucun intérêt d'autant que des solutions existent et sont accessibles sur Internet.

- W

Avec combinations_with_replacement ça semble le faire, si on fait simple, le résultat attendu semble bon

Code:

1
2
3
4
5
6
7
8
from itertools import combinations_with_replacement
 
s = ''.join(map(str, range(2, 7)))
for i in range(1, 4):
    for k in combinations_with_replacement(s, i):
        my_sum = sum(map(int, k))
        if my_sum == 6:
            print('+'.join(k) if len(k)>1 else k[0])

Voilà la fonction decomposer si ça peut aider : (trouvée sur le net et retouchée):oops::P

Code:

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
# -*- coding: cp1252 -*-
import copy
 
def decomposer(n):
    global SOL
    SOL=[] # contiendra l'ensemble des solutions
    for i in range (0,n+1):
        SOL.append([]) # liste vide partout pour commencer
 
    SOL[0]=[] #pour le total 0
    SOL[1]=[[1]] #pour le total 1
    processdec(n)
 
    # la récurrence est amorcée
    # on va pouvoir y aller
 
#construit les solutions pour k à partir de celles pour k
def processdec1 (k):
    global SOL,SK
    T=copy.deepcopy(SOL[k]) # récupérer les solutions précédentes
    SK=[] # pour recevoir les nouvelles solutions
    for i in range(0,len(T)):# récupérer les solutions une par une
        L=T[i]
        for j in range (0,len(L)):
            M=copy.deepcopy(L)
            M[j]=M[j]+1 # ajout d'une unité
            if (j>0) and M[j-1]<M[j]: #pour conserver la décroissance
                continue
            else:
                if M not in SK: # s'il s'agit d'une nouvelle possibilité
                    SK.append(M) # l'ajouter à celles trouvées précédemment
    M=[1]*(k+1)# que des 1 pour finir
    SK.append(M)
    SOL[k+1]=SK # mise à jour en vue du traitement suivant
    if k>1:
        SOL[k-1]=[]#pour libérer la mémoire
    return
 
def processdec (n): # itération de la fonction précédente
    for k in range(0,n):
        processdec1(k)
        if k==n-1:
            printres(k)
    return
 
def printres(k): #Affichage du résultat en détail
    global SK
    print ("le nombre ",k+1," peut se decomposer de ",len(SK)," manieres differentes")
    print SK
 
decomposer(10)

Affichera :

Code:

1
2
('le nombre ', 10, ' peut se decomposer de ', 42, ' manieres differentes')
[[10], [9, 1], [8, 2], [7, 3], [6, 4], [5, 5], [8, 1, 1], [7, 2, 1], [6, 3, 1], [6, 2, 2], [5, 4, 1], [5, 3, 2], [4, 4, 2], [4, 3, 3], [7, 1, 1, 1], [6, 2, 1, 1], [5, 3, 1, 1], [5, 2, 2, 1], [4, 4, 1, 1], [4, 3, 2, 1], [4, 2, 2, 2], [3, 3, 3, 1], [3, 3, 2, 2], [6, 1, 1, 1, 1], [5, 2, 1, 1, 1], [4, 3, 1, 1, 1], [4, 2, 2, 1, 1], [3, 3, 2, 1, 1], [3, 2, 2, 2, 1], [2, 2, 2, 2, 2], [5, 1, 1, 1, 1, 1], [4, 2, 1, 1, 1, 1], [3, 3, 1, 1, 1, 1], [3, 2, 2, 1, 1, 1], [2, 2, 2, 2, 1, 1], [4, 1, 1, 1, 1, 1, 1], [3, 2, 1, 1, 1, 1, 1], [2, 2, 2, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

Par contre les histoires de récursivité je viens de me lancer...J'ai encore un peu de mal...