Objectifs
Exercices sur les tableaux
true si le tableau possède un élément répété au moins deux fois, et false sinon.On veut automatiser la conversion d’une base vers une autre, pour cela on va faire l’exemple de la traduction d’un nombre en base 10 $M = d_k d_{k-1} \ldots d_2 d_1 d_0$ vers son équivalent en base 2 $a_l d_{l-1} \ldots a_2 a_1 a_0$:
Le polynôme $P=4-3X+X^2+5X^3$ peut être stocké dans un tableau de la forme $[4,-3,1,5]$. D’une manière générale, on stocke le polynôme $p_0+p_1X+…+p_nX^n$ dans un tableau de longueur $n+1$: $[p_0,p_1,…,p_n]$.
On considère deux tableaux $A$ et $B$ de $N$ entiers. On dit que $A$ est contenu dans $B$ lorsque tous les éléments de $A$ figurent au moins une fois dans $B$.
On cherche le deuxième élément le plus grand d’un tableau $t$ de taille $N$ fixée. On suppose que tous les éléments de $t$ sont distincts.
Écrire un algorithme qui calcule le produit scalaire de deux vecteurs de même taille passés en paramètre. Rappel~: \(u \cdot v= \displaystyle \sum_{i}v_i * u_i\)
La taille commune des deux vecteurs pourra être passée en paramètre.
Écrire un algorithme qui calcule et stocke dans un tableau (vecteur) de taille N les entiers $0!$, $1!$ \ldots $N-1!$, en faisant un minimum de multiplications. Quelle est la complexité de votre algorithme?
On rappelle que $i!=1\times 2\times 3 \times \ldots i$.
Implémenter la méthode du crible dont le principe est le suivant. (\emph{Source: wikipedia}) L’algorithme procède par élimination: il s’agit de supprimer d’une table des entiers de $2$ à $N$ tous les multiples d’un entier. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d’aucun entier, et qui sont donc les nombres premiers. On commence par rayer les multiples de $2$, puis à chaque fois on raye les multiples du plus petit entier restant. On peut s’arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment. À la fin du processus, tous les entiers qui n’ont pas été rayés sont les nombres premiers inférieurs à $N$.
Les mots seront supposés codés sour forme d’un d’un tableau de caractères de taille $N$ (fixé, grand) dont le dernier est égal à \0 (caractère spécial de fin de chaîne).
Écrire les programmes suivants:
'a' n'apparait jamais
'b' apparait pour la première fois en position 0
'c' apparait pour la première fois en position 35
...
On n’utilisera pas de tableau, et pour chaque lettre on utilisera une boucle while.
occurrences qui va nous servir à compter le nombre d’apparitions de chaque lettre. De quelle taille est-il ?occurrences avec le nombre d’apparition de chaque lettre dans le tableau tab, et afficher le résultat ensuite sous la forme:'a' apparait 0 fois
'b' apparait 1 fois
'c' apparait 4 fois
...
tab dans l’ordre alphabétique. On utilisera le tableau occurrences, et si le caractère 'a' n’apparaît pas, on n’affichera pas 'a'.occurrences pour modifier le tableau tab afin qu’il soit trié par ordre alphabétique, puis afficher le tableau tab afin de vérifier qu’il est trié. Indication~: avec le tableau occurrences, on connaît le nombre d’occurrences de chaque caractères. On peut donc écraser le contenu du tableau tab sans perdre la moindre donnée.(())() les parenthèses sont bien imbriquées, mais pas dans ((((()(.affiche_2d qui prend en paramètre un tableau à CMAX colonnes et LMAX lignes et qui affiche ce tableau en lignes et colonnes.Écrire un algorithme somme_tab2dim qui prend en paramètre un tableau tab à deux dimensions et qui:
ligne;Soient $n$ un entier et $M[n][n]$ une matrice de booléens représentant une relation $R$ sur les entiers de la façon suivante~: $M[i][j] = true$ si et seulement si $iRj$. Écrire des algorithmes permettant de déterminer si $R$ est réflexive, symétrique, transitive.