Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermée
#1 17-04-2018 12:40:57
- wade
- Membre
- Inscription : 10-03-2018
- Messages : 11
denombrement
Bonjour,pouvez vous m aider a resoudre cet exercice suivanr:
De combien de facons peut on descendre un escalier de 6 marches,sachant que l on peut descendre une,deux ou trois marches a la fois.
Hors ligne
#2 17-04-2018 13:41:57
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 049
Re : denombrement
Bonjour
Je ne sais pas si c'est la meilleure façon mais je ferai par recurrence : je compterais d'abord le nombre de façons de descendre un escalier à 1 marche, puis un escalier à deux marches, puis à 3 marches, etc...
F
En ligne
#3 18-04-2018 19:50:32
- wade
- Membre
- Inscription : 10-03-2018
- Messages : 11
Re : denombrement
Bonjour,en fait j ai essaye de faire par récurrence mais c' est un peu complique pour moi
Dernière modification par wade (18-04-2018 19:51:24)
Hors ligne
#4 18-04-2018 23:32:42
- D_john
- Invité
Re : denombrement
Bonsoir,
S'il y avait autant de marches qu'à la tour Eiffel, ça vaudrait la peine de chercher une méthode mais ici,
le plus simple pour répondre à cette question me semble l'arborescence :
L'arbre a 21 branches alors c'est pas la mort !
Courage...
#5 19-04-2018 16:30:42
- eldou
- Membre
- Inscription : 27-03-2018
- Messages : 18
Re : denombrement
Bonjour,
Si il faut combiner, dans ce cas, si je ne me trompe pas, ce serait :
[tex] _6C_1 + _6C_2 + _6C_3 [/tex] ?
Hors ligne
#6 19-04-2018 18:17:16
- D_john
- Invité
Re : denombrement
Salut eldou,
Je sais bien que parfois, on descend les maches 4 à 4 mais même en comptant ces possibilités (j'obtiens 29) je n'arrive pas au nombre que tu proposes (41). Je pense que wade ne reviendra pas alors je peux donner la bonne réponse : 24 possibilités.
A+
#7 19-04-2018 18:53:17
- eldou
- Membre
- Inscription : 27-03-2018
- Messages : 18
Re : denombrement
Bonjour D_john,
Merci pour la correction.
J'ai été trop vite, c'est un tort.
D'ailleurs, ça n' a pas de sens ce que j'ai proposé (combinaisons de marches).
Hors ligne
#8 19-04-2018 23:06:59
- eldou
- Membre
- Inscription : 27-03-2018
- Messages : 18
Re : denombrement
A vrai dire, j'apprends ...
En "googlant"; cet exercice de marche est lié à la suite de Fibonacci ?
Hors ligne
#9 20-04-2018 00:04:22
- D_john
- Invité
Re : denombrement
J’ai l’impression que les arbres ça ne te branche pas... c'est pourtant très simple.
Il s’agit de représenter graphiquement toutes les possibilités de descendre ces 6 marches par un arbre (à l’envers !).
On part de la marche n°6 (sur la première ligne).
Il y a 3 possibilités de descendre (sur la deuxième ligne) :
- soit 1 marche et on se retrouve sur la marche n°5 ;
- soit 2 marches et on se retrouve sur la marche n°4 ;
- soit 3 marches et on se retrouve sur la marche n°3 ;
On part de la marche n°5. Il y a 3 possibilités de descendre :
- soit 1 marche et on se retrouve sur la marche n°4 ;
- soit 2 marches et on se retrouve sur la marche n°3 ;
- soit 3 marches et on se retrouve sur la marche n°2 ;
etc. (et merci le copier coller !).
Quand on arrive à 0, la branche est terminée.
Quand toutes les branches sont à 0, il reste à les compter.
A toi de jouer... je te laisse terminer l’arbre.
6
/ | \
5 4 3
/ | \ / | \ / | \
4 3 2 3 2 1 2 1 0 (fin)
/ | \
3 2 1
#10 20-04-2018 08:51:55
- Ostap Bender
- Membre
- Inscription : 23-12-2015
- Messages : 242
Re : denombrement
Un programme python de débutant pour résoudre le problème et valider la solution 24.
def S(n):
if n<1:
return 0
elif n==1:
return 1
elif n==2:
return 2
elif n==3:
return 4
else:
return S(n-1)+S(n-2)+S(n-3)
print (S(6))
Ostap Bender
Hors ligne
#11 20-04-2018 10:47:00
- eldou
- Membre
- Inscription : 27-03-2018
- Messages : 18
Re : denombrement
Bonjour D_john,
En effet, je ne suis pas branché :-)
C'est à dire que le livre avec lequel j'apprends (Mathématiques de base, série Schaum) ne reprend pas le dénombrement par arbre. (Uniquement une brève théorie, avec théorèmes et exemples, ainsi que des exercices à résoudre).
Disons que j'étais en train de m'exercer avec les quelques exercices proposés sur ce lien, et que je suis tombé sur ce poste intitulé "dénombrement" (sous discussions des forums).
Dernière modification par eldou (20-04-2018 11:26:33)
Hors ligne
#12 22-04-2018 09:49:33
- eldou
- Membre
- Inscription : 27-03-2018
- Messages : 18
Re : denombrement
Un programme python de débutant pour résoudre le problème et valider la solution 24.
def S(n):
if n<1:
return 0
elif n==1:
return 1
elif n==2:
return 2
elif n==3:
return 4
else:
return S(n-1)+S(n-2)+S(n-3)print (S(6))
Ostap Bender
Je me suis trituré la tête, mais pas en vain. Pour la compréhension, le programme d'Ostap Bender se déroule de cette façon ?
1) La variable n=6 parcourt la fonction : n'étant pas inférieure à 1, ni égale à 1, 2 ou 3, elle s'appelle de nouveau avec n-1, donc n=5.
2) L'histoire se répète pour n =5 et n = 4
3) Arrivée à n=3 : la fonction retourne 4, et revient à la précédente n=4
4) S'étant arrêtée à n-1, elle continue en n-2, soit n=4-2, et retourne 2. Elle continue en n-3, soit n=4-3, et retourne 1.
5) Et ainsi de suite .. J'ai schématisé le déroulement ci-dessous (en jaune, les valeurs retournées)
Dernière modification par eldou (22-04-2018 10:58:24)
Hors ligne
#13 23-04-2018 15:10:31
- Ostap Bender
- Membre
- Inscription : 23-12-2015
- Messages : 242
Re : denombrement
Bonjour Elidou.
Le programme dit simplement que situ es sur la marche [tex]n\geq 4[/tex], tu n'as que trois possibilités qui s'excluent les unes les autres.
Tu descends d'une marche et il te reste S(n-1) possibilités.
Tu descends de deux marches et il te reste S(n-2) possibilités.
Tu descends de troismarches et il te reste S(n-3) possibilités.
Tu additionnes le tout, ça te donne S(n) possibilités.
Si tu développes en série entière [tex]S(x) = \dfrac 1{1-x-x^2-x^3} - 1[/tex] au voisinage de zéro, tu verras apparaître tes coefficients. Vois-tu pourquoi ?
Tu peux ensuite décomposer ta fraction en éléments simples pour avoir une expression fermée pour ces nombres. Moi je n'en ai pas le courage, rien de résoudre l'équation du troisième degré...
Ostap Bender
Hors ligne
#14 23-04-2018 17:51:55
- eldou
- Membre
- Inscription : 27-03-2018
- Messages : 18
Re : denombrement
Salut Ostap Blender,
Honnêtement, je ne suis pas si loin en math. Quésako, série entière ? Donc, non, je ne vois pas. Désolé et merci, en même temps. J'ai simplement compris le déroulement récursif du programme, c'est déjà cela de pris. Grâce aux exercices proposés sur geeksforgeeks.
Dans mon bouquin, en reprenant l'index, je lis séries entières, page 172 ;-). Je ne suis qu'à la fin du chapitre des probabilités, page 137.
Donc, j'y approche...
Pour mon apprentissage, je n'ai pas de contraintes de temps (contrairement à un étudiant), je fais cela récréativement. C'est ce qui rend plus agréable.
Hors ligne
#15 24-04-2018 15:09:36
- Ostap Bender
- Membre
- Inscription : 23-12-2015
- Messages : 242
Re : denombrement
Bonjour Eldou.
Une autre approche est de considérer que la suite [tex]S(n)[/tex] vérifie une récurrence lnéaire
[tex]S(n)-S(n-1)-S(n-2)-S(n-3)=0[/tex].
Soit [tex]a[/tex] la racine réelle de l'équation [tex]x^3-x^2-x-1=0 [/tex], [tex]b[/tex] etb[tex]\overline b[/tex] les racines irréelles de cette équation,
Les solutions (réelles) de cette récurrence linéaire sont les suites [tex](u_n)[/tex] définies par
[tex]u_n=Aa^n+Bb^n+\overline B (\overline b)^n[/tex] où [tex]A[/tex] et [tex]B[/tex] sont déterminées par les conditions initiales
[tex]\left\lbrace \begin{array}{rcccccl}
Aa&+&Bb&+&\overline B \overline b&=&1\\
Aa^2&+&Bb^2&+&\overline B (\overline b)^2&=&2\\
Aa^3&+&Bb^3&+&\overline B (\overline b)^3&=&4
\end{array}\right.
[/tex]
Ostap Bender
Hors ligne
#16 25-04-2018 16:10:09
- wade
- Membre
- Inscription : 10-03-2018
- Messages : 11
Re : denombrement
mercie !
Hors ligne
#17 20-06-2018 10:17:33
- Black Jack
- Membre
- Inscription : 15-12-2017
- Messages : 470
Re : denombrement
Salut,
Avec d'aussi petits nombres, même sans maîtriser le sujet, on peut arriver à tout lister.
Ce n'est pas une "bonne" méthode, mais cela doit permettre de vérifier si on ne s'est pas planté en réfléchissant par les méthodes probablement attendues (combinaisons et autres)
1 1 1 1 1 1 --> 1 possibilité.
1 1 1 1 2 --> 5 possibilités. (qui sont : 11112, 11121, 11211,12111,21111)
1 1 2 2 --> 6 possibilités. (qui sont : 1122,1212,1221,2211,2121,2112)
2 2 2 --> 1 possibilités.
1 2 3 --> 6 possibilités. (qui sont : ...)
3 3 --> 1 possibilités.
1 1 1 3 --> 4 possibilités. (qui sont : ...)
Total = 1 + 5 + 6 + 1 + 6 + 1 + 4 = 24 possibilités.
Hors ligne
#18 20-06-2018 16:09:12
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : denombrement
Salut,
non, non, c'est très bien comme ça, c'est astucieux et je ne pense pas qu'on cherche à faire faire des calculs plus sioux.
Je pense qu'on cherche plutôt à tester le bon sens propre au bon matheux !
De la considération des obstacles vient l’échec, des moyens, la réussite.
Hors ligne
Pages : 1
Discussion fermée