Discussion :

[mystral]

Bonjour à tous, voilà je cherche une solution à un programme, je souhaite repartir un entier A en plusieurs entiers N dont la somme donnera le nombre A.

exemple j'ai un montant 40000 que je veux repartir en 7
1- 10000
2- 5000
3- 5000
4- 5000
5- 5000
6- 5000
7- 5000

ou encore le nombre 120000

1- 20000
2- 20000
3- 20000
4- 15000
5- 15000
6- 15000
7- 15000

[Trap D]

Voila un code tout prêt en Python : les commentaires te permettront de comprendre

Code Python :

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
from constraint import *
 
# calcul du nombre de possibilités de cases blanches sur une rangée
# c'est ici qu'une bibliothèque de contraintes est utile !
# les arguments passés sont le nombre d'intervalles à calculer et
# le maximum possible pour les intervalles
def get_intervals(Nb, Max) :
    # Les variables en jeu sont nommées
    # on est donc ici limité à un maximum de 25 séquences de cases noires sur une ligne !
    all_keys = "abcdefghijklmnopqrstuvwxyz"
 
    # On a besoin de listes de valeurs à associées à chaque variable
    # Rappelons que les valeurs définies par le range s'arrètent à Max
    min = [i for i in range(Max+1)]
    max = [i for i in range(1,Max+1)]
    # création d'une instance de problème à résoudre
    problem = Problem()
 
    # Le premier intervalle peut être vide
    # (les cases noires démarrent au bord de la grille)
    problem.addVariable("a", min)
 
    # Entre les cases noires, il faut au moins une case blanche
    for i in range(1, Nb) :
        problem.addVariable(all_keys[i], max)
 
    # Le dernier intervalle peut être vide.
    problem.addVariable(all_keys[Nb], min)
 
    # La somme des cases noires doit être exactement Max.
    problem.addConstraint(ExactSumConstraint(Max))
 
    # on récumère les solutions
    Res = problem.getSolutions()
 
    # on met maintenant les solutions en forme pour les utiliser dans la suite du programme
    # il existe sans doute une écriture plus "Python" que celle que j'ai écrite
    Resultat = []
    for r in Res :
        item = []
        keys = list(r.keys())
        for i in range(Nb+1) :
            for u in keys :
                if all_keys[i] == u :
                    item.append(r[u])
        Resultat.append(item)
 
    return Resultat

Il faut installer une bibliothèque de contraintes que tu peux trouver ici

[tbc92]

Bonjour à tous, voilà je cherche une solution à un programme, je souhaite repartir un entier A en plusieurs entiers N dont la somme donnera le nombre A.

exemple j'ai un montant 40000 que je veux repartir en 7
1- 10000
2- 5000
3- 5000
4- 5000
5- 5000
6- 5000
7- 5000

ou encore le nombre 120000

1- 20000
2- 20000
3- 20000
4- 15000
5- 15000
6- 15000
7- 15000

Pour décomposer 40000, tu aurais pu choisir par exemple, 569+6776+10001+2049+3144+13391+4070 ... ou une multitude d'autres solutions.
Mais tu as choisi une solution assez particulière, avec le même nombre répété 6 fois,et avec des nombres tous multiples de 1000. C'est une coïncidence ou pas ?

Et si tu devais décomposer 41234 en 7 nombres tu choisirais quels nombres, selon quels critères ?

[Skoukou007]

Bonjour tout le monde, j'ai besoin d'aide concernant la programmation d'un algorithme que je dois faire d'ici 3 jours et qui doit être mis dans le language de la Ti-nspire. Alors voilà ce dont j'ai besoin: Décomposer un nombre entier avec la somme de nombres entiers. Par exemple : 4=2+2 et 4=1+1+1+1 et 4=3+1 et 4=4 (facultatif ce serait bien si l'algorithme ne répète pas deux fois la même décomposition comme 4=3+1 et 4=1+3). Pensez-vous que ce serait possible? Bon voilà, je vous défie de le faire car je pense que c'est un peu trop compliqué ^^.

Merci d'avance! Et bonne chance.

[picodev]

Bonjour,

Quand on a besoin d'aide on ne défie pas. On pose la question en montrant qu'on s'est un donné du mal pour trouver la réponse, on reste humble ...

Passe une bonne journée.

[Flodelarab]

Bonjour,

je pense que c'est un peu trop compliqué

Au contraire c'est très simple.

[Flodelarab]

Bonjour,

pour faire tous les cas possibles, il n'a pas besoin de bibliothèque mais plutôt d'huile de coude et une boucle.

[picodev]

Bonjour,

tbc92 a raison, sans plus de contraintes tu ne pourras jamais réellement calculer toutes les façons de faire. Ce que tu cherches à obtenir sont les k-partitions non ordonnées d'un entier n sans employer le 0, c'est-à-dire la manière de décomposer un entier n en k entiers strictement positifs dont la somme vaut n sachant que l'ordre des k entiers n'importe pas. Je noterai T(n,k) le nombres de k-partitions non ordonnées de l'entier n. Par exemple T(5,2) = 2 car il y a deux manière de décomposer 5 en somme de deux entiers : 5=1+4=2+3 (les 4+1 et 3+2 ne sont pas comptés).

Il y a une formule de récurrence pour trouver T(n,k) :

T(n,1) = T(n,n) = 1
si n<k, T(n,k)=0
sinon T(n,k)=T(n-1,k-1)+T(n-k,k)

Tu auras T(n,7) façons possibles pour tes exemples, ces nombres grandissent très vite :

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
n	    T(n,7)	log(T(n,7)/log(n)
10	         3	0.477121
20	        82	1.470999
30	       618	1.889478
40	      2738	2.145633
50	      8946	2.325897
60	     23961	2.462954
70	     55748	2.572345
80	    116742	2.662631
90	    225286	2.739033
100	    407254	2.804933
150	   4097732	3.038725
200	  21591496	3.187391
250	  79192479	3.293946
300	 230282157	3.375798
350	 569704489	3.441594
400	1251251004	3.496209
500	4677232746	3.582844

[tbc92]

Mystral n'a pas précisé son besoin, mais à priori, voici ce qu'il veut faire, avec en prime l'algorithme pour le faire

1. Etablir une liste de nombre 'éligibles'. En gros, j'imagine que les nombres considérés comme éligibles par mystral sont : 1 2 3 5 10 15 20 30 50 100 150 200 300 500 1000 1500 2000 3000 5000 10000 15000 20000 30000 50000 100000 150000 ... etc

2. A partir d'un nombre N à répartir en p portions, on va diviser N par p, ce qui donne un certain dividende D.
Et on va prendre dans la liste des nombres éligibles le nombre le plus proche de D.

Puis on peut boucler, puisqu'à présent, le problème est de constituer N-D en (p-1) nombres entiers.

Sur l'exemple pour 120000 :
120000/7 donne 17143, arrondi à 15000. Reste 12000-15000=105000 à répartir en somme de 6 nombres.
105000/6 donne 17500, arrondi à 15000 ( ou 20000, ça ne change rien au final)
90000/5 donne 18000, arrondi à 20000
70000/4 donne 17500, arrondi à 15000
55000/3 donne 18333, arrondi à 20000
35000/2 donne 17500, arrondi à 15000
Et pour le dernier nombre, on est obligé de prendre le reste 20000 ... tant mieux si ce nombre tombre dans la liste des nombres 'éligibles', mais ce n'est pas garanti.

Et sur l'exemple pour 40000 :
40000/7 = 5714, arrondi à 5000
35000/6 = 5833, arrondi à 5000
30000/5 = 6000, arrondi à 5000
25000/4 = 6250, arrondi à 5000
20000/3 = 6667, arrondi à 5000
15000/2 = 7500, arrondi à 5000
reste : 10000

[tbc92]

Pour parler de défi, il faut qu'il y ait un enjeu, un challenge, ou au moins une difficulté.
Ici, rien de tout ça.

[AdmChiMay]

Bonjour,

Je pense que tu étais d'humeur à discuter comme entre copains, mais ta pointe d'humour (je suppose, à cause du ^^), ne passe pas forcément avec les autres, qui peuvent aussi avoir des jours chargés. Et de fait, tu viens surtout de perdre une journée. Comme tout forum, celui-ci a une charte, qu'il est utile de lire. Bref, quand on a une urgence dans ses devoirs, on ne mets pas les autres au défi de le faire (valable même en post-bac).

Je te suggère de reformuler ton problème :
- Quelle est la question ? (ok, ça c'est bon)
- Quelle est la portée de tes exemples ? Quelle décomposition cherches-tu ? En cherches-tu une seule ? plusieurs ? toutes ? Ton entier a-t-il une valeur minimale, maximale ? Bref, toutes les contraintes données.

Ensuite, tes exemples en eux-même te donnent des pistes de réflexion, rien qu'à les lire ils sont "parlants".
Et maintenant, le point clef : qu'as-tu à proposer comme début de solution ? (et pas juste début - lire n - points de suspensions - fin).

Bon courage, sur 2 jours il est encore temps d'y arriver.

[Edit] Lorsque j'ai écris ce matin, trois des messages précédents ne s'affichaient pas...