# TD 1 -- Algorithme

###### tags `TD` `M1 S1` `Algorithme`
[Sommaire](/ueYXUIJIQ6C6hcYzKYeojA)
> [time= 16 sept 2020]

[TOC]

## ++Exercice 1++: le problème des fous sur un échiquier n × n
### Enoncer
On veut placer un nombre maximal de fous sur un échiquier de taille n × n sans que les fous se menacent mutuellement. On rappelle qu’un fou menance toutes les cases qui se trouvent sur les deux diagonales passant par sa case.
1. Sur un échiquier de taille 2 × 2 (3 × 3, 4 × 4) combien de fous peut-on placer sans qu’ils se menacent ?
2. Donnez un algorithme pour résoudre le problème.
3. Modifiez cet algorithme pour obtenir également le placement des fous.
4. Évaluer la complexité de l’algorithme.

### Réponse

#### 1)
n = 2 -> 2 fous

F,.
F,.

n = 3 -> 4 fous

F,.,.
F,.,F
F,.,.

n = 4 -> 6 fous

F,.,.,.
F,.,.,F
F,.,.,F
F,.,.,.

#### 2)

def est_menace(l, i, j):
    """
        test si le placement d'un fous en i, j
        menace le jeux
        
        l: list
            liste contenant la liste 
            des positions des trous déja places
        i: int
            ligne de l'élément à tester
        j: int
            colonne de l'élément à tester
    """
    if not l:
        return False
    i1, j1 = l[0]
    if abs(i - i1) == abs(j - j1):
        return True
    return est_menace(l[1:], i, j)

def fous_nombre(n):
    """
    resous le probleme des fous 
    sur une grille de n
    
    n: int
        taille de la grille
    """
    def fous(l):
        """
        resoud le probleme des fous 
        en donnant le nomre de fous possible
        """
        r_max = len(l)
        for i in range(n):
            for j in range(n):
                if not est_menace(l, i, j):
                    res = fous(l + [(i, j)])
                    if res > r_max:
                        r_max = res
        return r_max
    return fous([])

#### 3)

def fous_placement(n):
    """
    resous le probleme des fous 
    sur une grille de n
    
    n: int
        taille de la grille
    """
    def fous(l):
        """
        resoud le probleme des fous 
        en donnant le nomre de fous possible
        """
        r_max = len(l)
        l_max = l
        for i in range(n):
            for j in range(n):
                if not est_menace(l, i, j):
                    res, res_l = fous(l + [(i, j)])
                    if res > r_max:
                        r_max = res
                        l_max = res_l
        return r_max, l_max
    return fous([])

#### 4)
La compléxité est en (n^2^)^n^

## ++Exercice 2++: plus longue sous-suite croissante
### Enoncé

Plus longue sous-suite croissante
On s’intéresse au problème suivant : étant donné une liste L d’entiers, déterminer une suite strictement croissante d’indices $i_1 < \dotsc < i_l$, de longueur $l$ maximale, telle que $L[i_1] \leq􏰀 L[i_2] \leq􏰀 \dotsc \leq L[i_l]$.
1. Proposer un algorithme de type « backtracking » permettant de calculer la longueur maximale d’une sous-suite croissante.
2. Donner une relation de récurrence structurelle qui correspond à cet algorithme.
3. Modifier cet algorithme pour obtenir l’une des plus longues sous-suites croissantes, puis
pour compter ces plus longues sous-suites croissantes.
4. Évaluer la complexité de ces algorithmes.

### Réponse

exemple
| | | - | - | - | | - | - | - | | | |
| - | - | - | - | - | - | - | - | - | - | - | - |
| $-\infty$ | 2 | 1 | 3 | 4 | 2 | 5 | 6 | 7 | 3 | 4 | 5 |

#### 1)

def plssc(pre, l):
    """
    plus longue sous suite croissante
    pre : int
        on donne -infi par défaut
        est le rédécesseur
    l : list
        list des n élément à inspecté
    """
    if not l:
        return 0
    elif pre <= l[0]:
        skip = plssc(pre, l[1:])
        take = plssc(l[0], l[1:])
        return max(skip, take + 1)
    return plssc(pre, l[1:])

ou

def plssc_longeur(l):
    l = [min(l) - 1] + l
    def plssc(i, j):
        """
        plus longue sous suite croissante
        pre : int
            on donne -infi par défaut
            est le rédécesseur
        l : list
            list des n élément à inspecté
        """
        if j >= len(l):
            return 0
        elif l[i] <= l[j]:
            skip = plssc(l[i], j + 1)
            take = plssc(l[j], j + 1)
            return max(skip, take + 1)
        return plssc(i, j + 1)
    return plssc(0, 1)

#### 2)
$$
plssc(pre, A)=
\begin{cases}
0 & \text{si }n\text{ |L| = 0} \\
\begin{align}
\max(& plssc(pre, A[1:]),\\
& plssc(A[0], A[1:]) + 1)
\end{align}
& \text{si } \: pre \leq A[0]\\
plssc(pre, A[1:])
\end{cases}
$$

#### 4)
- si la liste est croissante (*l14 à l17*) on a une compléxité en **2^n^**
- si elle est décroissante (*l19*) on a une compléxité en **n**