Autor Tema: Suma polinómica (lista simple lineal) Abstracto de datos

0 Usuarios y 1 Visitante están viendo este tema.

14 Mayo, 2009, 06:41 pm
Leído 2558 veces

Watt

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 328
  • Karma: +0/-0
  • Sexo: Masculino
  • Dos numeros manejan el mundo?
Hola, estoy buscando la forma de hacer en pseudocodigo un programa que me sume dos polinomios (esos dos polinomios a sumar estan ordenados con respecto a su exponente), pero la verdad lo unico que me salio fue la primera parte para descartar que esten vacios:

Código: [Seleccionar]
Funcion SumaPol(L:puntero,Q:puntero): puntero       //Esta funcion recibe el puntero externo de las dos
                                                                       //listas a sumar y devuelve otra ya sumada.
{
     if(EsListaVacia(Q) and EsListaVacia(L)   SumaPol=error;
     else if (EsListaVacia(Q)) SumaPol=L;
     else if (EsListaVacia(L)) SumaPol=Q;
     else
           //Aqui vendria el codigo en cuestion
  :banghead: :banghead:

15 Mayo, 2009, 01:12 am
Respuesta #1

malpas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 17
  • Karma: +0/-0
  • Sexo: Masculino
Si están ordenados, quizá deberías ver cómo el algoritmo de mezcla natural puede ayudarte en este caso. Es sencillo.

Saludos.

15 Mayo, 2009, 01:31 am
Respuesta #2

Watt

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 328
  • Karma: +0/-0
  • Sexo: Masculino
  • Dos numeros manejan el mundo?
Que quieres decir exactamente con mezcla natural ?

15 Mayo, 2009, 06:08 pm
Respuesta #3

malpas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 17
  • Karma: +0/-0
  • Sexo: Masculino
El algoritmo de mezcla natural sirve para mezclar dos vectores ordenados en otro vector ordenado. El algoritmo es el siguiente:

Se tiene dos punteros A y B, uno en cada vector. Se compara el contenido de A con el de B; si el contenido de A es menor que el de B, se coje el contenido de A y se introduce en el vector final, se avanza el puntero de A y se vuelve  comparar. Si el de A es ahora mayor, se mete el de B y se avanza B. Y luego a volver a comparar siguiendo el mismo procedimiento. Si son iguales, se mete cualqueira de los dos, y se avanzan los dos punteros.

Esto te vale en tu caso, porque lo que debes hacer es comprobar exponentes. Sólo debes tener en cuenta que cuando son distintos, sumas el contenido del mayor o el menor con 0 y dejas el resultado en la lista destino. Cuando sean iguales sumas ambos miembros y lo dejas en la lista destino; incrementando los punteros de las listas como te he descrito antes.

Espero que te sirva para lo que quieres hacer xD.

Saludos.

01 Junio, 2009, 06:07 pm
Respuesta #4

Watt

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 328
  • Karma: +0/-0
  • Sexo: Masculino
  • Dos numeros manejan el mundo?
Mira las listas los polinomios serian algo asi:

\( P(x)=7X^4+3X^3-5X \)
\( Q(x)=6x^7+3x^5-x^4+x^2+x-7 \)
\( R(x)=P(x)+Q(x)=6x^7+3x^5+6x^4+3x^3+x^2-4x-7 \)

Para lo cual escribi el siguiente pseudocodigo

Código: [Seleccionar]
Func SumaPol(P:puntnodo,Q:puntnodo):puntnodo  //Devuelve el puntero externo a la lista nueva

if[ EsListaVacia(Q) and EsListaVacia(P) ]
   "Error"
else
   if[ EsListaVacia(Q) and not EsListaVacia(P) ]
SumaPol=P
   else
        if[ EsListaVacia(P) and not EsListaVacia(Q) ]
    SumaPol=Q
        else

     if[ P|.info.exp > Q|.info ]
                  O=P , T=Q
     else
  O=Q , T=P
     end if

     R=PrimerElementoLista(CrearLista(),O)
     K=R
     a=O|.info.exp   //"a" es una variable del tipo entera
             
     if( O.info.exp != T.info.exp )
          O=Siguiente(O)
             end if

     for( i=0; i< a; i++ )   //"i" es una variable del tipo entera
                    tmp1=0
    tmp2=0
    tmp3=0   //"los tmp son variables enteras temporales"
   
    while(not EsListaVacia(O) )
if(O|.info.exp == i)
    tmp1=O|.info.coef
end if
O=Siguiente(O)
    end while

      while(not EsListaVacia(T) )
if(T|.info.exp == i)
    tmp2=T|.info.coef
end if
T=Siguiente(T)
    end while

    if( tmp1 != 0  or tmp2 != 0)   
                            tmp3=tmp1+tmp2
    E|.info.exp = i
    E|.info.coef = tmp3
            InsertarDespues(R,E)
                    end if
              end for
     
              SumaPol=K
end if
    end if
end if

Te dejo la notación por si no entiendes algo:

P (puntero al nodo)
P| (el nodo)
P|.info.exp (el exponente del nodo)
P|.info.coef (el coeficiente del nodo)