Petando la pila. Problemas y retos usando recursividad.

[Pantaláimon]

Buenas.

Dado que veo que el tema de recursividad está gustando bastante propongo crear este hilo donde iré proponiendo diferentes retos a resolver en C sin usar iteración (bucles for, while, do while) ni goto, claro. Se pueden usar tantas funciones como se quieran.

De momento iré sacando los problemas de un pdf que tengo de ejercicios en Haskell y los iré adaptando a C. Pues venga, ¡Vamos al grano y presento los dos primeros retos!

1) Escriba una función contarNegativos que cuente cuantos números negativos existen en una lista
Ejemplo: dado el array {1, 4, -3, 2, -1, -8, 0, 1} debe devolver 3:

Aquí el código de plantilla:

Código C:

#include <stdio.h>
 
/* más codigo si hace falta */
 
int contarNegativos(int arr[], int n) {
    /* Escribir código */
    return 0;
}
   
int main (void) {
    int arr[] = {1, 4, -3, 2, -1, -8, 0, 1};
    int n = sizeof arr / sizeof *arr;
 
    /* calcular cantidad de negativos */
    int cantidad = contarNegativos(arr, n);
    /* mostrar cantidad de negativos */
    printf("%d\n", cantidad);
    return 0;
}
 

2) Escriba una función diag que tenga una lista de caracteres como parámetro y que dé como resultado los caracteres
en una diagonal.
Cadena:

Código C:

"abcde"
 

Resultado:

Código C:

a
 b
  c
   d
    e
 

Aquí el código de plantilla:

Código C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
/* más codigo si hace falta */
 
char* diag(char* cadena, char* resultado) {
    /* Escribir código */
    resultado[0] = '\0';
    return resultado;
}
 
int main (void) {
    char cadena [] = "abcde";
    int n = strlen(cadena);
 
    char* resultado = malloc(n * n + 1); /* doy mas espacio del necesario */
 
    // a partir de la cadena de caracteres retornar la nueva que tenga los caracteres en diagonal
    resultado = diag(cadena, resultado);
 
    //mostrar resultado
    puts(resultado);
 
    free(resultado);
    return 0;
}
 

Ya se irá complicando la cosa

Un saludo!

[Madh]

Una forma muy divertida de dominar la recursividad

El primer problema es bastante sencillito, aquí va mi soución:

Código C:

#include <stdio.h>
 
/* más codigo si hace falta */
 
int contarNegativos(int arr[], int n) {
    /* Escribir código */
 
    if (n>0){
        if (arr[n] < 0)
            return 1 + contarNegativos(arr, n-1);
        else
            return 0 + contarNegativos(arr, n-1);
    }
    
    else
        return 0;
}
   
int main (void) {
    int arr[] = {1, 4, -3, 2, -1, -8, 0, 1};
    int n = sizeof arr / sizeof *arr;
 
    /* calcular cantidad de negativos */
    int cantidad = contarNegativos(arr, n);
    /* mostrar cantidad de negativos */
    printf("%d\n", cantidad);
    return 0;
}
 

Respecto al segundo, pues no tengo ni idea. ¿De verdad se puede implementar con dos parámetros sin pasarle también el tamaño de la cadena original?

Saludos

[kutcher]

Excelente iniciativa Pantaláimon me gusta mucho este tipo de retos

Solución al primer reto:

Código C++:

#include <stdio.h>
 
int contarNegativos(int arr[], int n)
{
    if (n == 0) return(0);
    return (arr[n - 1] < 0 ? 1 : 0) + contarNegativos(arr, n - 1);
}
 
int main (void)
{
    int arr[] = {1, 4, -3, 2, -1, -8, 0, 1};
    int n = sizeof arr / sizeof *arr;
 
    int cantidad = contarNegativos(arr, n);
    printf("%d\n", cantidad);
 
    return(0);
}
 

Segundo:

Código C++:

#include <stdio.h>
 
char diag(char *str, int n)
{
    if (str[n] == '\0') return(0);
    printf( "%*c\n", n + 1, str[n]);
    return diag(str, n + 1);
}
 
int main (void)
{
    char cadena [] = "abcde";
    diag (cadena, 0);
 
    return(0);
}
 

Saludos y a la espera de mas retos

[leosansan]

Porfi, uno o dos días es lo que necesito porque el disco duro ha "petado".

Desde que esté operativo me pongo a ello.

Saluditos de León.

[vangodp]

ok... acepto el reto XD
Ni voy a mirar los otros posts hasta que tenga echo el código.
Pero no tengo mucha exp asi que hare como pueda jaja.

[eferion]

La propuesta parece interesante, ya veremos como acaba

ejercicio 1:

Código C++:

#include <stdio.h>
 
int contarNegativos(int arr[], int n)
{
  if ( n > 0 )
    return (*arr < 0) + contarNegativos( ++arr, n-1 );
  return 0;
}
 
int main (void)
{
  int arr[] = {1, 4, -3, 2, -1, -8, 0, 1};
  int n = sizeof arr / sizeof *arr;
 
  /* calcular cantidad de negativos */
  int cantidad = contarNegativos(arr, n);
  /* mostrar cantidad de negativos */
  printf("%d\n", cantidad);
  return 0;
}
 

ejercicio 2:

Código C++:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
/* más codigo si hace falta */
 
char* diag(char* cadena, char* resultado)
{
  if (*cadena)
  {
    int espacio = *resultado + 1;
    sprintf( resultado, "%*c\n%c", espacio, *cadena, espacio );
    diag( ++cadena, resultado + espacio + 1 );
  }
  else
    *resultado = 0;
  return resultado;
}
 
int main (void) {
    char cadena [] = "abcde";
    int n = strlen(cadena);
 
    char* resultado = (char*)calloc(n * n + 1, sizeof(char)); /* doy mas espacio del necesario */
 
    // a partir de la cadena de caracteres retornar la nueva que tenga los caracteres en diagonal
    resultado = diag(cadena, resultado);
 
    //mostrar resultado
    puts(resultado);
 
    free(resultado);
    return 0;
}
 

La única licencia que me he permitido es cambiar el malloc por calloc en el segundo ejercicio. Escribir de forma recursiva en un buffer sin inicializar no me parece buena idea.

[Pantaláimon]

Iniciado por eferion

La propuesta parece interesante, ya veremos como acaba
La única licencia que me he permitido es cambiar el malloc por calloc en el segundo ejercicio. Escribir de forma recursiva en un buffer sin inicializar no me parece buena idea.

Cierto, me parece conveniente. Gracias, voy a editarlo.

kutcher, el segundo problema trataría de escribir el resultado en una variable y no enviarlo directamente a la salida estándar.

Edit: vaya no puedo editar el primer post pero mejor la opción de usar calloc como dice eferion.
Saludos!!

[kutcher]

Iniciado por Pantaláimon

kutcher, el segundo problema trataría de escribir el resultado en una variable y no enviarlo directamente a la salida estándar.

xD es verdad, entonces dejo otra solución algo parecida a la de eferion pero usando snprintf:

Código C++:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
char* diag(char* s, char* resultado)
{
    static int i = 0, j = 0;
    if (*s)
    {
        j += snprintf (resultado + j,  26 - j, "%*c\n", ++i, *s);
        diag (++s, resultado);
    }
    return resultado;
}
 
int main (void)
{
    char cadena [] = "abcde";
    int n = strlen(cadena);
 
    char* resultado = (char*)calloc(n * n + 1, sizeof(char));
    resultado = diag(cadena, resultado);
    puts(resultado);
 
    free(resultado);
    return 0;
}
 

Saludos y que siga esto no pude pasar por aquí estos últimos días ya que estaba algo ocupado

[eferion]

Iniciado por kutcher

xD es verdad, entonces dejo otra solución algo parecida a la de eferion pero usando snprintf:

El problema que tiene tu función es que, debido a las variables globales, es de un solo uso. Si la intentas usar más de una vez en la ejecución de un programa vas a tener problemas.

Tienes que intentar solucionar ese problema. Forma parte del reto ;)

[kutcher]

Iniciado por eferion

El problema que tiene tu función es que, debido a las variables globales, es de un solo uso. Si la intentas usar más de una vez en la ejecución de un programa vas a tener problemas.

Tienes que intentar solucionar ese problema. Forma parte del reto ;)

Ya veo, modifique la función pero me he permitido agregar un parámetro mas a esta, espero que esto no sea un inconveniente :

Código C++:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
char* diag(char* s, char* resultado, int i)
{
    if (*s)
    {
        int j = 0;
        j = snprintf (resultado, i + 2, "%*c\n", i, *s);
        diag (++s, resultado + j, ++i);
    }
    return resultado;
}
 
int main (void)
{
    char cadena [] = "abcde";
    int n = strlen(cadena);
 
    char* resultado = (char*)calloc(n * n + 1, sizeof(char));
    resultado = diag(cadena, resultado, 1);
    puts(resultado);
 
    free(resultado);
    return 0;
}
 

Saludos

[Pantaláimon]

En el primer post comenté que no había problema en usar tantas funciones como se quisieran. Incluso dejé un comentario en las plantillas para dejarlo claro:

Código Javascript:

/* más codigo si hace falta */
 

Así que tu código podría quedar así:

Código Javascript:

char* auxdiag(char* s, char* resultado, int i)
{
    if (*s)
    {
        int j = 0;
        j = snprintf (resultado, i + 2, "%*c\n", i, *s);
        diag (++s, resultado + j, ++i);
    }
    return resultado;
}
 
char* diag(char* s, char* resultado) {
    return auxdiag(cadena, resultado, 1);
}
 
int main (void)
{
    char cadena [] = "abcde";
    int n = strlen(cadena);
 
    char* resultado = (char*)calloc(n * n + 1, sizeof(char));
    resultado = diag(cadena, resultado);
    puts(resultado);
 
    free(resultado);
    return 0;
}
 

¿leosan, vangodp, al final no os animáis?

Creo que la idea será ir poniendo dos problemas por semana. Así que el viernes doy las soluciones que tenía yo para estos problemas y propongo dos más.

Un saludo!

[eferion]

Entonces hay que esperar hasta el viernes para tener nuevos retos ???

[Pantaláimon]

Iniciado por eferion

Entonces hay que esperar hasta el viernes para tener nuevos retos ???

Venga va, uno sencillo para ir abriendo boca.

Crear una función la potencia que calcule la potencia entera no-negativa de un número a. Esta es la firma de la función:

Código C:

double potencia(double a, unsigned n);
 

¡Sed imaginativos!

[leosansan]

Iniciado por Pantaláimon

Venga va, uno sencillo para ir abriendo boca.

Crear una función la potencia que calcule la potencia entera no-negativa de un número a. Esta es la firma de la función:

Código C:

double potencia(double a, unsigned n);
 

¡Sed imaginativos!

Mucha imaginación para esto no creo

Código C++:

double potencia ( double base , unsigned exponente ) { 
    return  ( exponente == 0 ) ? 1 : base * potencia ( base , exponente - 1 ) ;
}
 
int main ( void ) {
    printf ( "%g" , potencia ( 8 , 3 ) ) ;
    return 0;
}
 

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

¡¡¡Saluditos!!!

[kutcher]

Iniciado por Pantaláimon

Venga va, uno sencillo para ir abriendo boca.

al fin mas retos, dejo mi solución :

Código C++:

double potencia(double a, unsigned n)
{
    if (n == 0) return 1;
    double x = potencia (a, n >> 1);
    return (n & 1) == 0 ? x * x : a * x * x;
}
 
int main(void)
{
  printf("%lf\n", potencia(2, 8));
 
  return (0);
}
 

Pantaláimon mas difíciles por favor esto ni siquiera me costo cinco minutos

[leosansan]

Iniciado por kutcher

al fin mas retos, dejo mi solución :

Mejor usa %g en printf y evitas la retahíla de ceros decimales.

¡¡¡Saluditos!!!

[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!

[leosansan]

Iniciado por Pantaláimon

Buenas!
usa un algoritmo de divide y vencerás. Que quizá para pequeños cómputos 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.

¿Insinúas que la función recursiva hace esto:

Código C++:

potencia ( 2 , 4 )  = 2 * potencia ( 2 , 3 ) =
                    = 2 * 2 * potencia ( 2 , 2 ) =
                    = 2 * 2 * 2 * potencia ( 2 , 1 ) =
                    = 2 * 2 * 2 * 2 * potencia ( 2 , 0 ) =
                    = 2 * 2 * 2 * 2 * 1
 

en lugar de esto?

Código C++:

potencia ( 2 , 4 )  = 2 * potencia ( 2 , 3 )     =
                    = 2 * 2 * potencia ( 2 , 2 ) =
                    = 4 * 2 * potencia ( 2 , 1 ) =
                    = 8 * 2 * potencia ( 2 , 0 ) =
                    = 16 * 1
 

Por cierto, podríamos ahorrarnos el multiplicar por uno. Por ejemplo:

Código C++:

double potencia ( double base , unsigned exponente ) { 
  if ( exponente >= 1 ) return base * potencia ( base , exponente - 1 ) ;
}
 

¡¡¡Saluditos!!!

[amchacon]

¿Quereís un problema recursivo?

Dado la siguiente estructura:

Código C++:

struct arbol
{
    arbol* ramas[2];
    int dato;
};
 

Dado un array a, transformarlo en un arbol. Os pongo un ejemplo:

[1,2,3,4]

No es necesario que esté ordenado.

[amchacon]

Iniciado por leosansan

Código C++:

double potencia ( double base , unsigned exponente ) { 
  if ( exponente >= 1 ) return base * potencia ( base , exponente - 1 ) ;
}
 

¡¡¡Saluditos!!!

Falta un else ahí ^^

[Pantaláimon]

No, leosan, no insinúo eso. En los dos casos que expones se realizan 4 multiplicaciones, tanto si vas multiplicando mientras avanzas al siguiente paso como si las multiplicas todas al final.

Fíjate en lo que hace el algoritmo de kutcher y verás:

Código pseudocódigo:

Calculamos potencia(2,8):
potencia(2, 8) = x * x
donde x = potencia(2,4)
 
Calculamos potencia(2,4):
potencia(2, 4) = x * x
donde x = potencia(2,2)
 
Calculamos potencia(2,1):
potencia(2,1) = 2 * x * x
donde x = potencia(2, 0) = 1
 
En total 4 multiplicaciones.
 

¿Cuanto costaría calcular potencia(2, 32)? sólo dos multiplicaciones más: 6

En cambio con tu algoritmo deberías hacer del orden de 32 multiplicaciones. Esta es la idea escondida.

Un saludo!

[Pantaláimon]

¡Hola de nuevo!

¡Llegó el día! Así que aquí os traigo dos problemas más:

1) Crear una función comb que reciba dos parámetros y te devuelva el coeficiente binomial. La fórmula del coeficiente binomial es: n! / (k! * (n-k)!) donde "!" es el signo del factorial. La firma de la función será:

Código C:

unsigned comb(unsigned n, unsigned k);
 

Una de las utilidades del coeficiente binomial es para calcular el numero de subconjuntos sin repetición ni orden que podemos obtener de otro conjunto. Por ejemplo, imaginemos una bolsa con 5 bolas con las letras A, B, C, D y E y que, entonces, sólo podemos coger 3 bolas. ¿Cuantas posibles combinaciones podemos obtener contando que sacar A,B,E es lo mismo que sacar A,E,B? Pues ese número te lo da: comb(5,3)

2) Dado un número, podemos jugar al siguiente juego:
a) Si es par, lo dividimos entre 2.
b) Si es impar, lo multiplicamos por 3 y luego le sumamos 1.
Podemos realizar estas reglas sobre el número que nos retorna tantas veces como nos dé la gana. Por ejemplo con el 6:

Código explicación:

6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 ...
 

Se puede ver que llega un punto en que hay un ciclo 4 -> 2 -> 1 que se repite indefinidamente. Lothar Collatz, observó que con todos los números que iba probando -tardara más o menos- siempre llegaba al ciclo 4 -> 2 -> 1 y conjeturó que esto debía pasar con todos los números (aún no se ha demostrado que sea cierto pero para el rango de número con que vamos a trabajar es cierto).

En este segundo problema deberemos crear una función promedioCollatz que dado un numero n, nos diga el promedio de pasos que tienen que hacer los numeros del 1 al n para llegar al número 1. Por ejemplo:
1 => 0 pasos para llegar al 1
2 => 1 paso para llegar al 1
3 => 7 pasos para llegar al 1
4 => 2 pasos para llegar al 1
5 => 5 pasos para llegar al 1

Entonces la función promedioCollatz se comportaría de la siguiente manera:

Código explicación:

[B]promedioCollatz(1)[/B] == 0 / 1 == 0
[B]promedioCollatz(2)[/B] == (0+1) / 2 == 0.5
[B]promedioCollatz(3)[/B] == (0+1+7) / 3 == 2.6666..
[B]promedioCollatz(4)[/B] == (0+1+7+2) / 4 == 2.5
[B]promedioCollatz(5)[/B] == (0+1+7+2+5) / 5 == 3
etc...
 

La firma de la función será la siguiente:

Código C:

double promedioCollatz(unsigned num)
 

Los problemas se pueden resolver tanto en C como en C++.

Y ahora, ¡A petar la pila!

[eferion]

Iniciado por Pantaláimon

1) Crear una función comb que reciba dos parámetros y te devuelva el coeficiente binomial.

Código C:

unsigned int comb(
    unsigned int n,
    unsigned int k )
{
  if ( n <= k )
    return 0;
  else if ( k > 0 )
    return n * ( n - k ) * comb( n - 1, k - 1 ) / ( k * ( n - k ) );
  else
    return 1;
}
 

Este de momento era fácil, vamos a ver el siguiente.

Iniciado por Pantaláimon

2) Dado un número, podemos jugar al siguiente juego...

Código C++:

unsigned int collatz(
    const unsigned int n )
{
  if ( n == 1 )
    return 0;
  else if ( n % 2 )
    return 1 + collatz( n * 3 + 1 );
  else
    return 1 + collatz( n / 2 );
}
 
double promedioCollatz(
    const unsigned int num )
{
  if ( num > 0 )
    return ( collatz( num ) + ( num - 1 ) * promedioCollatz( num - 1 ) ) / num;
  else
    return 0;
}
 

Vamos a probar ahora los de amchacon ;)

Iniciado por amchacon

¿Quereís un problema recursivo?

Dado un array a, transformarlo en un arbol. Os pongo un ejemplo:

Estoooooo el árbol no debería quedar con esta otra estructura??

Código:

 1
  \
   2
    \
     3
      \
       4

O si no... ¿qué valor tendrían los nodos en negro?

[leosansan]

Iniciado por Pantaláimon

¡Hola de nuevo!
Y ahora, ¡A petar la pila!

"Güeno" , el primero ( el segundo aún tengo que entenderlo ):

Código C++:

#include <stdio.h>
 
int unsigned comb ( unsigned n , unsigned k ) ; 
 
int main ( ) {
  printf ( "%u" , comb (  12 , 5 ) ) ;
  return 0 ;
}
 
int unsigned comb ( unsigned n , unsigned k )  {
    if ( k > n / 2 )
        k = n - k ;
    if ( k >= 1 )  return ( n  * comb (  n - 1 , k - 1 ) / k ) ;
    else
        return 1;
}
 

Observar que aprovecho las propiedades de los números combinatorios y así si piden como ( 25 , 20 ) calculo su equivalente comb ( 25 , 5 ) que realiza menos operaciones.

¡¡¡Saluditos!!!

[kutcher]

Mi solución al primer reto:

Código C++:

unsigned int comb(unsigned int n, unsigned int k)
{
    if(k > n) return 0;
    if (k == 0) return 1;
    return (k > n/2) ? comb(n, n - k) : n * comb(n - 1, k - 1) / k;
}
 

La solución al segundo esta estuvo medio complicada:

Código C++:

double promedioCollatz(unsigned num)
{
    unsigned y = num;
    if (y <= 1) return 0;
    return (y % 2 == 0) ? 1 + promedioCollatz( y / 2 )
                        : 1 + promedioCollatz( 3 * y + 1 );
}
 

Saludos

[eferion]

Iniciado por kutcher

La solución al segundo esta estuvo medio complicada:

Esa función está mal... no tiene que devolver el número de pasos hasta llegar al 1... tienes que devolver "el promedio", es decir, si esa función recibe un "4" tiene que hacer el siguiente cálculo: ( PASOS_COLLATZ( 4 ) + PASOS_COLLATZ( 3 ) + PASOS_COLLATZ( 2 ) + PASOS_COLLATZ( 1 ) ) / 4

No se si me explico.

[leosansan]

Iniciado por eferion

Esa función está mal... no tiene que devolver el número de pasos hasta llegar al 1... tienes que devolver "el promedio".......................

No se si me explico.

Sí campeón, te explicas alto y claro.

"Creo" no haberla pifiado. En lugar de dos funciones como eferion he usado dos argumentos, espero que sea válido:

Código C++:

#include <stdio.h>
#define NUMERO  8
 
double promedioCollatz ( unsigned num0 , unsigned num ) ; 
 
int main ( ) {
  int n = promedioCollatz ( NUMERO , NUMERO ) ;
  printf ( "\n%g\n" ,  ( ( n - 1 ) /  ( ( float ) NUMERO) ) ) ;
  return 0 ;
}
 
double promedioCollatz ( unsigned num0 , unsigned num )  {
  if ( num0 == 1 )
    return 1 ;
  return ( ( num == 1 ) ? promedioCollatz ( num0 - 1 , num0 - 1  ) : ( num %  2 != 0 ) ?  1 + promedioCollatz ( num0 , 3 * num + 1 ) : 1 + promedioCollatz ( num0 , num / 2 ) ) ;}
 

¡¡¡Saluditos!!!

[leosansan]

EDITO: Aprovecho para "adelgazar" el del coeficiente combinatorio:

Código C++:

include <stdio.h>
 
int unsigned comb ( unsigned n , unsigned k ) ; 
 
int main ( ) {
  printf ( "%u" , comb (  15 , 5 ) ) ;
  return 0 ;
}
 
int unsigned comb ( unsigned n , unsigned k )  {    
  return ( k > n / 2 ) ?  ( comb (  n , k )  ) : ( k >= 1 ) ?  ( n  * comb (  n - 1 , k - 1 ) / k ) : 1 ;}
 

¡¡¡ Horror ¡¡¡, no edita sino que crea un nuevo mensaje. Sorry ¡¡¡.

¡¡¡Saluditos!!!

[Pantaláimon]

Iniciado por leosansan

En lugar de dos funciones como eferion he usado dos argumentos, espero que sea válido:

No es válido leosan, aún no me ha dado tiempo de mirar la solución, pero la firma/prototipo de la función es el requerido por el enunciado. Si la función recursiva tiene más parámetros de los que se requiere, define ésta como una función auxiliar y que la función requerida por el enunciado llame a ésta. Por ejemplo: tal como he hecho para la solución de diag.

Un saludo!

[leosansan]

Iniciado por Pantaláimon

No es válido leosan, aún no me ha dado tiempo de mirar la solución, pero la firma/prototipo de la función es el requerido por el enunciado. Si la función recursiva tiene más parámetros de los que se requiere, define ésta como una función auxiliar y que la función requerida por el enunciado llame a ésta. ............................................

¡¡¡ Quisquilloso, bandido ¡¡¡.

Pero.....mejor que usar otra función, uffffff, ya que nadie ha dicho nada de que esté prohibido usar variables globales :

Código C++:

#include <stdio.h>
#define NUMERO  9
 
unsigned num0 = NUMERO ;
 
double promedioCollatz ( unsigned num ) ; 
 
int main ( ) {
  int n = promedioCollatz ( NUMERO ) ;
  printf ( "\n%g\n" ,  ( ( n - 1 ) /  ( ( float ) NUMERO) ) ) ;
  return 0 ;
}
 
double promedioCollatz ( unsigned num )  {
  if ( num0 == 1 )
    return 1 ;
  return ( ( num == 1 ) ? promedioCollatz ( --num0  ) : ( num %  2 != 0 ) ?  1 + promedioCollatz ( 3 * num + 1 ) : 1 + promedioCollatz ( num / 2 ) ) ;
}
 

Pero yo propondría que los prototipos que indicas sean tan sólo una ayuda por si alguien está muy perdido, así se mejoraría la inventiva e ingenio de los retos. Pero claro, es tan sólo una opinión.....

¡¡¡Saluditos!!!