Ver Mensaje Individual
  #17 (permalink)  
Antiguo 20/11/2014, 12:09
Pantaláimon
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 4 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

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:
Ver original
  1. int contarNegativos(int arr[], int n) {
  2.     return n > 0 ? (arr[n-1] < 0) + contarNegativos(arr, n - 1) : 0;
  3. }

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:
Ver original
  1. char* idiag(char* cadena, int n, int pos, char* resultado) {
  2.     if (n >= 1) {
  3.         if (n != 1)
  4.             sprintf(resultado + pos, "\n%*c", n - 1, ' ');
  5.         resultado[pos + n] = cadena[n - 1];
  6.         idiag(cadena, n - 1, pos - n, resultado);
  7.     }
  8.     return resultado;
  9. }
  10.  
  11. char* diag(char* cadena, char* resultado) {
  12.     int n = strlen(cadena);
  13.     return idiag(cadena, n, n * (n + 1) / 2 - 2, resultado);
  14. }
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:
Ver original
  1. 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:
Ver original
  1. 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++:
Ver original
  1. std::string diag(const std::string& str);
Mi solución es:
Código C++:
Ver original
  1. #include <string>
  2. #include <iostream>
  3.  
  4. std::string idiag(const std::string& cadena, int n) {
  5.     if(n > 0)
  6.         return idiag(cadena, n - 1) + (n == 1 ? "" : "\n") + std::string(n - 1, ' ') + cadena[n - 1];
  7.     else
  8.         return std::string();
  9. }
  10.  
  11. std::string diag(const std::string& cadena) {
  12.     return idiag(cadena, cadena.length());
  13. }
  14.  
  15. int main (void) {
  16.     std::string cadena = "abcde";
  17.  
  18.     std::string resultado = diag(cadena);
  19.  
  20.     std::cout << resultado << std::endl;
  21.  
  22.     return 0;
  23. }

Cita:
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":
Cita:
(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.

Cita:
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!
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 20/11/2014 a las 12:20