Exercicis resolts d’ADA

EDIT: Actualitzo el link perquè funcioni, ja que he vist que hi ha hagut gent que els ha intentat baixar
EDIT2 (24/12/08) Torno a actualitzar al link, ja que he tornat a veure intents de descàrrega, espero no haver-lo de tornar a canviar…

Aquí teniu la versió més recent, on hi ha resolts els exercicis:
1.3 1.4 1.27 1.28 1.37 2.5 2.29

Si trobeu errors, feu-me’ls saber!

—–

Afegeixo també una llista d’algoritmes que han passat les proves del Jutge.

radixSort
saldo
quadratLlatí
n-reines
sudoku

Desmotracions per inducció d’Anàlisi i Disseny d’Algorismes

Avui he perdut unes quantes hores iniciant-me al LaTex, un editor de text professional, en què no veus el resultat del
que estàs fent fins que no ho “compiles”. Diguem-ne que és un “programador” de documents. Tu no escrius HOLA i fas click a Negrita i es converteix en HOLA si no que tu escrius \bf{HOLA} i un cop ho compiles, veuràs el que vols veure.
És molt útil a l’hora d’escriure fórmules, ja que pots treballar amb index, subindex, sumatoris, arrels, límits, i tal i cual molt fàcilment, molt més fàcilment que amb l’editor de ecuaciones de microsoft, que a part de ser poc intuïtiu, es penja cada dos per tres, i fa el que vol, bàsicament.
Així que per practicar, he passat a LaTex unes quantes demostracions per inducció, que en el seu moment vaig necessitar i no vaig trobar, i finalment vaig haver de fer. Aquí us penjo el codi LaTex, i el resultat com a imatge.

Són tres, el primer no li trobo gaire utilitat, però els 2 següents sí que la tenen!


\documentstyle{article}
\begin{document}
Demostrar:
$\displaystyle\sum_{i=1}^k i2^{-i}=2-k2^{-k}-2^{1-k}$
\begin{center}
Per a k=1,
\begin{eqnarray*}
2^{-1}&=&2-2^{-1}-2^{1-1}\\
2^{-1}&=&2-2^{-1}-1\\
2^{-1}&=&1-2^{-1}\\
2^{-1}&=&2^{-1}\\
\end{eqnarray*}
\end{center}
\begin{center}
\noindent Per a $k\geq 1$,\\
\end{center}
\noindent \textbf {Hipotesi d'induccio}\\
\begin{eqnarray*}
\underline {2^{-1}+ 2 \cdot 2^{-2}+3 \cdot 2^{-3}+4 \cdot 2^{-4}+...+k\cdot2^{-k}}&=&\underline{\underline{2-k\cdot2^{-k}-2^{1-k}}}\\
\end{eqnarray*}
\noindent \textbf {Demostracio}\\
\begin{eqnarray*}
\underline {2^{-1} + 2 \cdot 2^{-2}+3 \cdot 2^{-3}+4 \cdot 2^{-4}+...+k\cdot2^{-k}}+(k+1)\cdot2^{-k+1} &=& 2-(k+1)\cdot2^{-k+1}-2^{1-(k+1)}\\
\underline{\underline{2-k\cdot2^{-k}-2^{1-k}}}+(k+1)\cdot2^{-(k+1)}&=&2-(k+1)\cdot2^{-k-1}-2^{1-(k+1)}\\
-k\cdot2^{-k}-2^{1-k}+k\cdot2^{-k-1}+2^{-k-1}&=&-k\cdot2^{-k-1}-2^{-k-1}-2^{-k}\\
-k\cdot2^{-k}-2^{1-k}+2^1\cdot k\cdot 2^{-k-1}+2^1\cdot 2^{-k-1}&=&-2^{-k}\\
-k\cdot2^{-k}-2^{1-k}+k\cdot2^{-k}+2^{-k}&=&-2^{-k}\\
2^{-k}\left(-k-2+k+1\right) &=&-2^{-k}\\
2^{-k}\left(-1\right) &=&-2^{-k}\\
-2^{-k}&=&-2^{-k}\\
\end{eqnarray*}
\end{document};

El del sumatori de les i’s, és a dir 1+2+3+4+5…


\documentstyle{article}
\begin{document}
Demostrar:
$\displaystyle\sum_{i=0}^n i=\frac{n\left(n+1\right)}{2}$
\begin{center}
Per a n=1,
\begin{eqnarray*}
1&=&\frac{2 \cdot 1}{2}\\
1&=&1\\
\end{eqnarray*}
\end{center}
\begin{center}
\noindent Per a $n\geq 1$,\\
\end{center}
\noindent \textbf {Hipotesi d'induccio}\\
\begin{eqnarray*}
\underline {1+2+3+4+5+...+n}&=&\underline{\underline{\frac{n\left(n+1\right)}{2}}}\\
\end{eqnarray*}
\noindent \textbf {Demostracio}\\
\begin{eqnarray*}
\underline {1+2+3+4+5+...+n}+\left(n+1\right) &=& \frac{\left(n+1\right)\left(n+2\right)}{2}\\
\underline{\underline{\frac{n\left(n+1\right)}{2}}}+n+1&=&\frac{n^2}{2}+\frac{2\cdot n}{2}+\frac{n}{2}+1 \\
\frac{n\left(n+1\right)}{2}&=&\frac{n^2}{2}+\frac{n}{2}\\
\frac{n\left(n+1\right)}{2}&=&\frac{n\left(n+1\right)}{2}
\end{eqnarray*}
\end{document}


I finalment el del sumatori dels 2^i, que diria que te a veure amb les torres de Hanoi, potser el número de moviments que has de fer segons el número de blocs que tinguis? Crec que si que era això, si tens 3 blocs, has de fer 2^n+1 -1 moviments per tal de moure’ls tots d’una banda a l’altra…


\documentstyle{article}
\begin{document}
Demostrar:
$\displaystyle\sum_{i=0}^n 2^i=2^{n+1}-1$
\begin{center}
Per a n=0,
\begin{eqnarray*}
2^0&=&2^1-1\\
1&=&2-1\\
1&=&1\\
\end{eqnarray*}
\end{center}
\begin{center}
\noindent Per a $n\geq 0$,\\
\end{center}
\noindent \textbf {Hipotesi d'induccio}\\
\begin{eqnarray*}
\underline {2^0+2^1+2^2+2^3+2^4+...+2^n}&=&\underline{\underline{2^{n+1}-1}}\\
\end{eqnarray*}
\noindent \textbf {Demostracio}\\
\begin{eqnarray*}
\underline {2^0+2^1+2^2+2^3+2^4+...+2^n}+2^{n+1} &=& 2^{n+2}-1\\
\underline{\underline{2^{n+1}-1}}+2^{n+1}&=&2^{n+2}-1 \\
2^{n+1}+2^{n+1}&=&2^{n+2}\\
2^{n+2}&=&2^{n+2}\\
\end{eqnarray*}
\end{document}