duda recursividad pascal

[kamsky]

tengo k implementar un TAD polinomio :

TYPE
Tpolinomio = ^polinom;

polinom = RECORD

grado:integer;
coeficiente:real;
sig:Tpolinomio;


end;



procedure polinomiovacio(var p:Tpolinomio);

procedure insertarcampo(var pol:Tpolinomio;gradopol:integer;coefpol:real);

procedure crear(var p:Tpolinomio);

procedure imprimir(p:Tpolinomio);

procedure sumar(p1,p2:Tpolinomio; var p3:Tpolinomio);

function evaluar(p:Tpolinomio; x:real):Real;

{procedure multiplicar(p1,p2:Tpolinomio; var p3:Tpolinomio); }

procedure liberarmemoria(p:Tpolinomio);


con las operaciones ahi peustas, la duda me surge a la hora de hacer el proce sumar

lo tengo que hacer mediante recursividad y respetando la estructura LIFO (pila), y he estado pensando pero no se me ocurre nada en concreto, les rogaría que me aporten ideas frescas,muchas gracias, me urge

[Polimeron]

Si he entendido bien y se supone que los polinomios (los respectivos coeficientes de la variable de cada grado) están almacenados en una estructura tipo pila, usar la recursividad para calcular su suma es bastante facil porque para el caso general, lo unico que tienes que ir haciendo es recuperar los elementos del tope de las pilas de polinomios P1 y P2 y almacenar el resultado de su suma en el polinomio P3(mientras que ninguna pila llegue a estar vacia --> caso base; en caso de que alguna termine antes que otra, es decir, tenga mas elementos que la otra, solo copias los elementos de la sobrante a la P3). Por este caso no te bastara con solo un caso base y se empeorara un poco la eficiencia, por tener que hacer mas comparaciones pero por lo demas...


Segun lo que veo no se si se tratara de una pila de ese tipo de registros(tipo polinomio) o de un array de registros; de la otra forma(el array) en lugar de ir recuperando tope de la pila, tendras que recorrerlo desde la ultima posicion (suponiendo que insertas en el orden) e ir haciendo lo mismo que en el caso de una pila.

Si hay alguna duda con respecto a la resupesta, avisad me, y aclaro lo mejor que sepa, o en su caso te escribo el algoritmo en el pseudocodigo, auque creo que es mejor que lo intentes solo.

[kamsky]

ante todo gracias por la ayuda

el ejercicio ya lo tengo hecho en forma no recursiva, el problema es el que tu comentas, que al tener que haber varios casos base se pierde la eficacia, por que hay que ver si ambos no son vacios, y despues cual de los dos es vacio y cual no, por eso mi duda, de si se os ocurria otra forma de hacerlo recursivamente, pero creo que la respuesta es no..

a por cierto, tu pusiste como hacerlo en un caso general, comparo , si son iguales los sumo y si son diferentes pongo el de mayor grado y a continuacion el de menor grado, pero eso no es exactamente asi, me explico, supongamos que tenemos los siguientes polinomios:

3 + 5x^2 + 4x^3

4 + 3x + 6x^2

cogemos y comparamos el grado de 3 y d 4, al ser igual se suma, quedando:

p3 = 7

continuemos, cogemos 5x^2 y 3x, al ser menor 3x lo coloco primero y a continuacion 5x^2, resultando:

p3= 7 + 3x + 5x^2

finalmente, cogemos 4x^3 y 6x^2 y lso coloco:

p3 = 7 + 3x + 5x^2 + 6x^2 + 4x^3
y ahi esta el problema, 5x^2 y 6x^2 aparecen como 2 nodos diferentes cuando no deberian serlo.. este tipo de casos complican mas el codigo, por lo que creo que en este caso es más eficaz y más cómodo el hacer el procedimiento sin recursividad, si alguien cree lo contrario les ruego me lo hagan saber...

repito mi agradecimiento por los comentarios

[Polimeron]

Buenas,

Tienes razón en ese caso que pones, habria que comparar los grados de los elementos de los polinomios P1 y P2 antes de sumar, y luego realizar otra comparacion con el tope de la pila del polinomio P3 (para insertar o sumar con el tope existente); para facilitar esto, yo supuse que los elementos se insertan en orden de grados y si alguno no existe, insertas un 0 en la pila con el dicho grado, con lo cual ese problema se resolveria. En cuanto al procedimiento recursivo, la eficiencia temporal no esta muy clara hasta comparar los dos algoritmos en concreto, pero es cierto que en lo que se refiere a la eficiencia espacial, es peor que el metodo iterativo(por usar la pila del sistema para los resultados intermedios); me gustaria que posetees el algoritmo iterativo que tienes para compararlo con una posible solucion recursiva (para ver si se puede conseguir una mejora de verdad). Saludos

[kamsky]

ahi dejo el procedimiento que use finalmente para sumar:


{Procedimiento que dados 2 polinomios devuelve un 3º que es la suma
de los anteriores}

procedure sumar(p1,p2:Tpolinomio; var p3:Tpolinomio);

begin {procedimiento sumar}



while ((p1<>nil) and (p2<>nil)) do
begin

if ((p1^.grado) = (p2^.grado)) then
begin

insertarcampo(p3, p1^.grado,( p1^.coeficiente + p2^.coeficiente));

p1:=p1^.sig;
p2:=p2^.sig;

end {fin if}

else

if((p1^.grado) < (p2^.grado)) then
begin
insertarcampo(p3, p1^.grado, p1^.coeficiente);

p1:=p1^.sig;

end {fin else if}

else

if((p1^.grado) > (p2^.grado)) then
begin
insertarcampo(p3, p2^.grado, p2^.coeficiente);

p2:=p2^.sig;

end; {fin else if}

end; {fin while}

while p1<> nil do
begin
insertarcampo(p3, p1^.grado, p1^.coeficiente);

p1:=p1^.sig;

end; {fin while}

while p2<> nil do
begin
insertarcampo(p3, p2^.grado, p2^.coeficiente);

p2:=p2^.sig;
end; {fin while}

end;{fin procedimiento sumar}


el problema de lo que tu dijiste es que si me meten un coeficiente que sea 0 no lo almaceno como 0 , si no que no lo almaceno ,de ahi surge el problema que expuse.... bueno, creo que como lo he hecho está relativamente bien, ahora tengo otro problema, tengo que hacer un procedimiento que sea multiplicar 2 polinomios, lo intente hacer recursivamente y es un lio, hice algo parecido a esto:


{Procedimiento que dados 2 polinomios, devuelve un 3º que es la
multiplicación de los 2 anteriores}

procedure multiplicar(p1,p2:Tpolinomio; var p3:Tpolinomio);

var
paux:Tpolinomio; {variable auxiliar}
paux2:Tpolinomio; {variable auxiliar}
p2primero:Tpolinomio;

begin {procedimiento multiplicar}
writeln('dentro');
if numelementos(p1) > 0 then
begin
writeln('numelementos p1 >0 = ',numelementos(p1));
if numelementos(p2) > 0 then
begin
writeln('numelementos p2 >0 = ',numelementos(p2));
p2primero:= p2;

paux2^.grado:= (p1^.grado + p2^.grado);
writeln('paux2 grado = ',paux2^.grado);
paux2^.coeficiente:= (p1^.coeficiente * p2^.coeficiente);
writeln('paux2 coef = ',paux2^.coeficiente:3:0);
paux2^.sig:= nil;

sumar(p3,paux2,paux );
p3:=paux;

p2:= p2^.sig;

multiplicar(p1,p2,p3);

end {fin if}
else
begin
p2:= p2primero;
end; {fin else}

writeln('p1 grado= ',p1^.grado);
p1:=p1^.sig;
if p1<>nil then
writeln('p1grado= ',p1^.grado);

multiplicar(p1,p2,p3);

end; {fin if}

writeln('fuera');

end; {procedimiento multiplicar}




pero no m tira... alguna idea????????? gracias por la ayuda d new