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,b1)) 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)=0ba
    • Egalité=(=0(Sous(a,b)))(=0(Sous(a,b)))
  • Even(n)={1 si n=01Even(n1) sinon
  • div2(n)={0 si n=0Even(n)×(1+div2(n2))+(1Even(n))×div2(n1)=Even(n)+div2(n1) sinon

EX2

MinEstAvant(l,n)={1 si ml;𝜉(m,n)=00 sinon={1𝜉(0,n) si l=0MinEstAvant(l1,n)+(1MinEstAvant(l1,n))(=0(𝜉(l,n))) sinon 𝜃(m,n)={1=0(𝜉(0,n)) si m=0MinEstAvant(m,n)𝜃(m1,n)+(1MinEstAvant(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×2n1 sinon K={22x(2y+1)1div2(2nz) où nminmz{(z+1)/2m est impair} L(2x(2y+1)1)=z+12K(z) div2(2nz)={div2(z) si n=02n1z sinon 𝜑(n,x)={J(g(n),0) si x=0J(h(K(𝜑(n1,n),L(𝜑(n1,n)+1))),L(𝜑(n1,n)+1)) sinon

Leave a comment