Vous n'êtes pas connecté. Connectez-vous ou enregistrez-vous

 » Mathématiques » Mathématiques dans l'Enseignement Supérieur » 

Problème mathématique [ Ensemble et récursivité]


Voir le sujet précédent Voir le sujet suivant Aller en bas  Message [Page 1 sur 1]

Drspinoza


Posteur Débutant
Posteur Débutant
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.

Voir le profil de l'utilisateur

Professeur J

avatar
Professeur de Mathématiques
Professeur de Mathématiques
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$.

Voir le profil de l'utilisateur http://www.mathsendirect.fr

Drspinoza


Posteur Débutant
Posteur Débutant
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é :/

Voir le profil de l'utilisateur

Professeur J

avatar
Professeur de Mathématiques
Professeur de Mathématiques
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$.

Voir le profil de l'utilisateur http://www.mathsendirect.fr

Drspinoza


Posteur Débutant
Posteur Débutant
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.

Voir le profil de l'utilisateur

Drspinoza


Posteur Débutant
Posteur Débutant

Ce devoir me rend fou  Sad

Voir le profil de l'utilisateur

Professeur J

avatar
Professeur de Mathématiques
Professeur de Mathématiques
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).

Voir le profil de l'utilisateur http://www.mathsendirect.fr

Drspinoza


Posteur Débutant
Posteur Débutant
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,

Voir le profil de l'utilisateur

Professeur J

avatar
Professeur de Mathématiques
Professeur de Mathématiques
Je t'en prie. Par contre, je te conseille de prendre ton cours pour ce qui est des notations, etc.

Voir le profil de l'utilisateur http://www.mathsendirect.fr

Contenu sponsorisé


Voir le sujet précédent Voir le sujet suivant Revenir en haut  Message [Page 1 sur 1]

Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum