log1-annexe-suites.tex

% =================================
\chapter{Les suites}
% =================================

Ce chapitre propose en exercice des suites.
Un exemple simple pourrait être celui-ci.

\begin{Exercice}{Suite des nombres pairs}
	Écrire l'algorithme qui affiche les $N$ premiers termes
	de la suite: $2$, $4$, $6$, \dots.
\end{Exercice}

Toutes ces suites peuvent se résoudre 
en suivant un même squelette d'algorithme que nous allons expliquer ici.

Puisqu'on doit écrire plusieurs nombres et qu'on sait exactement combien,
on se tournera tout naturellement vers un \K{pour}.

\section*{En fonction de i}

Le cas le plus simple est lorsque le nombre à afficher à l'étape $i$
peut être calculé à partir de $i$ seulement.
L'algorithme est alors

\cadre{
\begin{pseudo}
\LComment schéma 1 de résolution d'une suite.
\For{i de 1 à N}
	\Write $f(i)$
\EndFor
\end{pseudo}
}

Pour l'exercice 1, la fonction est $f(i)=2*i$\footnote{Si vous
n'êtes pas convaincu, vérifiez qu'à l'étape $1$ on affiche $2$,
à l'étape $2$ on affiche $4$, \dots} ce qui donne

\cadre{
\begin{pseudo}
\Module{suite1}{N\In: entier}{} \RComment en utilisant le schéma 1
	\Decl i : entier
	\For{i de 1 à N}
		\Write 2 * i
	\EndFor
\EndModule
\end{pseudo}
}

\section*{En fonction du nombre précédent}

Parfois, il est difficile (voire impossible) de trouver $f(i)$.
On suivra alors une autre approche qui revient à calculer un nombre
à afficher à partir du nombre précédemment affiché
(ou, plus exactement, de calculer le suivant à partir du nombre
qu'on vient d'afficher).
La structure générale est alors

\cadre{
\begin{pseudo}
\LComment schéma 2 de résolution d'une suite.
\Let nb \Gets \textit{\{1\up{ère} valeur à afficher\}}
\For{i de 1 à N}
	\Write nb
	\Let nb \Gets \textit{\{calculer ici le nb suivant\}}
\EndFor
\end{pseudo}
}

Par exemple, pour l'exercice 1 : le 1\up{er} nombre à afficher est $2$
et le nombre suivant se calcule en ajoutant $2$ au nombre courant.

\cadre{
\begin{pseudo}
\Module{suite1}{N\In: entier}{} \RComment en utilisant le schéma 2
	\Decl nb, i : entiers
	\Let nb \Gets 2
	\For{i de 1 à N}
		\Write nb
		\Let nb \Gets nb + 2
	\EndFor
\EndModule
\end{pseudo}
}

On remarque que, lors du dernier passage dans la boucle,
on calcule une valeur qui ne sera pas affichée.
Cette petite perte de temps est dommage mais négligeable
et permet de garder une structure claire et générale à la solution.

\section*{Avec une mémoire}

Dans certains cas,
il n'est pas possible de déduire directement le nombre suivant
en connaissant juste le nombre précédent.

Prenons un exemple un peu plus compliqué pour l'illustrer.

\begin{Exercice}{3 pas en avant, 2 pas en arrière} 
	Écrire l'algorithme qui affiche les $N$ premiers termes
	de la suite: $1$, $2$, $3$, $4$, $3$, $2$, $3$, $4$, $5$, $4$, $3$, \dots.
\end{Exercice}

Si on vient d'écrire, disons un $3$,
impossible sans information supplémentaire,
de connaitre le nombre suivant.
Il faudrait savoir si on est en phase d'avancement ou de recul
et combien de pas il reste à faire dans cette direction.

Ajoutons des variables pour retenir l'\emph{état} où on est.

\cadre{
\begin{pseudo}
\Module{suite2}{N\In: entier}{} 
	\Decl nb, nbPasRestants, direction, i : entiers
	\Let nb \Gets 1
	\Let nbPasRestants \Gets 3 \RComment 3 pas
	\Let direction \Gets 1 \RComment en avant
	\For{i de 1 à N}
		\Write nb
		\Let nb \Gets nb + direction \RComment faire un pas dans la bonne direction
		\Let nbPasRestants \Gets nbPasRestants - 1
		\If{nbPasRestants $=$ 0} \RComment Il est temps de changer de direction
			\Let direction \Gets -direction
			\If{direction $=$ 1}
				\Let nbPasRestants \Gets 3 
			\Else 
				\Let nbPasRestants \Gets 2
			\EndIf
		\EndIf
	\EndFor
\EndModule
\end{pseudo}
}

On obtient un algorithme plus long 
mais qui respecte toujours le schéma vu.

Un conseil : essayez de respecter ce schéma 
et vous obtiendrez plus facilement un algorithme
correct et lisible, également dans les cas particuliers.

\begin{Exercice}{Fibonnaci} 
	Résoudre la suite de Fibinacci en respectant le cadre vu dans cette annexe.
\end{Exercice}