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]

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

[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

[wiztricks]

voici l'exercice

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

[fred1599]

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

Code :

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

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

[Fawn_noOb_wxPython]

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

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
# -*- 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 :

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

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