\documentclass[12pt,a4paper]{article}
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{kpfonts}
\usepackage{pas-algo}
\usetikzlibrary{matrix,arrows,calc}
\usepackage[margin=2cm]{geometry}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage{cellspace}
\usepackage{eso-pic}
\usepackage{enumitem}
\usepackage[urlcolor=purple,colorlinks=true]{hyperref}
\usepackage{listings}
\definecolor{violet}{cmyk}{0.28,0.89,0,0.28}
\definecolor{vert}{cmyk}{0.17,0,0.17,0.07}
\newcommand{\chapHead}[1]{% #1 = Titre
\begin{tikzpicture}
\fill[blue!20] (0,0) rectangle+(\textwidth,-1.5cm);
\fill[orange!5] (0,-1) rectangle +(\textwidth,-5cm);
\fill[violet] (12cm,0) rectangle +(4cm,-4.5cm);
\fill[violet!80] (12cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!70] (12.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (13cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (12cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!50] (12.5cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (12cm,-3.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (13.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[vert] (12cm,-4.5cm) rectangle +(4cm,-1.5cm);
% "Article"
\node[below] at (14cm,-0.5cm) {%
\begin{minipage}{4cm}
\begin{center}
\color{white}\fontfamily{lmss}\fontseries{bx}\selectfont{\Large Article}

\bigskip

\emph{par\\{\small Stéphane PASQUET}}
\end{center}
\end{minipage}
};
% Titre
\node[below right] (titre) at (0.25cm,-1.5cm) {%
\begin{minipage}{11cm}
\fontfamily{lmss}\fontseries{bx}\selectfont\color{purple}\Huge #1
\end{minipage}
};
\node[below right,text=purple] at ($(titre.south west)+(0,-1em)$) {\fontfamily{lmss}\fontshape{it}\selectfont Disponible sur \url{http://www.mathweb.fr}};
% Date
\node at (14cm,-5.5cm) {%
\begin{minipage}{4cm}
\begin{center}
\fontfamily{lmss}\fontseries{bx}\selectfont\color{black}\today
\end{center}
\end{minipage}
};
\end{tikzpicture}
}
% Sections
\titleformat{\section}[block]
{\fontfamily{lmss}\fontseries{bx}\fontsize{16}{14}\selectfont\color{violet}}
{\thesection}
{1em}
{\fontfamily{lmss}\fontseries{bx}\selectfont}
\setlength{\parindent}{0pt}

% Paragraph

\titleformat{\paragraph}[runin]
{\fontfamily{lmss}\fontseries{b}\selectfont\color{purple}}{\theparagraph}{1em}{}
% Enoncé

\newsavebox{\PASboxEnonce}

\newenvironment{enonce}
{%
\begin{lrbox}{\PASboxEnonce}
\fontfamily{lmss}
\fontshape{it}
\selectfont
}
{%
\end{lrbox}
\begin{tikzpicture}
\tikzstyle{degrade} = [rectangle,inner sep=10pt,fill=violet!30,path fading=east]
\node[degrade] {\begin{minipage}{\linewidth}\usebox{\PASboxEnonce}\end{minipage}};
\end{tikzpicture}
}

% Itemize

\setlist[itemize,1]{label={\color{purple}\textbullet}}

% footpage

\cfoot{\fontfamily{lmss}\fontseries{bx}\selectfont\color{white}\fcolorbox{violet}{violet}{\thepage}}

\renewcommand{\headrulewidth}{0pt}
\newcommand{\sgn}[1]{\text{sgn}(#1)}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newenvironment{cadrecode}{%
  \def\FrameCommand{{\color[HTML]{888888}\vrule width 3pt}\colorbox{gray!10}}%
  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
{\endMakeFramed}

\begin{document}
\pagestyle{fancy}
\chapHead{La méthode de Hörner}

\section*{Introduction}

Considérons un polynôme $P$, dont une racine est égale à $a$.\\
La méthode de HÖRNER va nous permettre de trouver les coefficients du polynôme $Q$ tel que :
\[P(x)=(x-a)Q(x)\]
Bien entendu, il existe d'autres méthodes, comme la \emph{division euclidienne de polyn\^omes} ou encore la \emph{méthode des coefficients indéterminés}, mais nous allons voir que la méthode de HÖRNER a deux avantages sur les autres : sa rapidité et le fait que l'on puisse la programmer aisément.

\section*{Un exemple simple}

Considérons le polyn\^ome :
\[ P(x)=x^4-3x^3+7x^2-4x-12\]
dont une racine évidente est $a=2$.\\
Nous allons réfléchir à une méthode qui nous permet de trouver les coefficients de $Q(x)$, tel que $P(x)=(x-2)Q(x)$, à l'aide d'une division euclidienne.
\begin{center}
\begin{tabular}{SrSrSrSrSr|Sl}
$x^4$ & $\textcolor{red}{-3}x^3$ & $+7x^2$ & $-4x$ & $-12$ & $x-2$\\
\cline{6-6}
$-x^4$ & $\textcolor{red}{+2}x^3$ &  &  & & $x^3\textcolor{red}{-1}x^2\textcolor{blue}{+5}x\textcolor{green!60!black}{+6}$\\
\cline{1-2}
       & $\textcolor{red}{-1}x^3$ & $\textcolor{blue}{+7}x^2$ & $-4x$ & $-12$ & \\
       & $+x^3$ & $\textcolor{blue}{-2}x^2$ &       &       & \\
\cline{2-3}       
       &        & $\textcolor{blue}{5}x^2$ & $\textcolor{green!60!black}{-4}x$ & $-12$ & \\
       &        & $-5x^2$ & $\textcolor{green!60!black}{+10}x$&      & \\
\cline{3-4}       
       &        &         & $\textcolor{green!60!black}{6}x$ & $-12$ & \\
       &        &         & $-6x$ & $+12$ & \\
       \cline{4-5}
      &        &         &     & 0 & 
\end{tabular}
\end{center}

On peut alors remarquer que :
\begin{itemize}
\item[$\bullet$] $\textcolor{red}{-1}=-3+2\times2$
\item[$\bullet$] $\textcolor{blue}{5}=7+2\times\textcolor{red}{(-1)}$
\item[$\bullet$] $6=-4+2\times\textcolor{blue}{5}$
\end{itemize}

\newpage

\AddToShipoutPictureBG
{%
	\put(0,\LenToUnit{\dimexpr\paperheight-2cm})
	{%
		\begin{tikzpicture}
		\begin{scope}[rotate=-90]
		\fill[violet!80] (12cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!70] (12.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (13cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (12cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!50] (12.5cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (12cm,-3.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (13.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
		\end{scope}
		\end{tikzpicture}
	}
	\put(\LenToUnit{\dimexpr\paperwidth-1.5cm},0)
	{%
		\begin{tikzpicture}
		\begin{scope}[rotate=90]
		\fill[violet!80] (12cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!70] (12.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (13cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (12cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!50] (12.5cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (12cm,-3.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (13.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
		\end{scope}
		\end{tikzpicture}
	}
}

\section*{Généralisation}

Posons $P(x)=\displaystyle\sum_{k\leqslant n} p_kx^k$, $Q(x)=\displaystyle\sum_{k<n} q_kx^k$ et $a$ une racine de $P$.\\
D'après le raisonnement précédent, on peut écrire :
\[ 
\left\lbrace 
\begin{array}{l}
q_{n-1}=p_n\\
q_k=p_{k+1}+aq_{k+1}\quad\forall 0\leqslant k<n
\end{array}
\right. 
\]

\section*{Schématisation}

On schématise l'algorithme de HÖRNER à l'aide d'un tableau :
\begin{center}
\begin{tikzpicture}[>=stealth',every node/.style={scale=0.9}]
\matrix[draw,fill=gray!10,rounded corners] (m) [matrix of math nodes, row sep=3em, column sep=3em]
{
|(pn)|p_n & |(pnmu)| p_{n-1} & |(pnmd)| p_{n-2} & \cdots & |(pu)| p_1 & |(pz)| p_0\\
|(qn)|q_{n-1} & |(qnmu)| q_{n-2} & |(qnmd)| q_{n-3} & \cdots & |(qu)| q_0 & |(qz)| 0\\
};
\draw[->] (pn)--(qn);
\draw[->] (qn.north east)--(pnmu.south) node[midway,above,rotate=35]{$\times a+$}--(qnmu) node [midway,below,rotate=90]{$=$};
\draw[->] (qnmu.north east)--(pnmd.south) node[midway,above,rotate=35]{$\times a+$}--(qnmd) node [midway,below,rotate=90]{$=$};
\draw[->] (qu.north east)--(pz.south) node[midway,above,rotate=35]{$\times a+$}--(qz) node [midway,below,rotate=90]{$=$};
\end{tikzpicture}
\end{center}

\section*{Application}

Soit :
\[ P(x)=3x^5-4x^4+8x^3-3x^2-2x-2.\]
Une racine de $P$ est $a=1$ d'où :
\begin{center}
\begin{tikzpicture}[>=stealth',every node/.style={scale=0.9}]
\matrix[draw,fill=gray!10,rounded corners] (m) [matrix of math nodes, row sep=3em, column sep=3em]
{
|(p5)|3 & |(p4)| -4 & |(p3)| 8 & |(p2)| -3 & |(p1)| -2 & |(p0)| -2\\
|(q5)|3 & |(q4)| -1 & |(q3)| 7 & |(q2)| 4 & |(q1)| 2 & |(q0)| 0\\
};
\draw[->] (p5)--(q5);
\draw[->] (q5.north east)--(p4.south) node[midway,above,rotate=35]{$\times 1+$}--(q4) node [midway,below,rotate=90]{$=$};
\draw[->] (q4.north east)--(p3.south) node[midway,above,rotate=35]{$\times 1+$}--(q3) node [midway,below,rotate=90]{$=$};
\draw[->] (q3.north east)--(p2.south) node[midway,above,rotate=35]{$\times 1+$}--(q2) node [midway,below,rotate=90]{$=$};
\draw[->] (q2.north east)--(p1.south) node[midway,above,rotate=35]{$\times 1+$}--(q1) node [midway,below,rotate=90]{$=$};
\draw[->] (q1.north east)--(p0.south) node[midway,above,rotate=35]{$\times 1+$}--(q0) node [midway,below,rotate=90]{$=$};
\end{tikzpicture}
\end{center}

D'où :
\[
P(x)=(x-1)(3x^4-x^3+7x^2+4x+2).
\]

\section*{Algorithme}

\begin{algo}{Méthode de Hörner}
\begin{algoentries}
Nombre entier n (degré du polynôme P)\\
Liste P (coefficients dans le polynôme P)\\
Nombre réel a (racine du polynôme P)
\end{algoentries}
\begin{algobody}
P[n]$\rightarrow$Q[n-1]
\begin{algofor}{i}{n-2}{0}
P[i+1]+a*Q[i+1]$\rightarrow$Q[i]
\end{algofor}
\end{algobody}
\begin{algoend}
Afficher Q
\end{algoend}
\end{algo}

\section*{Programme Python}


\begin{lstlisting}[%
language=python,%
showspaces=false,%
showstringspaces=false,%
frame=single,%
frameround=tttt,%
framerule=5pt,%
keywordstyle=\color{green!50!black}\bfseries,%
basicstyle=\ttfamily]
n = int(input("Degré du polynôme : "))
a = float(input("Racine du polynôme : "))
p = (n+1)*[0]
for i in range(0,n+1):
    print("Coefficient de x^",i," : ")
    p[i]=float(input());

q = n*[0]
q[n-1] = p[n]
j = n-2
while j > -1:
    q[j] = p[j+1]+a*q[j+1]
    j=j-1

for i in range(0,n):
    print("Coefficient de x^",i," : ",q[i],end='\n')
\end{lstlisting}
\end{document}