log1-annexe-parcours-tab.tex

\chapter{Les parcours de tableaux} 

Les tableaux interviennent dans de nombreux problèmes 
et il est primordial de savoir les parcourir 
en utilisant des algorithmes
corrects, efficaces et lisibles.

Examinons les situations courantes et voyons quelles solutions conviennent.
Commençons par le cas, plus facile, des tableaux à une dimension
avant de passer à ceux à deux dimensions.
On pourrait aussi envisager d'autres parcours
(à l'envers, une case sur deux, \dots) 
mais ils ne représentent aucune difficulté nouvelle.

% ==============================================
\section{Parcours d'un tableau à une dimension} \label{Les parcours de tableaux}
% ==============================================

Soit le tableau statique \textit{tab} déclaré ainsi

\cadre{
\begin{pseudo}
	\Decl tab~: \K{tableau} [1 à n] de T \RComment où \textit{T} est un type quelconque
\end{pseudo}
}

Ou oit le tableau dynamique \textit{tab} déclaré ainsi

\cadre{
\begin{pseudo}
	\Decl tab~: \K{tableau} de T \RComment où \textit{T} est un type quelconque
	\Let tab \Gets \K{nouveau} \K{tableau} [1 à n] de T
\end{pseudo}
}


Envisageons d'abord le parcours complet
et voyons ensuite les parcours avec arrêt prématuré.

\subsection{Parcours complet}

Pour le parcourir, on peut utiliser la boucle \K{pour}
comme dans l'algorithme \vref{algo:parcours1-complet-pour}
où "traiter" va dépendre du problème concret posé~:
afficher, modifier, sommer, \dots

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours complet d'un tableau via une boucle pour}
	\label{algo:parcours1-complet-pour}
	\LComment Les déclarations sont omises pour ne pas alourdir les algorithmes.
	\For{i de 1 à n}
		\Stmt traiter tab[i]
	\EndFor
\end{pseudo}
\end{algorithm}

\subsection{Parcours avec sortie prématurée}

Parfois, on ne doit pas forcement parcourir le tableau jusqu'au bout
mais on pourra s'arrêter prématurément si une certaine condition est remplie.
Par exemple~:
\begin{liste}
\item on cherche la présence d'un élément et on vient de le trouver ;
\item on vérifie qu'il n'y a pas de $0$ et on vient d'en trouver un.
\end{liste}

La première étape est de transformer le \K{pour} en \K{tant que}
ce qui donne l'algorithme \vref{algo:parcours1-complet-tq}.

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours complet d'un tableau via une boucle tant-que}
	\label{algo:parcours1-complet-tq}
	\Let i \Gets 1
	\While{i $\le$ n}
		\Stmt traiter tab[i]
		\Let i \Gets i + 1
	\EndWhile
\end{pseudo}
\end{algorithm}

On peut à présent introduire le test d'arrêt.
Une contrainte est qu'on voudra, à la fin de la boucle, savoir
si oui ou non on s'est arrêté prématurément et, si c'est le cas,
à quel indice.

Il existe essentiellement deux solutions, avec ou sans variable booléenne.
En général, la solution [A] sera plus claire si le test est court.

\subsubsection*{[A] Sans variable booléenne}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours partiel d'un tableau sans variable booléenne}
	\label{algo:parcours1-partiel-sans-bool}
	\Let i \Gets 1
	\While{i $\le$ n ET \textit{test sur tab[i] dit que on continue}}
		\Let i \Gets i + 1
	\EndWhile
	\If{i $>$ n}
		\LComment On est arrivé au bout
	\Else
		\LComment Arrêt prématuré à l'indice i.
	\EndIf
\end{pseudo}
\end{algorithm}

On pourrait inverser les deux branches du \K{si-sinon} en inversant le test
mais attention à ne pas tester tab[i] car $i$ n'est peut-être pas valide.

\subsubsection*{[B] Avec variable booléenne}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours partiel d'un tableau avec variable booléenne}
	\label{algo:parcours1-partiel-avec-bool}
	\Let i \Gets 1
	\Let trouvé \Gets faux
	\While{i $\le$ n ET NON trouvé}
		\If{\textit{test sur tab[i] dit que on a trouvé}}
			\Let trouvé \Gets vrai
		\Else
			\Let i \Gets i + 1
		\EndIf
	\EndWhile
	\LComment Tester le booléen pour savoir si arrêt prématuré.
\end{pseudo}
\end{algorithm}

Attention à bien choisir un nom de booléen adapté au problème
et à l'initialiser à la bonne valeur. 
Par exemple, si la variable s'appelle "continue"
\begin{liste}
\item initialiser la variable à vrai ;
\item le test de la boucle est "\dots ET continue" ;
\item mettre la variable à faux pour sortir de la boucle.
\end{liste}

% ================================================
\section{Parcours d'un tableau à deux dimensions}
\label{algo:Tab2D}
% ================================================

Considérons à présent un tableau à deux dimensions 
(m lignes et n colonnes)

Déclaration d'un tableau statique~:

\cadre{
\begin{pseudo}
	\Decl tab~: tableau [1 à m, 1 à n] de T
\end{pseudo}
}

Déclaration d'un tableau dynamique~:

\cadre{
	\begin{pseudo}
	\Decl tab~: \K{tableau} de T
	\Let tab \Gets \K{nouveau} \K{tableau} [1 à m, 1 à n] de T
	\end{pseudo}
	}


Commençons par des cas plus simples 
où on ne parcourt qu'une seule des dimensions 
puis attaquons le cas général.

\subsection{Parcours d'une dimension}

On peut vouloir ne parcourir qu'une seule ligne du tableau.
Si on parcourt la ligne $l$, on visite les cases 
$(l,1)$, $(l,2)$, \dots, $(l,n)$.
L'indice de ligne est constant et c'est l'indice de colonne qui varie.
Ce qui donne l'algorithme \vref{algo:parcours2-ligne}.

\begin{tabular}{|*{5}{>{\centering\arraybackslash}m{0.3cm}|}}
\hline
\ & \ & \ & \ & \  \\
\hline
\cellcolor{gray!25}\ & \cellcolor{gray!25}\ & \cellcolor{gray!25}\ & \cellcolor{gray!25}\ & \cellcolor{gray!25}\  \\
\hline
\ & \ & \ & \ & \  \\
\hline
\end{tabular}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours de la ligne $l$ d'un tableau à deux dimensions}
	\label{algo:parcours2-ligne}
	\For{c de 1 à n}
		\Stmt traiter tab[l,c]
	\EndFor
\end{pseudo}
\end{algorithm}

Retenons~: Pour parcourir une ligne, on utilise une boucle sur les colonnes. 

Symétriquement, on pourrait considérer le parcours de la colonne $c$
comme avec l'algorithme \vref{algo:parcours2-col}.

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours de la colonne $c$ d'un tableau à deux dimensions}
	\label{algo:parcours2-col}
	\For{l de 1 à n}
		\Stmt traiter tab[l,c]
	\EndFor
\end{pseudo}
\end{algorithm}

Si le tableau est carré ($m=n$) on peut aussi envisager le parcours
des deux diagonales.

Pour la colonne descendante, 
les éléments à visiter sont $(1,1)$, $(2,2)$, \dots, $(n,n)$.
Une seule boucle suffit 
comme le montre l'algorithme \vref{algo:parcours2-diag1}.

\begin{tabular}{|*{3}{>{\centering\arraybackslash}m{0.3cm}|}}
\hline
\cellcolor{gray!25}\ & \ & \ \\
\hline
\ & \cellcolor{gray!25}\ & \ \\
\hline
\ & \ & \cellcolor{gray!25}\ \\
\hline
\end{tabular}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours de la diagonale descendante d'un tableau carré}
	\label{algo:parcours2-diag1}
	\For{i de 1 à n}
		\Stmt traiter tab[i,i]
	\EndFor
\end{pseudo}
\end{algorithm}

Pour la colonne montante, 
on peut envisager deux solutions, 
avec deux indices (cf. algorithme \vref{algo:parcours2-diag2a})
ou un seul (cf. algorithme \vref{algo:parcours2-diag2b})
qui se base sur le fait que $i+j=n+1 \Rightarrow j=n+1-i$.

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours de la diagonale montante d'un tableau carré - 2 indices}
	\label{algo:parcours2-diag2a}
	\Let j \Gets n
	\For{i de 1 à n}
		\Stmt traiter tab[i,j]
		\Let j \Gets j - 1
	\EndFor
\end{pseudo}
\end{algorithm}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours de la diagonale montante d'un tableau carré - 1 indice}
	\label{algo:parcours2-diag2b}
	\For{i de 1 à n}
		\Stmt traiter tab[i,n+1-i]
	\EndFor
\end{pseudo}
\end{algorithm}

\subsection{Parcours des deux dimensions}

\subsubsection*{Parcours par lignes et par colonnes}

Les deux parcours les plus courants sont les parcours ligne par ligne
et colonne par colonne.
Les tableaux suivants montrent dans quel ordre chaque case est visitée dans ces deux parcours.

\begin{center}
\begin{minipage}{0.4\textwidth}
\begin{center}
Parcours ligne par ligne\\
\begin{tabular}{|*{5}{>{\centering\arraybackslash}m{0.35cm}|}}
\hline
1 & 2 & 3 & 4 & 5 \\
\hline
6 & 7 & 8 & 9 & 10 \\
\hline
11 & 12 & 13 & 14 & 15 \\
\hline
\end{tabular}
\end{center}
\end{minipage}
\qquad
\begin{minipage}{0.4\textwidth}
\begin{center}
Parcours colonne par colonne\\
\begin{tabular}{|*{5}{>{\centering\arraybackslash}m{0.35cm}|}}
\hline
1 & 4 & 7 & 10 & 13 \\
\hline
2 & 5 & 8 & 11 & 14 \\
\hline
3 & 6 & 9 & 12 & 15 \\
\hline
\end{tabular}
\end{center}
\end{minipage}
\end{center}

Le plus simple est d'utiliser deux boucles imbriquées 
(cf. algorithmes \vref{algo:parcours2-lig2} et \vref{algo:parcours2-col2})

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours d'un tableau à 2 dimensions, ligne par ligne}
	\label{algo:parcours2-lig2}
	\For{l de 1 à m}
		\For{c de 1 à n}
			\Stmt traiter tab[l,c]
		\EndFor
	\EndFor
\end{pseudo}
\end{algorithm}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours d'un tableau à 2 dimensions, colonne par colonne}
	\label{algo:parcours2-col2}
	\For{c de 1 à m}
		\For{l de 1 à n}
			\Stmt traiter tab[l,c]
		\EndFor
	\EndFor
\end{pseudo}
\end{algorithm}

Mais on peut obtenir le même résultat avec une seule boucle
si l'indice sert juste à compter le nombre de passages
et que les indices de lignes et de colonnes sont gérés manuellement.

L'algorithme \vref{algo:parcours2-1bcl} montre ce que ça donne
pour un parcours ligne par ligne.
La solution pour un parcours colonne par colonne est similaire
et laissée en exercice.

L'avantage de cette solution apparaitra 
quand on verra des situations plus difficiles.

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours d'un tableau à 2 dimensions via une seule boucle}
	\label{algo:parcours2-1bcl}
	\Let lg \Gets 1
	\Let col \Gets 1
	\For{i de 1 à m*n}
		\Stmt traiter tab[lg,col]
		\Let col \Gets col + 1	\RComment Passer à la case suivante
		\If{col$>$n} \RComment On déborde sur la droite, passer à la ligne suivante
			\Let col \Gets 1
			\Let lg \Gets lg + 1
		\EndIf
	\EndFor
\end{pseudo}
\end{algorithm}

\subsubsection*{Interrompre le parcours}

Comme avec les tableaux à une dimension, 
envisageont l'arrêt prématuré lors de la rencontre d'une certaine condition.
Et, comme avec les tableaux à une dimension, 
transformons d'abord nos \K{pour} en \K{tant que}.

Par exemple, les deux parcours ligne par ligne, avec une et deux boucle(s)
sont explicités dans les algorithmes \vref{algo:parcours2-lig2-tq}
et \vref{algo:parcours2-1bcl-tq}.

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours d'un tableau à 2 dim, ligne par ligne, via un tant que}
	\label{algo:parcours2-lig2-tq}
	\Let l \Gets 1
	\While{l $<$ m}
		\Let c \Gets 1
		\While{c $<$ n}
			\Stmt traiter tab[l,c]
			\Let c \Gets c + 1
		\EndWhile
		\Let l \Gets l + 1
	\EndWhile
\end{pseudo}
\end{algorithm}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours d'un tableau à 2 dim via une seule boucle et un tant que}
	\label{algo:parcours2-1bcl-tq}
	\Let lg \Gets 1
	\Let col \Gets 1
	\Let i \Gets 1
	\While{i $\le$ m*n} \RComment ou "lg $\le$ m" 
		\Stmt traiter tab[lg,col]
		\Let col \Gets col + 1	\RComment Passer à la case suivante
		\If{c$>$n} \RComment On déborde sur la droite, passer à la ligne suivante
			\Let col \Gets 1
			\Let lg \Gets lg + 1
		\EndIf
		\Let i \Gets i + 1		
	\EndWhile
\end{pseudo}
\end{algorithm}

On peut à présent introduire le test comme on l'a fait 
dans les algorithmes \vref{algo:parcours1-partiel-sans-bool}
et \vref{algo:parcours1-partiel-avec-bool}.

Illustrons-le au travers de deux exemples.
L'algorithme \vref{algo:parcours2-lig2-arret} introduit un test 
à l'algorithme \vref{algo:parcours2-lig2-tq} en utilisant un booléen
alors que l'algorithme \vref{algo:parcours2-1bcl-arret} introduit un test
à l'algorithme \vref{algo:parcours2-1bcl-tq} sans utiliser de booléen.

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours avec test d'arrêt - deux boucles et un booléen}
	\label{algo:parcours2-lig2-arret}
	\Let trouvé \Gets faux
	\Let l \Gets 1
	\While{l $<$ m ET NON trouvé}
		\Let c \Gets 1
		\While{c $<$ n ET NON trouvé}
			\If{\textit{tab[l,c] impose l'arrêt du parcours}}
				\Let trouvé \Gets vrai
			\Else \RComment Ne pas modifier les indices si arrêt demandé
				\Let c \Gets c + 1
			\EndIf
		\EndWhile
		\If{NON trouvé} \RComment Ne pas modifier les indices si arrêt demandé
			\Let l \Gets l + 1
		\EndIf
	\EndWhile
\end{pseudo}
\end{algorithm}

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours avec test d'arrêt - une boucle et pas de booléen}
	\label{algo:parcours2-1bcl-arret}
	\Let lg \Gets 1
	\Let col \Gets 1
	\Let i \Gets 1
	\While{i $\le$ m*n ET tab[lg,col] n'impose pas l'arrêt}  
		\Let col \Gets col + 1	\RComment Passer à la case suivante
		\If{c$>$n} \RComment On déborde sur la droite, passer à la ligne suivante
			\Let col \Gets 1
			\Let lg \Gets lg + 1
		\EndIf
		\Let i \Gets i + 1		
	\EndWhile
	\LComment Arrêt prématuré si i $\le$ m*n.
\end{pseudo}
\end{algorithm}

\subsubsection*{Parcours plus compliqué - le serpent}

Envisageons un parcours plus difficile illustré par le tableau suivant.

\begin{center}
\begin{tabular}{|*{5}{>{\centering\arraybackslash}m{0.35cm}|}}
\hline
1 & 2 & 3 & 4 & 5 \\
\hline
10 & 9 & 8 & 7 & 6 \\
\hline
11 & 12 & 13 & 14 & 15 \\
\hline
\end{tabular}
\end{center}

Le plus simple est d'adapter l'algoithme \vref{algo:parcours2-1bcl}
en introduisant un sens de déplacement, 
ce qui donne l'algorithme \vref{algo:parcours2-serpent}.

\begin{algorithm}[H]
\begin{pseudo}
	\caption{Parcours du serpent dans un tableau à deux dimensions}
	\label{algo:parcours2-serpent}
	\Let lg \Gets 1
	\Let col \Gets 1
	\Let depl \Gets 1	\RComment 1 pour avancer, -1 pour reculer
	\For{i de 1 à m*n}
		\Stmt traiter tab[lg,col]
		\If{1 $\le$ col + depl ET col + depl $\le$ n}
			\Let col \Gets col + depl \RComment On se déplace dans la ligne
		\Else
			\Let lg \Gets lg + 1	\RComment On passe à la ligne suivante
			\Let depl \Gets -depl	\RComment et on change de sens
		\EndIf
	\EndFor
\end{pseudo}
\end{algorithm}