Petando la pila. Problemas y retos usando recursividad.

[Pantaláimon]

Buenas!

Voy dejando mis soluciones de los retos de la semana. Pero contad que no hay límite de tiempo para resolverlos. Si alguien entra ahora o va a otro ritmo, puede ofrecer sus propuestas sobre retos antiguos sin ningún tipo de problema.

La primera solución fue del mismo estilo de kutcher (empezando a contar por el último), aunque quizá la mía se entiende un poco menos por escribirla en una sola línea:

Código C:

int contarNegativos(int arr[], int n) {
    return n > 0 ? (arr[n-1] < 0) + contarNegativos(arr, n - 1) : 0;
}
 

Y siguiendo la misma lógica (calcular empezando por el final) hice la segunda que a diferencia de las soluciones que habéis dado no añade un carácter de nueva linea al final del string (aunque esto está abierto a interpretaciones):

Código C:

char* idiag(char* cadena, int n, int pos, char* resultado) {
    if (n >= 1) {
        if (n != 1)
            sprintf(resultado + pos, "\n%*c", n - 1, ' ');
        resultado[pos + n] = cadena[n - 1];
        idiag(cadena, n - 1, pos - n, resultado);
    }
    return resultado;
}
 
char* diag(char* cadena, char* resultado) {
    int n = strlen(cadena);
    return idiag(cadena, n, n * (n + 1) / 2 - 2, resultado);
}
 

Aunque, al empezar a rellenar el string por atrás, tuve un pequeño inconveniente: el carácter '\0' se me añadía al final de cada cadena que escribía, no pudiendo, así, resumir la acción en un simple:

Código C:

sprintf(resultado + pos, "\n%*c%c", n - 1, ' ', cadena[n - 1]);
 

Por otro lado, y viendo comportamientos irregulares que tiene C. Por ejemplo, que:

Código C:

printf("%*c", 0, 'a');
 

imprime un carácter 'a'. Y como el hilo es para trabajar con recursividad y temas como el manejo de memoria dinámica los podríamos mandar un poco al garete. Los próximos ejercicios los voy a proponer tanto para resolver en C como C++. Aquí adelanto las solución de diag para C++.

Suponiendo la siguiente firma:

Código C++:

std::string diag(const std::string& str);
 

Mi solución es:

Código C++:

#include <string>
#include <iostream>
 
std::string idiag(const std::string& cadena, int n) {
    if(n > 0)
        return idiag(cadena, n - 1) + (n == 1 ? "" : "\n") + std::string(n - 1, ' ') + cadena[n - 1]; 
    else
        return std::string();
}
 
std::string diag(const std::string& cadena) {
    return idiag(cadena, cadena.length());
}
 
int main (void) {
    std::string cadena = "abcde";
 
    std::string resultado = diag(cadena);
 
    std::cout << resultado << std::endl;
 
    return 0;
}
 

Iniciado por leosansan

Mucha imaginación para esto no creo

Con imaginación, me refería a no tomar la solución más evidente, pues había otras mejores. Estaba esperando una solución como la de kutcher, que independientemente de que use operadores de "gurú del C":

(n & 1) == 0 se podría traducir a (n % 2 == 0)
(n >> 1) se podría traducir a (n / 2)

usa un algoritmo de divide y vencerás. Que quizá para pequeños computos no se nota, pero en caso de trasladar esta función para calculo de potencias con exponentes muy grandes el algoritmo de kutcher gana sobradamente. Por poner un ejemplo, si el exponente es 2^32 , tu algoritmo realizará del orden de 2^32 multiplicaciones mientras que el de kutcher realizará 33 multiplicaciones.

Iniciado por leosansan

Por cierto, ya que la base es un entero podríamos haber hecho la función potencia de tipo int en lugar de double.

La base no es un entero, la base que propuse es double. Un real elevado a un entero no negativo, en general, da un real. Un entero elevado a un entero no negativo, en general, da un entero. No veo razón para elejir mejor una u otra.

¡Mañana dos nuevos retos!