- DrspinozaPosteur Débutant
- Messages : 5
Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 21:55
Salut,
Je ne vous demande pas de répondre à ma place mais peut-être pourriez-vous m'aider à mieux comprendre parce-que je ne sais pas par ou commencer.
On s'intéresse a l’ensemble C des clôtures solides. Elles sont construites avec
des poteaux, représentés par le symbole ‘|’, et des traverses, représentées par le
symbole ‘×’. Par exemple, les clôtures “|×|×|” et “|×|||×||” sont solides, alors
que les clôtures “| × |×” et “| × ×|” ne le sont pas. On définit récursivement
l’ensemble C de la fa¸con suivante.
1. La chaîne “| × |” appartient `a C.
2. Si c ∈ C, alors les chaines “c|” et “c × |” sont dans C.
La longueur d’une clôture est le nombre de traverses que la clôtures possède.
a) Donnez une définition récursive de la fonction L(c) qui calcule la longueur
d’une clôture c.
b) Donnez une définition récursive de la fonction P(c) qui calcule le nombre de
poteaux d’une clôture c.
c) Montrez, par induction, qu’une clôture solide a toujours un nombre de poteaux
strictement supérieur à sa longueur. Aide : faites l’induction sur le nombre
de fois ou la règle 2 a été appliquée.
Je ne vous demande pas de répondre à ma place mais peut-être pourriez-vous m'aider à mieux comprendre parce-que je ne sais pas par ou commencer.
On s'intéresse a l’ensemble C des clôtures solides. Elles sont construites avec
des poteaux, représentés par le symbole ‘|’, et des traverses, représentées par le
symbole ‘×’. Par exemple, les clôtures “|×|×|” et “|×|||×||” sont solides, alors
que les clôtures “| × |×” et “| × ×|” ne le sont pas. On définit récursivement
l’ensemble C de la fa¸con suivante.
1. La chaîne “| × |” appartient `a C.
2. Si c ∈ C, alors les chaines “c|” et “c × |” sont dans C.
La longueur d’une clôture est le nombre de traverses que la clôtures possède.
a) Donnez une définition récursive de la fonction L(c) qui calcule la longueur
d’une clôture c.
b) Donnez une définition récursive de la fonction P(c) qui calcule le nombre de
poteaux d’une clôture c.
c) Montrez, par induction, qu’une clôture solide a toujours un nombre de poteaux
strictement supérieur à sa longueur. Aide : faites l’induction sur le nombre
de fois ou la règle 2 a été appliquée.
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 22:11
Salut, ça ressemble à de l'algorithmique, je vais essayer de t'aider comme je peux^^
Pour la première question, tu peux écrire quelque chose du genre (dépend des notations que tu utilises) :
Si $c$ est une clôture, on lit de gauche à droite les poteaux et les traverses. Si le premier caractère est un poteau, on pose $L(c)=L(c')$ où $c'$ est la même clôture en ayant supprimé le premier caractère. Au contre, si le premier caractère est une traverse, tu poses $L(c)=L(c')+1$.
Pour la première question, tu peux écrire quelque chose du genre (dépend des notations que tu utilises) :
Si $c$ est une clôture, on lit de gauche à droite les poteaux et les traverses. Si le premier caractère est un poteau, on pose $L(c)=L(c')$ où $c'$ est la même clôture en ayant supprimé le premier caractère. Au contre, si le premier caractère est une traverse, tu poses $L(c)=L(c')+1$.
- DrspinozaPosteur Débutant
- Messages : 5
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 22:44
Ok donc la définition récursive ça me donne un truc.
Si il y'a une traverse dans le prochain caractère alors:
L(c+1) = L(c) + 1 ?
Sinon :
L(c+1) = L(c).
Mm je pense que j'ai pas bien compris désolé :/
Si il y'a une traverse dans le prochain caractère alors:
L(c+1) = L(c) + 1 ?
Sinon :
L(c+1) = L(c).
Mm je pense que j'ai pas bien compris désolé :/
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 22:52
Moi je comprends pas trop ce que tu as écrit^^ C'est quoi $L(c+1)$ ? Faut se rappeler que $L(c)$ c'est la longueur de $c$.
- DrspinozaPosteur Débutant
- Messages : 5
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 22:58
Je suis un peu mélangé.
Normalement dans mes cours de récursivité on utilise toujours le P(n+1) pour prouver que la fonction P(n) est vraie.
Mais si je continue sur ton raisonnement L(c') représente quoi.
Et pour la deuxième question P(c) = P(c') si le premier caractère est une traverse et P(c) = P(c')+1 si il s'agit d'un poteau.
Ce qui revient a la même formule.
Je trouve vu la difficulté des questions précédentes que la réponse de cet exercice semble beaucoup trop basique.
Normalement dans mes cours de récursivité on utilise toujours le P(n+1) pour prouver que la fonction P(n) est vraie.
Mais si je continue sur ton raisonnement L(c') représente quoi.
Et pour la deuxième question P(c) = P(c') si le premier caractère est une traverse et P(c) = P(c')+1 si il s'agit d'un poteau.
Ce qui revient a la même formule.
Je trouve vu la difficulté des questions précédentes que la réponse de cet exercice semble beaucoup trop basique.
- DrspinozaPosteur Débutant
- Messages : 5
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 23:11
Ce devoir me rend fou
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 23:12
Je t'ai écrit ce qu'était $c'$ : c'est la même clôture à laquelle on a enlevé le premier caractère. Peut-être que c'est mieux avec un exemple ?
Si je veux calculer la longueur de la clôture : $||x||$ (de tête on sait qu'on doit arriver à $1$).
Tu as $L(||x||)=L(|x||)=L(x||)=L(||)+1=L(|)+1=L()+1=1$
Ici, on a évidemment $L()=0$ (longueur nulle pour une clôture... vide).
Si je veux calculer la longueur de la clôture : $||x||$ (de tête on sait qu'on doit arriver à $1$).
Tu as $L(||x||)=L(|x||)=L(x||)=L(||)+1=L(|)+1=L()+1=1$
Ici, on a évidemment $L()=0$ (longueur nulle pour une clôture... vide).
- DrspinozaPosteur Débutant
- Messages : 5
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 23:17
Ok je comprend mieu merci, donc c'est comme ça que ça fonctionne.
Il me reste plus qu'à chercher comment rédiger tout ça.
J'ai une idée de comment résoudre la question 3 mais si j'arrive pas je reviens haha ^^.
Merci beaucoup,
Il me reste plus qu'à chercher comment rédiger tout ça.
J'ai une idée de comment résoudre la question 3 mais si j'arrive pas je reviens haha ^^.
Merci beaucoup,
Re: Problème mathématique [ Ensemble et récursivité]
Dim 6 Déc - 23:20
Je t'en prie. Par contre, je te conseille de prendre ton cours pour ce qui est des notations, etc.
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|