buenas, no me queda muy claro como resolver este ejercicio, tendría que usar una función auxiliar que vaya acumulando los resultados?
se agradece si me pueden dar una mano.
gracias
Este es un problema difícil.
La clave puede estar en pensar la estructura, el relacionamiento entre casos, al revés de lo habitual.
Es decir que para tratar el polinomio
que es igual a 
no consideremos los subcasos de la forma 
, con 
entre 0 y 
, sino los subcasos 
.
La función recursiva tendría este encabezado:
float hornerRec ( float * P , uint i , uint n , float x );
Lo que cambia de caso a caso es la.
Lo primero a preguntarse es ¿cuál es el valor de para el cual no hace falta hacer llamadas recursivas? Ese es el caso base.
Esto sería el inicio de una posible solución. Falta bastante. Seguí preguntando si hace falta.
La clave puede estar en pensar la estructura, el relacionamiento entre casos, al revés de lo habitual.
Es decir que para tratar el polinomio
que es igual a no consideremos los subcasos de la forma , con entre 0 y , sino los subcasos .La función recursiva tendría este encabezado:
float hornerRec ( float * P , uint i , uint n , float x );
Lo que cambia de caso a caso es la
. Lo primero a preguntarse es ¿cuál es el valor de
para el cual no hace falta hacer llamadas recursivas? Ese es el caso base.Esto sería el inicio de una posible solución. Falta bastante. Seguí preguntando si hace falta.
gracias por la respuesta.
yo lo estaba tratando de encarar de la siguiente manera:
float hornerAcum(float* P,uint n, int acum ,float x){
if (n==0)
return P[0];
else{
acum=(acum)*x+P[n];
return acum+hornerAcum(P,n-1,acum,x);
}
}
float horner(float*P,uint n,float x){
return hornerAcum(P,n,0,x);
}
se que tiene alguno errores, pero de esta manera puede llegar a resolverse, o va por otro lado la cosa?
yo lo estaba tratando de encarar de la siguiente manera:
float hornerAcum(float* P,uint n, int acum ,float x){
if (n==0)
return P[0];
else{
acum=(acum)*x+P[n];
return acum+hornerAcum(P,n-1,acum,x);
}
}
float horner(float*P,uint n,float x){
return hornerAcum(P,n,0,x);
}
se que tiene alguno errores, pero de esta manera puede llegar a resolverse, o va por otro lado la cosa?
Creo que esa versión va bien encaminada. Habría un problema con el caso base porque perderías lo acumulado. Y puede ser que sobre la última suma. Porque la motivación de esta versión que sea recursión de cola, y así como está lo último que se hace no es la llamada recursiva sino la suma.
Pero en lo esencial parece correcta.
Pero en lo esencial parece correcta.
gracias por responder.
Estuve tratando de corregir ese error, Se me ocurrió agregar antes del return la siguiente linea:
acum=acum+hornerAcum(P,n-1,acum,x); y luego devolver acum.
Haciendo esto tampoco llego al resultado.
Como podría arreglarlo?
gracias
Estuve tratando de corregir ese error, Se me ocurrió agregar antes del return la siguiente linea:
acum=acum+hornerAcum(P,n-1,acum,x); y luego devolver acum.
Haciendo esto tampoco llego al resultado.
Como podría arreglarlo?
gracias
¿Será necesario hacer la suma?
Hay que tener en cuenta que representa acum.
Hay que tener en cuenta que representa acum.
El polinomio, como puse más arriba, lo podemos expresar así: 
Al invocar la función cuando el coeficiente es 
el valor del parámetro acum es y por lo tanto se cumple
el valor del parámetro acum es y por lo tanto se cumple
.Y esto se cumple en cada una de las llamadas.
Poniendo como subíndice el coeficiente para el que se invoca la función:
= a(x)- ¿qué devuelve el caso base? Puede depender de qué elijas como caso base.
- ¿cómo debe transformarse el parámetro acum para la llamada recursiva (por ejemplo ¿cómo se transforma
en 
)? Es parecido a lo que pusiste pero no igual. - ¿cómo se usa el resultado de la llamada recursiva? Hay que recordar que el valor que devuelve es
.
gracias por la respuesta.
Igualmente sigue sin quedarme muy claro como arreglarlo.
Estuve revisando la manera en que transformo acum de i en acum de i-1 y no veo que tendría que cambiar.
Igualmente sigue sin quedarme muy claro como arreglarlo.
Estuve revisando la manera en que transformo acum de i en acum de i-1 y no veo que tendría que cambiar.
No entiendo porque tu acum empieza en n y termina en -1,tu caso base sería cuando n es -1?Si es así, equivale a mi caso base cuando n=0?
La suma lo hice para que cuando llegue al caso base, sume P[0] y devuelva a(x).
Con respecto al segundo punto que señalé, como transformar en , lo que hiciste está bien. Me confundió ver la y no me dí cuenta que esa variable es el parámetro que corresponde al coeficiente (pensé que era el de la llamada inicial).
El primer punto, el del caso base. Sí, se puede elegir -1 o 0. Si es -1 el valor del parámetro
es igual al resultado buscado. Para algunos esto permite una solución elegante y otros la consideran rebuscada y prefieren que el caso base sea 0. En este último caso el resultado debe ser 
.
Y sobre el tercer punto, el valor devuelto en cada una de las llamadas recursivas es, por lo que debe cumplirse
.
en , lo que hiciste está bien. Me confundió ver la y no me dí cuenta que esa variable es el parámetro que corresponde al coeficiente (pensé que era el de la llamada inicial).El primer punto, el del caso base. Sí, se puede elegir -1 o 0. Si es -1 el valor del parámetro
es igual al resultado buscado. Para algunos esto permite una solución elegante y otros la consideran rebuscada y prefieren que el caso base sea 0. En este último caso el resultado debe ser .Y sobre el tercer punto, el valor devuelto en cada una de las llamadas recursivas es
, por lo que debe cumplirse.Buenas estaba haciendo este ejercicio y creo que lo resolví. Estuve leyendo el intercambio y me pareció bueno sumarme.
En este caso la representación del polinomio es un puntero a un arreglo flotante? De ser así esa memoria dinámica se pide antes de invocar a la función cierto? Me gustaría entender un poco mas esto porque en el Ejercicio2 el del String palíndromo hice el código pero no lo podía implementar. No tengo muy clara la sintaxis para hacer el arreglo (dinámico) ya sea de caracteres o de flotantes, luego inicializarlo para poder usarlo en las respectivas funciones que piden en el practico. Se que esto no es necesario pero es una manera de corroborar que lo que hice este bien.
Este es el codigo:
float hornerRec (float *p, unit i, unit n, float x){
if (n==0)
return i;
else
return hornerRec(P, i*x + P[n-1], n-1, x);
}
//funcion que piden en el Ej7
float horner(float *P, uint n, float x){
return hornerRec(P, P[n], n,x);
Abajo dejo razonamiento solo por si a alguien le sirve.
saludos.
En realidad ahora que lo pienso Fernando creo que a manera en la que lo resolví es igual a como vos decís porque vos llamas a la función con los siguientes parámetros hornerRec(P, 0, n, x) pero tu caso base es distinto a lo que entras con el i en 0. Vos vas hasta -1 y en mi caso es hasta 0.
Pero si entras con 0 en la siguiente llamada recursiva vas a entrar con P[n] que es como yo la invoco de una.
Creo que si no estoy equivocado y estoy entendiendo bien por donde iba tu razonamiento, entonces estamos hablando de los mismo.
La funcion que tiene n = -1 como caso base es
float hornerRec(float *P, uint i, unit n, float x){
if (n==-1)
return i;
else
return hornerRec(P, i*x + P[n], n-1, x);
}
float horner(float *P, unit n, float x){
return float hornerRec(P, 0, n, x)
}
Un saludo
Pero si entras con 0 en la siguiente llamada recursiva vas a entrar con P[n] que es como yo la invoco de una.
Creo que si no estoy equivocado y estoy entendiendo bien por donde iba tu razonamiento, entonces estamos hablando de los mismo.
La funcion que tiene n = -1 como caso base es
float hornerRec(float *P, uint i, unit n, float x){
if (n==-1)
return i;
else
return hornerRec(P, i*x + P[n], n-1, x);
}
float horner(float *P, unit n, float x){
return float hornerRec(P, 0, n, x)
}
Un saludo
Hola Nicolás.
Gracias por aportar a la discusión. MIrando tu solución parece razonable. Probala para verificar con algunos casos pero tiene pinta de que anda bien.
Sobre las preguntas
En este caso la representación del polinomio es un puntero a un arreglo flotante? De ser así esa memoria dinámica se pide antes de invocar a la función cierto?
La respuesta a la primer pregunta es sí. La segunda también es sí. No es que sea una arreglo dinámico. Si bien es memoria que se pide en tiempo de ejecución. lo manejamos como memoria estática en el sentido que no cambiamos su tamaño.
La forma de pedir memoria sería la siguiente:
float * P = new float[n] (esto iría de 0 a n-1)
otra forma en tiempo de compilaciòn sería:
float P[n];
Saludos,
Gracias por aportar a la discusión. MIrando tu solución parece razonable. Probala para verificar con algunos casos pero tiene pinta de que anda bien.
Sobre las preguntas
En este caso la representación del polinomio es un puntero a un arreglo flotante? De ser así esa memoria dinámica se pide antes de invocar a la función cierto?
La respuesta a la primer pregunta es sí. La segunda también es sí. No es que sea una arreglo dinámico. Si bien es memoria que se pide en tiempo de ejecución. lo manejamos como memoria estática en el sentido que no cambiamos su tamaño.
La forma de pedir memoria sería la siguiente:
float * P = new float[n] (esto iría de 0 a n-1)
otra forma en tiempo de compilaciòn sería:
float P[n];
Saludos,
Gracias Federico, mañana lo pruebo bien a ver si anda. Pero entonces en el caso de un string el largo no es variable, quiero decir no te lee cualquier nombre o palabra que ingreses por la entrada. Se que igual tu aclaración fue sobre un arreglo que representa al polinomio pero por las dudas pregunto.
Un saludo.
Un saludo.
Hola
El tamaño del arreglo debe ser n + 1.
Con respecto a lo que planteabas, sí, los dos algoritmos son casi iguales. Hay una pequeña diferencia de lo que calculan y en el significado de i.
En el primero, en el que el caso base es 0 y la primera invocación es con i = P[n], lo que se calcula es![P[0] + x P[1] + \cdots + x^{n-1} P[n-1] + x^n \cdot i](https://eva.fing.edu.uy/filter/tex/pix.php/32f63bf8cd535ab88e675970fb0e7776.png "P[0] + x P[1] + \cdots + x^{n-1} P[n-1] + x^n \cdot i")
.
En el segundo, en el que el caso base es -1 y la primera invocación es con i = 0, lo que se calcula es![P[0] + x P[1] + \cdots + x^{n} P[n] + x^{n+1} \cdot i](https://eva.fing.edu.uy/filter/tex/pix.php/5696e26e5f024413d3345729929d735f.png "P[0] + x P[1] + \cdots + x^{n} P[n] + x^{n+1} \cdot i")
.
Pero me parece que genera algo de confusión los nombres de los parámetros, sobre todo el i, que hace pensar en un índice, o valor de exponente; y creo que también n porque puede hacer pensar en el grado del polinomio inicial.
Desde el inicio de esta conversación hubo dos algoritmos que son bastante diferentes.
El tamaño del arreglo debe ser n + 1.
Con respecto a lo que planteabas, sí, los dos algoritmos son casi iguales. Hay una pequeña diferencia de lo que calculan y en el significado de i.
En el primero, en el que el caso base es 0 y la primera invocación es con i = P[n], lo que se calcula es
.En el segundo, en el que el caso base es -1 y la primera invocación es con i = 0, lo que se calcula es
.Pero me parece que genera algo de confusión los nombres de los parámetros, sobre todo el i, que hace pensar en un índice, o valor de exponente; y creo que también n porque puede hacer pensar en el grado del polinomio inicial.
Desde el inicio de esta conversación hubo dos algoritmos que son bastante diferentes.
El primero tenía el mismo encabezado que el que vos hiciste ahora,
float hornerRec ( float * P , uint i , uint n , float x ),
pero en realidad lo que calcula es ![P[i] + x P[i+1] + \cdots + x^{n-i}P[n]](https://eva.fing.edu.uy/filter/tex/pix.php/f19f53ef4d5d46c5b6b670fc8997f2c0.png "P[i] + x P[i+1] + \cdots + x^{n-i}P[n]")
.
. El segundo, el que planteó Bruno,
float hornerAcum(float* P,uint n, int acum ,float x),
es el equivalente, salvo por nombres y orden de los parámetros, al tuyo. Voy a hacer pequeños cambios a ese encabezado de Bruno para ponerlo en correspondencia con el tuyo
float hornerAcum(float* P, float acum, int j ,float x)
Puse j en lugar de n, porque ese parámetro no es el grado del polinomio original, sino el del monomio que se está tratando, y acum en lugar de i porque es una evaluación que se viene acumulando. En tu versión acum es![P[j] + x P[j+1] + \cdots + x^{n-j} P[j]](https://eva.fing.edu.uy/filter/tex/pix.php/0af5c7a92359d4775f67ef6227c654d4.png "P[j] + x P[j+1] + \cdots + x^{n-j} P[j]")
. Entonces, por lo dicho antes, tu algoritmo calcula ![P[0] + x P[1] + \cdots + x^{j-1} P[j-1] + x^j \cdot (P[j] + x P[j+1] + \cdots + x^{n-j} P[j])](https://eva.fing.edu.uy/filter/tex/pix.php/fbd6eee0aa2abf68a450a557a3dd9a6b.png "P[0] + x P[1] + \cdots + x^{j-1} P[j-1] + x^j \cdot (P[j] + x P[j+1] + \cdots + x^{n-j} P[j])")
, lo cual es correcto.
float hornerAcum(float* P, float acum, int j ,float x)
Puse j en lugar de n, porque ese parámetro no es el grado del polinomio original, sino el del monomio que se está tratando, y acum en lugar de i porque es una evaluación que se viene acumulando. En tu versión acum es
. Entonces, por lo dicho antes, tu algoritmo calcula , lo cual es correcto. Y este algoritmo tiene la ventaja con respecto al primero de ser tail recursion. Se puede derivar del primero debido al acumulador.
Buenas, quería saber si mi solución es correcta, adjunto imagen;
Hola.
Puede ser correcta, depende de lo que se pretenda calcular, de cuál es la especificación de hornerRec. ¿Qué representan n y acum?
En la letra la n es el grado del polinomio. En cambio, por lo que se ve en tu main, estás considerando que n es la cantidad de monomios.
Para entender hornerRec, si al parámetro n le llamaras i, para poder diferenciarlo del n del llamado inicial, ¿qué representa acum?
Puede ser correcta, depende de lo que se pretenda calcular, de cuál es la especificación de hornerRec. ¿Qué representan n y acum?
En la letra la n es el grado del polinomio. En cambio, por lo que se ve en tu main, estás considerando que n es la cantidad de monomios.
Para entender hornerRec, si al parámetro n le llamaras i, para poder diferenciarlo del n del llamado inicial, ¿qué representa acum?
Buenas, gracias por la respuesta. Entiendo que si n es el grado del polinomio, entonces mi arreglo tendría que ser n+1, y si en el parámetro n lo llamo i , lo debería invocar comomo i= i+1 para usarlo como la cantidad de monomios.
Acum representaría xan+1 en la regla de horner P(x) = a0 + x(a1 + x(a2 + · · · + (xan)· · ·))). Entonces en el primer llamado me devolvería xan, es correcto?
Acum representaría xan+1 en la regla de horner P(x) = a0 + x(a1 + x(a2 + · · · + (xan)· · ·))). Entonces en el primer llamado me devolvería xan, es correcto?
Ahora prestando atención, creo que acum no está cumpliendo ninguna función
Posiblemente quieras actualizar acum en cada llamada.
Te sugiero que vuelvas a intentar haciendo que n tenga el mismo rol que en la letra y que a la variable que en HornerRec le llamás n le des otro nombre, por ejemplo i, para poder expresar en función de i y n qué significa acum y así poder entender la relación entre las llamadas. También tené es cuenta que en la primera invocación de HornerRec accedés a P fuera del rango en que está definido.
Te sugiero que vuelvas a intentar haciendo que n tenga el mismo rol que en la letra y que a la variable que en HornerRec le llamás n le des otro nombre, por ejemplo i, para poder expresar en función de i y n qué significa acum y así poder entender la relación entre las llamadas. También tené es cuenta que en la primera invocación de HornerRec accedés a P fuera del rango en que está definido.
Hola Nicolás,
Tuve un error en el último ejemplo del mensaje anterior "float P[n]" y es que el tamaño del arreglo tiene que estar definido para que la memoria del arreglo se reserve en tiempo de compilación, dos ejemplos serían:
int n = 100;
float P [n];
o
float P [100];
Saludos
Tuve un error en el último ejemplo del mensaje anterior "float P[n]" y es que el tamaño del arreglo tiene que estar definido para que la memoria del arreglo se reserve en tiempo de compilación, dos ejemplos serían:
int n = 100;
float P [n];
o
float P [100];
Saludos
Esto funciona. ¿Es válido así o hay algo mal?
float hornerRecursivo(float coef[], uint i, uint n, float x) {
if (i == n) {
return coef[n];
}
return coef[i] + x*hornerRecursivo(coef, i+1, n, x);
}
float horner(float coef[], uint n, float x) {
return hornerRecursivo(coef, 0, n, x);
}
Hola Gennaro, cómo estás?
No me queda del todo clara tu consulta?
Si tu consultas está asociada a la posibilidad de utilizar una función recursiva como lo haces con "hornerRecursivo", la respuesta es sí.
Si quieres saber si tu código funciona, te invito a que lo pruebes haciendo un main sencillo y verás que tu solución devuelve el resultado esperado.
Por último, pero no menos importante, por favor nota que conceptualmente no estás resolviendo el ejercicio correctamente, porque no estás respetando la letra. Se solicita una función que reciba, entre otras cosas, un float * P, pero tu función recibe un float chef[].
Saludos
No me queda del todo clara tu consulta?
Si tu consultas está asociada a la posibilidad de utilizar una función recursiva como lo haces con "hornerRecursivo", la respuesta es sí.
Si quieres saber si tu código funciona, te invito a que lo pruebes haciendo un main sencillo y verás que tu solución devuelve el resultado esperado.
Por último, pero no menos importante, por favor nota que conceptualmente no estás resolviendo el ejercicio correctamente, porque no estás respetando la letra. Se solicita una función que reciba, entre otras cosas, un float * P, pero tu función recibe un float chef[].
Saludos
Hola, tengo una consulta con este ejercicio, en el caso de que i == n ¿No debería de devolver coef[n]*x ? Porque sino entiendo que se estaría perdiendo una evaluación del polinomio.
Muchas gracias.
Muchas gracias.