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}


Un programa útil

Doncs sí, per primer cop a la meva vida, he fet un programa mínimament útil, que millora l’accessibilitat de les persones invidents en l’escriptura a l’ordinador.
El programa consisteix en un simulador d’escriptura braille. Les tecles FDS JKL passen a ser les tecles 1 2 3 4 5 6 dels teclats braille, i així una persona invident que no vulguis fer servir un teclat normal tal com és concebut, pot escriure sense cap problema.
Ara estic fent la versió que un cop escrita una lletra, la canta, d’aquesta manera pot saber si el que escriu és correcte en tot moment!
Si algú vol el programa, que me’l demani!

Problemes d’SO d’E/S (entrada sortida)

*LINK ACTUALITZAT, ja que he detectat alguns intents de baixar-se els codis en C (suposo que perquè demà és l’examen final d’SO…)

Aquí penjo alguns dels exercicis d’E/S d’SO programats en C.
El Zip amb tots els codis

Problema 2.3 Catail
Un programa que requereix un fitxer d’entrada, i surt indèntic per la sortida estàndard.

Problema 2.4 Micp
Feu un programa en C i crides al sistema UNIX que permeti copiar fitxers plans de manera que detecti els mateixos errors i generi els mateixos missatges d’error que la comanda cp de UNIX.

>micp fitxer_origen fitxer_copiat

Heu d’afegir al vostre programa MICP una opció ( -o ) que indiqui que si el fitxer destí ja existeix no ha de sobrescriure’l.
Problema 2.5 Rev
Modifiqueu el comportament de MICP de manera que el fitxer copiat sigui l’invers. Aquest programa l’anomenarem REV i mantindrà l’opció -o que heu afegit.

Problema 2.6 Mitee
Escriviu un programa que copïi el que rep per la seva entrada estàndar sobre la seva sortida estàndar i a més, sobre un fitxer que ens passaran com a paràmetre. En el cas que el fitxer que passem com a paràmetre ja existeixi, Mitee ha de sobrescriure’l.
>mitee
Donarà error ja que falta el paràmetre.

>mitee pppp
Copiarà el que introduïm pel teclat sobre el fitxer pppp i a més, ens ho mostrarà per pantalla.

>mitee cccc <aaaa >bbbb
Generarà dos fitxers, el bbbb i el cccc, tots dos amb el mateix contingut que aaaa.
Afegeix a Mitee l’opció -a del tee. (consultar man tee)

Problema 2.9 Intercambio de Parejas
Implementar el comando exchange que intercambia dos columnas de caracteres de un fichero.
>exchange c1 c2 file
Donde file será el fichero de entrada y c1 y c2 son las dos columnas a intercambiar. El fichero modificado se ha de extraer por la salida estándar.
Ejemplo:

cat fichero.txt
1000300000
1000200000

>exchange 0 4 fichero.txt
3000100000
2000100000