Problema 2 · Programació II UDL 2012

Justificación formal o inductiva del diseño (definición de casos base y regla inductiva sobre el tamaño del sufijo)

Solución: El tamaño del problema viene determinado por la longitud del sufijo, dada por $N = \text{elems.length} - \text{pos}$. - Caso base: Cuando el sufijo está vacío, es decir, cuando $\text{pos} \ge \text{elems.length}$ (o $N = 0$), el número de ocurrencias de cualquier valor es trivialmente $0$. - Paso recursivo: Para un sufijo no vacío ($\text{pos} < \text{elems.length}$), el sufijo comprende el elemento actual `elems[pos]` seguido por el subsufijo que inicia en $\text{pos} + 1$. Por hipótesis de inducción, `timesInSuffix(elems, pos + 1, value)` computa correctamente las apariciones en un sufijo de longitud $N - 1$. Así: - Si `elems[pos] == value`, el resultado es $1 + \text{timesInSuffix}(\text{elems}, \text{pos} + 1, \text{value})$. - Si `elems[pos] != value`, el resultado es $0 + \text{timesInSuffix}(\text{elems}, \text{pos} + 1, \text{value})$. En cada llamada, `pos` incrementa en 1, garantizando la convergencia hacia el caso base.

Implementación del método recursivo timesInSuffix

Solución: ```java if (pos >= elems.length) { return 0; } int count = (elems[pos] == value) ? 1 : 0; return count + timesInSuffix(elems, pos + 1, value); ``` ```java if (pos >= elems.length) { return 0; } if (elems[pos] == value) { return 1 + timesInSuffix(elems, pos + 1, value); } else { return timesInSuffix(elems, pos + 1, value); } ```