Resultados 1 al 5 de 5

Tema: duda recursividad pascal

  1. #1 duda recursividad pascal 
    Medio
    Fecha de ingreso
    Apr 2006
    Mensajes
    85
    Descargas
    0
    Uploads
    0
    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
    Citar  
     

  2. #2  
    Medio
    Fecha de ingreso
    Jan 2006
    Mensajes
    98
    Descargas
    0
    Uploads
    0
    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.
    Última edición por Polimeron; 09-04-2006 a las 18:39
    Citar  
     

  3. #3  
    Medio
    Fecha de ingreso
    Apr 2006
    Mensajes
    85
    Descargas
    0
    Uploads
    0
    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
    Citar  
     

  4. #4  
    Medio
    Fecha de ingreso
    Jan 2006
    Mensajes
    98
    Descargas
    0
    Uploads
    0
    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
    Citar  
     

  5. #5  
    Medio
    Fecha de ingreso
    Apr 2006
    Mensajes
    85
    Descargas
    0
    Uploads
    0
    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
    Citar  
     

Temas similares

  1. recursividad
    Por krizalid en el foro GENERAL
    Respuestas: 4
    Último mensaje: 29-06-2011, 05:45
  2. Recursividad con vectores en Java
    Por Hispasat88 en el foro GENERAL
    Respuestas: 24
    Último mensaje: 22-04-2009, 19:50
  3. Duda? pascal
    Por intruso123 en el foro PROGRAMACION DESKTOP
    Respuestas: 6
    Último mensaje: 14-05-2008, 00:46
  4. Pascal
    Por MartínAriel en el foro GENERAL
    Respuestas: 1
    Último mensaje: 23-03-2006, 17:00
  5. turbo pascal
    Por NAro1 en el foro PROGRAMACION DESKTOP
    Respuestas: 5
    Último mensaje: 11-01-2003, 13:58

Marcadores

Marcadores

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •