TD6 : Fonctions récursives EX 1 Fonction prédécesseur : Pred Pred=Prim(Z,𝜋22) Soustraction Sous de a par b : −Sous(a,b)={a si b=0Pred(Sous(a,b−1)) sinon Sous=Comp(Prim(𝜋22,Comp4(Pred,𝜋41)),𝜋22,𝜋21) Égalité : =0 = true pour 0, false sinon =0=Prim(Comp1(S,Z),Comp1(Z,𝜋31)) Or, comme il n’y a pas de nombres négatifs (Pred(0)=0): Sous(a,b)=0⟺b≥a éEgalité=(=0(Sous(a,b)))∧(=0(Sous(a,b))) Even(n)={1 si n=01−Even(n−1) sinon div2(n)={0 si n=0Even(n)×(1+div2(n−2))+(1−Even(n))×div2(n−1)=Even(n)+div2(n−1) sinon EX2 MinEstAvant(l,n→)={1 si ∃m≤l;𝜉(m,n→)=00 sinon={1−𝜉(0,n→) si l=0MinEstAvant(l−1,n→)+(1−MinEstAvant(l−1,n→))(=0(𝜉(l,n→))) sinon 𝜃(m,n→)={1−=0(𝜉(0,n→)) si m=0MinEstAvant(m,n→)𝜃(m−1,n→)+(1−MinEstAvant(m,n→))×m×(=0(𝜉(m,n→)) sinon 𝜙(n→)=𝜃(𝜓(n→),n→) EX3 J={ℕ2⟶ℕ(x,y)↦2x(2y+1)−1 bijection 2n={1 si n=02×2n−1 sinon ù≝K={ℕ⟶ℕ22x(2y+1)−1↦div2(2nz) où n≝minm≤z{(z+1)/2m est impair} L(2x(2y+1)−1)=z+12K(z) div2(2nz)={div2(z) si n=02n−1z sinon 𝜑(n,x)={J(g(n),0) si x=0J(h(K(𝜑(n−1,n),L(𝜑(n−1,n)+1))),L(𝜑(n−1,n)+1)) sinon Share on Twitter Facebook Google+ LinkedIn Previous Next Leave a comment
Leave a comment