Diseño algorítmico de funciones

1. Enunciado del problema


Hay elecciones en la República de Tranfuyastán y se trata de diseñar una función recursiva, completamente verificada, que permita comprobar si hay predominio de algún partido político en una circunscripción determinada, compuesta por un número variable de distritos electorales. Así, esa función deberá poder ser utilizada para poder comprobar los datos de cadacurcunscripción que en la noche electoral llegarán a la sede central del servicio informático del PINTA. En los casos en que no haya predominancia, será necesaria una segunda vuelta.

2. Especificación del algoritmo

{Q ( n ( 0 }
fun kpred (a: vector [1..n] de etiquetas, p: etiqueta, u: natural dev b: booleano)
{R ( b = (N( ( {1..n}.p = a[(])>u}

Dado un vector a de etiquetas de partidospolíticos (vencedores de los distritos de una circunscripción), kpred devolverá 1 o verdadero si la etiqueta p (el partido p) está presente en ese vector en número superior al umbral u. Si es inferior, kpred devolverá 0. Veamos qué ocurre con 3 valores para el valor umbral u:
u=0 ( kpred devolverá verdadero siempre que el partido p haya sido votado
u=n-1 ( kpred devuelve verdadero sólo si pha ganado por unanimidad
nMOD2 ( kpred devolverá verdadero si p tiene mayoría absoluta




3. Algoritmo recursivo no final


1. Función auxiliar.
Nuestro problema no permite un diseño recursivo de forma directa. Para eso dividiremos el problema en dos partes: conteo y decisión sobre la predominancia. Para la primera parte del problema definimos una función más sencilla quekpred, que llamaremos kcont, que solamente cuenta las veces que una etiqueta p aparece en un vector a. Es nuestra función auxiliar. Dejamos para después la decisión sobre u.

2. Especificación de kcont.
{Q ( n ( 0 }
fun kcont (a: vector [1..n] de etiquetas, p: etiqueta dev k: natural)
{R ( k = (N( ( {1..n}.p = a[(])}
Como decía en 3.1, kcont devuelve el número k de veces que p aparece en elvector de etiquetas a.

3. Expresión de kpred respecto a kcont.


kpred( a, p, u ) = ( kcont( a, p ) > u )





4. Especificación de la función inmersora y llamada inicial


A partir de kcont construiremos una función inmersora ikcont que permitirá una solución recursiva del problema. Para ello debilitaremos la poscondición de kcont, sustituyendo la constante n por una variablei:
{R ( k = (N( ( {1..i}.p = a[(]) ( i = n}
pasa a ser
{R ( k = (N( ( {1..i}.p = a[(])}
y por lo tanto diseñaremos ikcont para que se cumpla kcont( a, p) = ikcont(a, p, i) ( i =n, que sería la llamada inicial.
La especificación de la función inmersora queda entonces:
{Q ( n ( 0 ( 0 ( i ( n }
fun ikcont (a: vector [1..n] de etiquetas, p: etiqueta, i: natural dev k: natural)
{R ( k = (N( ({1..i}.p = a[(])}


5. Análisis por casos de ikcont.


Si n ( 0, como dice la precondición, entonces se pueden dar tres casos:

i = 0 ( {1..0} = conjunto vacío, luego ikcont devolverá k = 0
Este es el caso trivial: cuando i=0 el vector está vacío. Este será el caso donde deberá terminar la descomposición recursiva.


i > 0 si p = a[i] ( k = ikcont( a, p, i-1) + 1si p ( a[i] ( k = ikcont( a, p, i-1) + 0


Este sería el caso no trivial, que tiene además un predicado lógico que será necesario evaluar para enlazar con la llamada recursiva posterior. En concreto, se comprueba si el elemento a[i] es igual o no a la etiqueta de referencia p. Cada vez que el algoritmo pase por este punto, la recursión avanzará y la fracción del vector original quequeda por analizar será 1 posición menor: i-1.




6. Composición algorítmica


{Q ( n ( 0 ( 0 ( i ( n }
fun ikcont (a: vector [1..n] de etiquetas, p: etiqueta, i: natural dev k: natural)
caso i = 0 ( k = 0
i > 0 p = a[i] ( k = ikcont( a, p, i-1) + 1
p ( a[i] ( k = ikcont( a, p, i-1) + 0
fcaso
ffun
{R ( k = (N( ( {1..i}.p = a[(])}

Como vemos,...