\documentclass{article}
\usepackage{amssymb, amsmath, geometry, multicol, stmaryrd}
\usepackage{listings, xcolor}
\usepackage[utf8]{inputenc}

\definecolor{red}{rgb}{0.8, 0.0, 0.0}
\definecolor{green}{rgb}{0.0, 0.8, 0.0}
\definecolor{blue}{rgb}{0.0, 0.0, 0.8}
\definecolor{orange}{rgb}{0.8, 0.5, 0.0}
\definecolor{lightgreen}{rgb}{0.6, 0.9, 0.6}

\lstloadlanguages{C}
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{white},
    commentstyle=\color{orange},
    keywordstyle=\color{blue},
    numberstyle=\tiny\color{blue},
    stringstyle=\color{lightgreen},
    basicstyle=\footnotesize\ttfamily,             
    captionpos=t,
    numbers=none,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=4
}
\lstset{style=mystyle,
        frameround=fttt,
        frame=trBL, 
        linewidth=15cm,
        aboveskip=5pt,
        belowskip=15pt,
        language=c,
        escapeinside={\%*}{*)}
}

\geometry{tmargin=.7in, bmargin=.75in, lmargin=.75in, rmargin = .75in}

\begin{document}
\setlength{\parindent}{0mm}

\title{OCaml - Listes}
\author{Aubin SIONVILLE}
\date{MPI Clemenceau - 2021-2023}
\maketitle

\section*{Types utilisés}

\begin{lstlisting}
    // Type pour les tableaux d'entiers munis de leur taille
    typedef struct {
        int* tab;
        int taille;
    } tableau;

    // Type pour les tableaux de tableaux d'entiers munis de leur taille
    typedef struct {
        tableau* tab;
        int taille;
    } tabtab;
    
    // Type pour les tableaux de booleens munis de leur taille
    typedef struct {
        bool* tab;
        int taille;
    } b_tableau;
\end{lstlisting}

\newpage

\section{Création de tableaux}

\subsection*{Par boucle while}

    Fonction prenant en argument un entier naturel non nul $n$ et retournant un tableau de $n$ booléens rempli de 0 à l'aide d'une boucle \textbf{while}.

    \begin{lstlisting}
        b_tableau creer_tableau_while(int n) {
            bool* tab = malloc(n * sizeof(bool));
            int i = 0;
            while (i < n) {
                tab[i] = false;
                i++;
            }
            b_tableau t = {tab, n};
            return t;
        }
    \end{lstlisting}

\subsection*{Par boucle for}

    Fonction prenant en argument un entier naturel non nul $n$ et retournant un tableau contenant les entiers de $1$ à $n$ à l'aide d'une boucle \textbf{for}.

    \begin{lstlisting}
        tableau creer_tableau_for(int n) {
            int* tab = malloc(n * sizeof(int));
            for (int i = 0; i < n; i++) {
                tab[i] = 0;
            }
            tableau t = {tab, n};
            return t;
        }
    \end{lstlisting}

\subsection*{Création et affichage}
    Programme qui crée le tableau contenant les entiers $1, 2, 4, 8, 12, 56, -3$ et $19$, puis qui affiche un à un ces éléments.

    \begin{lstlisting}
        void afficher_tableau(tableau t) {
            if (t.taille == 0) {
                printf("Tableau vide \n")
            }
            else {
                printf("Tableau de taille %d : \n", t.taille);
                for (int i = 0; i < t.taille; i++) {
                    printf("%d ", t.tab[i]);
                }
                printf("\n");
            }
        }

        int main() {
            int tab[8] = {1, 2, 4, 8, 12, 56, -3, 19};
            tableau t = {tab, 8};
            afficher_tableau(t);
            return 0;
        }
    \end{lstlisting}

\subsection*{Tableau d'entiers aléatoires}
    Fonction prenant en argument un entier naturel non nul $n$, et deux entiers relatifs $a$ et $b$ tels que $a < b$ et et retournant un tableau de $n$ entiers aléatoires tirés uniformément dans $\llbracket a, b \rrbracket$. \\
    On veillera à ce que le tableau construit par l'appel à cette fonction change potentiellement à chaque exécution.

    \begin{lstlisting}
        tableau creer_tableau_aleatoire(int n, int a, int b) {
            int* tab = malloc(n * sizeof(int));
            int l = b - a;
            for (int i = 0; i < n; i++) {
                tab[i] = rand() % l + a;
            }
            tableau t = {tab, n};
            return t;
        }

        int main() {
            srand(time(NULL));
            tableau t = creer_tableau_aleatoire(10, 0, 10);
            afficher_tableau(t);
            return 0;
        }
    \end{lstlisting}

\newpage

\section{Agrégation}

\subsection*{Existence d'un élément}
    Fonction testant l'existence d'un $0$ dans un tableau d'entiers parcouru par boucle \textbf{while}.

    \begin{lstlisting}
        bool existe_0(tableau t) {
            int i = 0;
            while (i < t.taille && t.tab[i] != 0) {
                i++;
            }
            return i < t.taille;
        }
    \end{lstlisting}

\subsection*{Indice de la première occurrence}
    Fonction calculant l'indice du premier $0$ dans un tableau d'entiers parcouru par boucle \textbf{while} arrêtée dès que possible, sans utiliser de \textbf{break}, ni de \textbf{return} dans la boucle. \\
    La fonction devra retourner $-1$ si le tableau ne contient aucun $0$.

    \begin{lstlisting}
        int indice_premier_0(tableau t) {
            int i = 0;
            while (i < t.taille && t.tab[i] != 0) {
                i++;
            }
            if (i == t.taille) {
                return -1;
            }
            else {
                return i;
            }
        }
    \end{lstlisting}

    Fonction calculant l'indice du premier $0$ dans un tableau d'entiers parcouru par boucle \textbf{while} arrêtée dès que possible, grâce à une instruction \textbf{return} dans la boucle. \\
    La fonction devra retourner $-1$ si le tableau ne contient aucun $0$.

    \begin{lstlisting}
        int indice_premier_0_bis(tableau t) {
            int i = 0;
            while (i < t.taille) {
                if (t.tab[i] == 0) {
                    return i;
                }
                i++;
            }
            return -1;
        }
    \end{lstlisting}

    Fonction calculant l'indice du premier $0$ dans un tableau d'entiers parcouru par boucle \textbf{for}. \\
    La fonction devra retourner $-1$ si le tableau ne contient aucun $0$.

    \begin{lstlisting}
        int indice_premier_0_for(tableau t) {
            for (int i = 0; i < t.taille; i++) {
                if (t.tab[i] == 0) {
                    return i;
                }
            }
            return -1;
        }
    \end{lstlisting}

\subsection*{Indice de la dernière occurrence}

    Fonction calculant l'indice du dernier $0$ dans un tableau d'entiers parcouru par boucle \textbf{while} arrêtée dès que possible, grâce à une instruction \textbf{return} dans la boucle. \\
    La fonction devra retourner $-1$ si le tableau ne contient aucun $0$.

    \begin{lstlisting}
        int indice_dernier_0(tableau t)
        {
            int i = t.taille - 1;
            while (i >= 0) {
                if (t.tab[i] == 0) {
                    return i;
                }
                i--;
            }
            return -1;
        }
    \end{lstlisting}

\subsection*{Somme des éléments}
    Fonction prenant en argument un tableau d'entiers et calculant la somme des éléments du tableau. \\
    On fournira une implémentation au moyen d'une boucle \textbf{for}.

    \begin{lstlisting}
        int somme(tableau t) {
            int somme = 0;
            for (int i = 0; i < t.taille; i++) {
                somme += t.tab[i];
            }
            return somme;
        }
    \end{lstlisting}

\subsection*{Recherche de minimum}
    Fonction calculant l'indice du minimum dans un tableau d'entiers non vide parcouru par une boucle \textbf{for}.

    \begin{lstlisting}
        int indice_minimum(tableau t) {
            if (t.taille == 0) {
                return -1;
            }
            int indice_min = 0;
            for (int i = 1; i < t.taille; i++) {
                if (t.tab[i] < t.tab[indice_min]) {
                    indice_min = i;
                }
            }
            return indice_min;
        }
    \end{lstlisting}

\subsection*{Conjonction d'un tableau de booléens}
    Fonction calculant la conjonction des éléments d'un tableau de booléens parcouru par une boucle \textbf{while}.

    \begin{lstlisting}
        bool conjonction(tableau t) {
            bool conj = true;
            int i = 0;
            while (i < t.taille && conj) {
                conj = conj && t.tab[i];
                i++;
            }
            return conj;
        }
    \end{lstlisting}

\subsection*{Maximum d'occurrences}
    Fonction prenant en argument un tableau d'entiers à valeurs dans $\llbracket 0, m-1 \rrbracket$ où $m$ est donné en argument, et calculant l'entier de $\llbracket 0, m-1 \rrbracket$ ayant le plus d'occurrences dans le tableau. \\
    On fournira une implémentation en $\mathcal{O}(n + m)$

    \begin{lstlisting}
        int maximum_occurrences(tableau t, int m) {
            int* nb_occurrences = malloc(m * sizeof(int));
            for (int i = 0; i < m; i++) {
                nb_occurrences[i] = 0;
            }

            for (int i = 0; i < t.taille; i++) {
                nb_occurrences[t.tab[i]]++;
            }

            int max = 0;
            for (int i = 1; i < m; i++) {
                if (nb_occurrences[i] > nb_occurrences[max]) {
                    max = i;
                }
            }

            free(nb_occurrences);
            return max;
        }
    \end{lstlisting}
\end{document}