Math forum
Les maths ont leur forum !
Les Cours Thierry
Cours de mathématiques et soutien scolaire par le webmaster de Math foru'
RUBRIQUES

 
Cours & Math-fiches

 
Math foru' sur Facebook


 
Rechercher dans les forums Derniers messages S'inscrire pour poster des messages S'inscrire pour poster des messages
vers le sujet précédent vers le sujet suivant
Modéré par: Thierry, mathtous
Fin 

Ecriture d'un entier comme la somme d'une suite d'entiers ordonnés

- classé dans : Enigmes

Envoyé: 25.07.2007, 00:32



enregistré depuis: juil.. 2007
Messages: 1

Status: hors ligne
dernière visite: 25.07.07
Bonjour,

dans le cas d'un calcul de probas, je suis amené à résoudre le problème suivant :

Soit m un entier positif. Je cherche à déterminer l'ensemble de n-uplets qui permettent d'écrire m sous la forme :



avec la contrainte

Par exemple, pour et , on trouve 5 triplets :

(5,0,0)
(4,1,0)
(3,2,0)
(3,1,1)
(2,2,1)

Mes questions sont les suivantes :

1/ Est-ce un problème connu en mathématiques ? Si oui, pouvez-vous svp m'indiquer un lien traitant de ce problème.

2/ Quel est le cardinal de l'ensemble des n-uplets, ?

3/ Y a t'il un moyen simple de générer cet ensemble ? J'ai écrit un programme qui génère cet ensemble, mais je le trouve compliqué (plein de if, while, ...)... Il y a peut-être moyen de faire plus simple.

Merci d'avance pour vos réponses.

Moniksdad.
Top 
 
Envoyé: 25.07.2007, 03:01

Modérateur


enregistré depuis: juin. 2005
Messages: 1469

Status: hors ligne
dernière visite: 24.02.13
Salut.

1) Aucune idée. icon_frown

2) J'aurais tendance à dire qu'il est infini : pour tout n il existe au minimum une solution qui est (m;0;0;...;0) avec n-1 zéros. Donc le cardinal de ton ensemble est supérieur à celui des entiers naturels qui lui est infini. icon_smile

3) Si on aime faire griller son ordinateur on teste toutes les solutions une par une. Le problème est qu'il faudrait alors envisager n parmi m+1 n-uplets, et ça c'est pas cool parce que ça fait beaucoup très rapidement.

Sinon on réfléchit 2 secondes à comment générer l'ensemble sans jamais passer par les n-uplets qui ne conviennent pas : on ne construit que ceux qui marchent. C'est peut-être comme ça que tu as fait.

Bon moi j'ai une idée, mais ça utilise ce que l'on appelle une fonction récursive. Ne connaissant pas ton niveau en programmation, je vais t'expliquer rapidement ce que c'est.

Une fonction récursive est une fonction qui s'appelle elle-même. Pour que ce soit clair, écrivons une fonction appelée "factorielle" qui prend comme argument un nombre n, et qui retourne n!.

factorielle(n)
{
if (n == 1) return 1;
else return n*factorielle(n-1);
}

Si on exécute factorielle(3); la fonction va renvoyer la valeur 6.

En fait au début n=3, alors la fonction va calculer 3*factorielle(2).
Puis comme n=2, la fonction va calculer 2*factorielle(1).
Enfin, comme n=1, la fonction ne renvoie que 1.

Je ne sais pas si tu as compris, mais si tu ne connaissais pas cette façon de coder, et bien sache que c'est super pratique vu que l'on n'a plus besoin d'en écrire des tonnes.

Par exemple si elle n'était pas récursive on aurait pu l'écrire autrement :

factorielle(n)
{
total = n;

while (n-- > 1) total *= n;

return total;
}

Et on a gagné une boucle while !

Pour ne pas utiliser la fonction factorielle à l'infini, on a utilisé ce que l'on appelle un critère d'arrêt : if (n == 1); qui permet d'empêcher la fonction de s'appeler elle-même.

Le rapport avec ton problème ? Et bien je ne sais pas trop comme l'expliquer sans l'écrire en fait. On exploite le fait que les nombres soient en ordre décroissant.

Par exemple décomposons m=10 dans des n-uplets de taille n=4.

(10;0;0;0)
(9;1;0;0)
(8;2;0;0)
(8;1;1;0)
(7;3;0;0)
(7;2;1;0)
(7;1;1;1)
(6;4;0;0)
(6;3;1;0)
(6;2;2;0)
(6;2;1;1)
(5;5;0;0)
etc.

Regarde par les n-uplets de la forme (6;...). On a, à droite, si on enlève le 6, les groupes :

(4;0;0)
(3;1;0)
(2;2;0)
(2;1;1)

Et ça c'est la résolution du problème pour m=4 et n=3 !
Continuons en regardant à droite des 2 :

(2;0)
(1;1)

C'est la résolution du problème pour m=2 et n=2 ! Tu commences à comprendre ?

Jusqu'à ce que n=1 ou m=0 (les critères d'arrêts), par exemple à côté du "4" et du "3;1" c'était le cas, tu appelles la fonction récursive qui te génèrerait des ensembles de plus en plus petits.

Je m'arrête là pour le moment, dis-moi si tu as compris ou non ce que j'ai raconté. Et autre chose importante : tu codes en quel langage ? Parce que selon le langage la valeur renvoyée par la fonction ne serait pas forcément la même, voire on ferait sans (en C par exemple ce serait le cas vu que je prévoyais de renvoyer des tableaux alors que là il faudrait s'amuser avec des pointeurs). icon_smile

@+
Top 


Boîte de connexion

 Bienvenue invité
Inscris-toi c'est gratuit !



Rejoins-nous afin de poser tes questions dans les forums de Math foru' :

 Crée ton compte
 Connexion :
Pseudo :


Mot de passe :


Retenir


Identifiants perdus ?
Membres
Dernier Nouveaux aujourd'hui0
Dernier Nouveaux hier1
Dernier Total13132
Dernier Dernier
aimé
 
Liens commerciaux