Récursivité - examen

[Antoon]

Bonjour,

J'ai un examen de fin de session en Maths puis je suis complètement perdu.
C'est à rendre demain.
J'ai fais la moitié des exercices mais l'autre moitié je n'y comprend absolument rien.
Ce que je demande, n'est pas la réponse mais des explications car j'ai un autre examen dans une semaine.

Ces exercices sont focalisés surtout sur la récursivité.

Question 5.

On considère la fonction récursive ci-dessous
A(0,n)=n, n=0, 1, 2, 3 ...
A(m,0)=m, m=10, 1, 2, 3 ...
A(m,n)=A(m-1;A(m,n-1))

a) Montre par induction(preuve récursive) que A(1,n)=1, pour tout n.

Alors pour ça j'ai pensé à gaire A(1,n+1)=A(1-1, A(n+1-1))
Et la je bloque à A(1,n+1)=A(0, A(n))
Ca fait A(0,n) ?

b) Utilisez a) pour montrer que A(2,n)=1, pour tout n>=1.

?!



Question 6
f(m,0) = m, pour m = 0, 1, 2, 3 ...
f(m, n) = m x f(m, n - 1) pour m=0, 1, 2, 3 .. et n = 1, 2, ...

Calculer f(5,2) et f(6,3). Trouvez une formule explicite (non récursive) pour cette fonction.





Question 7
Trouver une fonction récursive f(n) permettant de calculer le nombre de mots de longueur n que l'on peut écrire avec les lettres a, b, c et qui ne contiennent pas le pattern >. Expliquez.





Question 8
Dans le problème des lapins de Fibonacci, nous supposons que :

i) Il y avait au départ 9 couples de lapins.
ii) Un couple de lapins donne naissance à une première portée de 2 couples à la fin du 4eme mois et par la suite il donne naissance à une portée de 8 couples à tous les mois.

Soit f(n), le nombre de couples de lapins à la fin du n ieme mois. Trouver une formule récursive pour f(n).

Alors .. le prof avait donnée une formule du genre : f(n) = anciens + nouveaux nés issus de la premiere portée + nouveaux nés issus d'une portée ultérieure.
f(0)=9
f(1)=9
f(2)=9
f(3)=9
f(4)= 9+2
f(5)=9+2+8
f(6)=9+2+8+8
f(7)=9+2+8+8+8
...
...

Est ce que ça a du sens ?



Question 9

Soit A={ n|n appartient à l'ensemble des N et n MOD 23=6 }
Définir A récursivement.

Je comprend que tout nombre n divisé par 23 reste 6 ... Mais là je ne vois pas ce que je peux faire =/



Question 10

Soit A, l'ensemble de toutes les chaines binaires ayant un nombre impair de zéros.
Définir A récursivement.

A={0 impair}
...
Besoin d'aide là aussi.


Merci beaucoup de votre aide, j'en ai vraiment besoin.

[fatal_error]

salut,

Alors pour ça j'ai pensé à gaire A(1,n+1)=A(1-1, A(n+1-1))
Et la je bloque à A(1,n+1)=A(0, A(n))
Ca fait A(0,n) ?

tu tes planté avec A(n+1-1), il te manque une composante ( A(x,y) et non A(x))
une facon simple : A(1,n) = A(0, A(1, n-1)) = A(1,n-1)...=A(1,0)

[Antoon]

Oops, je viens de voir mon erreur. Merci beaucoup.
Tu aurais le courage de m'expliquer le reste, ce que je ne comprend pas ? :$

[fatal_error]

pour la b, tu composes
tu sais que pour tout n tu connais A(1,n), tas tout intéret a tenter de ramener A(2,n) en un truc en A(1,qqch) et c'est gagné

la 6 tu devrais y arriver!
le reste jsais pas, on verra plus tard..