#Exercice 1

def premiereRecurrence(n):
    return 2 if n == 0 else 4 * premiereRecurrence(n - 1) - 1

def secondeRecurrence(n):
    return 4 if n == 1 else (n + secondeRecurrence(n - 1)) ** (1 / 2)

# Complexité du premier programme O(2^n)
# Complexité du nouveau programme : O(n)
def w(n):
    if n == 0:
        return 2
    else:
        w_ = w(n - 1)
        return 0.5 * (w_ + 3 / w_)

print(w(100), 3 ** (1/2))

# Exercice 2

def pgcd(n, m):
    #Cas de base
    if n == 0 or m == 0:
        return max(n, m)
    if n == m:
        return n
    #Appels récursifs
    if n > m:
        return pgcd(n - m, m)
    else:
        return pgcd(m - n, n)

print(pgcd(6, 12))

# EXERCICE 2

# EXERCICE 3

from sympy import *

def fibo(n):
    def aux(n):
        A = Matrix([[1, 1], [1, 0]])
        if n == 1:
            return A
        if n == 0:
            return eye(2)
        else:
            if n % 2 == 0:
                return aux(n / 2) * aux(n / 2)
            else:
                return aux((n - 1) / 2) * aux((n - 1) / 2) * A

    F0 = Matrix([[1], [0]])
    return (aux(n) * F0)[0]

print(fibo(100))

# EXERCICE 4

def binom(n, p):
    if n <= 0 or p <= 0 or p >= n:
        return 1
    return n / p * binom(n - 1, p - 1)

def binom2(n, p):
    if n <= 0 or p <= 0 or p >= n:
        return 1
    return binom(n - 1, p) + binom(n - 1, p - 1)

# Complexité en n : O(2^n)
# Si p est grand, le calcul risque d'être long.

n = 100
triangle = [[-1 for i in range(n + 1)] for j in range(n + 1)]

def binomPascal(n, p):
    if p == 0 or p == n:
        triangle[n][p] == 1
        return 1
    assert n >= p, "n doit être >= p " + str(n) + " " + str(p)
    if triangle[n][p] == -1:
        triangle[n][p] = binomPascal(n - 1, p - 1) + binomPascal(n - 1, p)
    return triangle[n][p]

def triangleGen(n):
    for p in range(n + 1):
        binomPascal(n, p)
#
# print(binomPascal(n, 50))
# triangleGen(n)
# print(triangle)

# EXERCICE 5
import sys
sys.setrecursionlimit = 9999
def phiDeb(i, j):
    return phiDeb(i - 1, j) + phiDeb(i, j - 1)
# print(phiDeb(15, 10))

valeurs_chemins = [[1 if i == 0 or j == 0 else 0 for i in range(20)] for j in range(20)]
def phi(i, j):
    if valeurs_chemins[i][j] == 0:
        valeurs_chemins[i][j] = phi(i - 1, j) + phi(i, j - 1)
    return valeurs_chemins[i][j]

print(phi(15, 10))

# EXERCICE 6

npsi = 1001
valeurspsi = [[-1 for i in range(npsi)] for j in range(npsi)]

def psi(n, m):
    if valeurspsi[n][m] == -1:
        if n == 0 and m == 0:
            valeurspsi[n][m] = 1
        elif m < 0:
            valeurspsi[n][m] = 0
        elif m == 0 and n > 0:
            valeurspsi[n][m] = 0
        elif n == 0 and m > 0:
            valeurspsi[n][m] = 1
        elif n > m:
            valeurspsi[n][m] = psi(n - m, m) + psi(n, m - 1)
        elif
        return valeurspsi[n][m]
    else:
        return valeurspsi[n][m]

print(psi(1000, 1000))