• Author / Uploaded
• Omsar Selazn

Citation preview

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Asignatura

ESTRUCTURAS DE DATOS I Tema

“TDA Polinomio” MSc. Rodolfo Arana Gonzales Abril 2019

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Temas

• •

• •

La estructura de datos “Polinomio” Niveles de definición de la estructura Formas de implementación Programa en lenguaje C++

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Estructura de datos polinomio ¿Que es un polinomio? Un polinomio es una función real sobre una variable real, que tiene la forma: P(x) = anxn + an-1xn-1 + an-2xn-2 + an-3xn-3 + … a0x0 Donde:

an es cualquier número real n es cualquier número natural llamado grado

x es una variable real Ejemplo P(x) = 3x124 + 4x11 – 8x3 + 6x – 9

Grado 124, numero de términos 5.

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Tres niveles de definición de una estructura • Nivel lógico o abstracto Especificar el Tipo de Datos Abstracto o TDA

• Nivel de Implementación Modelo de computadora en un lenguaje C++

• Nivel de aplicación Uso practico de la estructura

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Nivel lógico: Tipo de Datos Abstracto (TDA) Cada término de un polinomio es un par ordenado (C, E), donde C es coeficiente tipo real y E es el exponente tipo natural. Dominios: Números naturales Número reales Polinomios Boleanos • Un polinomio puede tener uno o más términos. • Puede ser completo o incompleto.

• Un polinomio es una estructura lineal.

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

TDA Polinomio Atributos  [Arreglo] o [lista enlazada]  Otros atributos

Métodos  

 



Métodos constructores Métodos destructores Métodos consultores: obtenerDatos Métodos modificadores: ponerDatos Métodos propios

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

TDA Polinomio Métodos propios sumar(polinomio p, polinomio q); restar(polinomio p, polinomio q); multiplicar(polinomio p, polinomio q); dividir(polinomio p, polinomio q, polinomio resto); calcularRaices(real inferior, real superior); copiar(); anular(); grado() terminos(); evaluar(real x); derivar(); integrar();

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Nivel de implementación 1) Implementación estática (arreglos) •

Forma 1. Implementación con arreglos del polinomio completo

•

Forma 2. Implementación con arreglos solo términos presentes

•

Forma 3. Implementación con arreglos con un subtipo registro o clase.

2) Implementación dinámica (listas enlazadas) •

Cada término del polinomio es un nodo de la lista enlazada.

•

La asignación de espacio de memoria es dinámica.

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Implementacion estática (1) Forma 1. Con arreglos del polinomio completo De cada término del polinomio completo en orden inverso, solo se almacena el coeficiente.

Ejemplo Pn(x) = 3x124 + 4x11 - 8x3 + 6x – 9 -9

6

0

-8

…

4

…

3

0

1

2

3

...

11

...

124

El índice representa el exponente.

Se requieren n elementos. Para el ejemplo 125 elementos. Si el polinomio no es completo, los términos faltantes se almacenaran como ceros.

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Implementacion estática (2) Forma 2. Con arreglos solo términos presentes Solo se almacenan los términos presentes del polinomio, los pares (coef, exp).

Ejemplo Pn(x) = 3x124 + 4x11 - 8x3 + 6x – 9 3

124

4

11

-8

3

6

1

-9

0

0

1

2

3

4

5

6

7

8

9

Se requieren solo 2t elementos (t: nro. terminos). Para el ejemplo, 10 elementos de tipo real. En este caso, el arreglo no contiene ceros porque solo almacena los terminos presentes del polinomio.

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Implementacion estática (3) Forma 3. Con arreglos usando un registro o clase. Cada posición del arreglo almacena un término en forma de “registro o clase” con dos campos: [coeficiente; exponente]

Ejemplo Pn(x) = 3x124 + 4x11 - 8x3 + 6x – 9 [3; 124]

[4; 11]

[-8; 3]

[6; 1]

[-9; 0]

0

1

2

3

4

Se requieren solo t elementos (t: nro. terminos). Para el ejemplo 5 elementos de tipo registro. En este caso, el arreglo no contiene ceros porque solo almacena terminos presentes del polinomio

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Implementacion “Forma 2” Para la estructura de la forma 2, se debe definir una clase polinomio, utilizando un vector de términos.

Para el polinomio: Pn(x) = 3x124 + 4x11 - 8x3 + 6x – 9

Prof. Rodolfo Arana Gonzales

Clase Polinomio

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Programa “Forma 2” en C++

class Polinomio { private: float p[10000]; // vector de terminos del polinomio int grado; // grado del polinomio int nTerm; // numero de términos public: // metodos constructores y destructores Polinomio() {ind=0;} // Constructor // metodos modificadores void setTerm(float coef, int exp); // metodos consultores void getTerm(int i, float &coef, int &exp); int getGrado(); int getNumTerm(); // metodos propios o manipuladores Polinomio sumar(Polinomio P, Polinomio Q); Polinomio derivar(); }

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Implementacion “Forma 3” Para la estructura de la forma 3, se deben definir dos clases: la clase término y la clase polinomio, utilizando un vector de términos. Clase Polinomio Clase Termino

(Programa para la forma 3, desarrollado en lenguaje C++.) Ver programa

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Implementación dinámica 2) Implementación dinámica (listas enlazadas) Cada término del polinomio es un nodo de una lista enlazada. La asignación de espacio de memoria para cada nodo es realizada dinámicamente. Nodo

Coef, exp Lista de nodos

Prof. Rodolfo Arana Gonzales

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE TECNOLOGIA – UNIDAD DE POSTGRADO

Prof. Rodolfo Arana Gonzales