apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.968 seguidores
Pré-visualização50 páginas
de n compat´ıveis com os tipos de dados definidos (integer).

Polinoˆmios

Nesta sec¸a˜o vamos mostrar como representar e fazer ca´lculos com polinoˆmios repre-
sentados como vetores.

Para uma sucessa˜o de termos a0, ..., an ∈ R, podemos para este curso definir um
polinoˆmio de grau n como sendo uma func¸a˜o que possui a seguinte forma:

P (x) = anx
n + an−1xn−1 + . . .+ a1x+ a0

Vamos considerar ao longo desta sec¸a˜o que ∀k > n, enta˜o ak = 0. Tambe´m
consideramos que an 6= 0 para um polinoˆmio de grau n.

Do ponto de vista computacional, uma poss´ıvel representac¸a˜o para um polinoˆmio
e´ um vetor de n+1 elementos cujos conteu´dos sa˜o os coeficientes reais dos respectivos
monoˆmios. Consideremos enta˜o o tipo abaixo, podemos exemplificar alguns casos:

type polinomio = array [ 0 . .max] of real ;

160 CAPI´TULO 10. ESTRUTURAS DE DADOS

• P (x) = 5− 2x+ x2:

0 1 2
5 -2 1

• P (x) = 7− 2x2 + 8x3 − 2x7

0 1 2 3 4 5 6 7
7 0 -2 8 0 0 0 -2

No restante desta sec¸a˜o iremos mostrar algoritmos que realizam operac¸o˜es costu-
meiras sobre polinoˆmios. A primeira e´ calcular o valor de um polinoˆmio em um dado
ponto x ∈ R. Por exemplo, se P (x) = 5− 2x + x2 enta˜o, P (1) = 5− 2× 1 + 12 = 4.
A func¸a˜o em Pascal que implementa este ca´lculo esta´ apresentado na figura 10.33.

function valor no ponto (var p: polinomio ; n: integer ; x: real) : real ;
var i : integer ;

soma, pot x : real ;

begin
soma:= 0;
pot x:= 1;
for i := 0 to n do (∗ basta usar a tecnica do acumulador ∗)
begin

soma:= soma + p[ i ] ∗ pot x ;
pot x:= pot x ∗ x; (∗ controlando a potencia de x ∗)

end;
valor no ponto:= soma;

end;

Figura 10.33: Calcula o valor de P (x) para um dado x ∈ R.

O pro´ximo algoritmo interessante e´ o ca´lculo do polinoˆmio derivada de um po-
linoˆmio P. Seja P ′(x) a derivada de P (x) assim definido:

P ′(x) = nanxn−1 + (n− 1)an−1xn−2 + . . .+ 2a2x+ a1
O programa que implementa este ca´lculo esta´ na figura 10.34.
Por outro lado, para calcular o valor no ponto de uma derivada de um polinoˆmio,

na˜o e´ necessa´rio que se calcule previamente um vetor auxiliar contendo a derivada. Isto
pode ser feito diretamente usando-se o polinoˆmio P , bastando trabalhar corretamente
os ı´ndices do vetor, conforme mostrado na figura 10.35.

Os pro´ximos problemas va˜o nos permitir trabalhar um pouco com os ı´ndices do
vetor. O primeiro problema e´ a soma de polinoˆmios. O segundo e´ a multiplicac¸a˜o.
Antes mostraremos a definic¸a˜o matema´tica para estes conceitos.

Sejam dois polinoˆmios P e Q assim definidos, supondo que n >= m:

10.1. VETORES 161

procedure derivada (var p: polinomio ; n: integer
var q: polinomio ; var m: integer) ;

var i : integer ;

begin
for i := 1 to n do

q[ i−1]:= i ∗ p[ i ] ; (∗ diretamente da definicao de derivada ∗)
m:= n − 1;

end;

Figura 10.34: Calcula o polinoˆmio derivada de P (x).

function derivada no ponto (var p: polinomio ; n: integer ; x: real) : real ;
var i : integer ;

soma, pot x : real ;
begin

soma:= 0;
pot x:= 1;
for i := 1 to n do
begin

soma:= soma + i ∗ p[ i ] ∗ pot x ;
pot x:= pot x ∗ x;

end;
derivada no ponto:= soma;

end;

Figura 10.35: Calcula o valor de P ′(x) para um dado x ∈ R.

P (x) = anx
n + . . .+ amx

m + . . .+ a1x+ a0

Q(x) = bnx
m + bn−1xm−1 + . . .+ b1x+ b0

Enta˜o o polinoˆmio soma de P e Q, denotado P +Q e´ assim definido:

(P +Q)(x) = anx
n + . . .+ am+1x

m+1 + (am + bm)x
m + . . .+ (a1 + b1)x+ (a0 + b0)

Basicamente e´ a mesma operac¸a˜o de soma de vetores estudada neste cap´ıtulo,
embora naquele caso exigimos que os tamanhos dos vetores fossem iguais. No caso
de polinoˆmios os vetores podem ter tamanhos diferentes desde que se assuma que
os coeficientes que faltam no polinoˆmio de maior graus sa˜o nulos. A implementac¸a˜o
deste processo esta´ na figura 10.36.

Considerando os mesmos polinoˆmios P e Q acima definidos, o produto de P por
Q, denotado PQ e´ assim definida:

(PQ)(x) = (an+mb0 + . . .+ anbm + . . .+ a0bn+m)x
n+m + . . .+

(akb0 + ak−1b1 + . . .+ a0bk)xk + . . .+ (a1b0 + a0b1)x+ (a0b0)

162 CAPI´TULO 10. ESTRUTURAS DE DADOS

procedure soma (var p: polinomio ; n: integer ; var q: polinomio ; m: integer ;
var r : polinomio ; var grau r : integer) ;

var i , menor grau: integer ;

begin
if n > m then (∗ primeiro copia a parte que sobra ∗)
begin

menor grau:= m
grau r:= n;
for i := m+1 do n do

r [ i ]:= p[ i ] ;
end else
begin

menor grau:=n;
grau r:= m;
for i := n+1 to m do

r [ i ]:= q[ i ] ;
end
for i := 0 to menor grau do (∗ este for eh o mesmo da soma de vetores ∗)

r [ i ]:= p[ i ] + q[ i ] ;
end;

Figura 10.36: Calcula a soma de P (x) com Q(x).

A operac¸a˜o matema´tica exige que sejam feitas todas as multiplicac¸o˜es e posterior
agrupamento dos monoˆmios de mesmo grau, somando-se os coeficientes, para cada
monoˆmio.

O programa apresentado na figura 10.37 implementa os ca´lculos para obtenc¸a˜o do
polinoˆmio produto de P por Q. O programa realiza os ca´lculos para cada monoˆmio
a` medida em que os ı´ndices dos dois comandos for variam, o que e´ um uso especial
da te´cnica dos acumuladores, embora os acu´mulos na˜o sejam simultaˆneos para cada
monoˆmio do resultado final da operac¸a˜o, eles sa˜o feitos aos poucos. Para isto e´ preciso
zerar o vetor antes de comec¸ar.

procedure produto (var p: polinomio ; n: integer ;
var q: polinomio ; m: integer ;
var r : polinomio ; var grau r : integer) ;

var i , j : integer ;

begin
for i := 0 to n+m do

r [ i ]:= 0;
for i := 0 to n do

for j:= 0 to m do
r [ i+j ]:= r [ i+j ] + p[ i ]∗q[ j ] ;

grau r:= n+m;
end;

Figura 10.37: Calcula o produto de P (x) com Q(x).

10.1. VETORES 163

10.1.6 Exerc´ıcios

1. Fac¸a um programa que leia e armazene em um vetor uma sequeˆncia de inteiros.
Em seguida o programa deve ler uma sequeˆncia de inteiros informados pelo
usua´rio e, para cada um deles, dizer se ele pertence ou na˜o ao vetor armazenado
previamente.

2. Fac¸a um programa que leia duas sequeˆncias de n inteiros em dois vetores dis-
tintos, digamos, v e w e verifique se os dois vetores sa˜o ideˆnticos.

3. Fac¸a um programa em que leia dois vetores de nu´meros reais e descubra se um
deles e´ permutac¸a˜o do outro, isto e´, se eles tem os mesmos elementos, ainda
que em ordem diferente. A quantidade de elementos lidos em cada vetor e´ no
ma´ximo 100, e cada sequeˆncia termina quando o valor 0 e´ digitado. Por exemplo:

[2, 2, 0, 3, 4] e [2, 2, 0, 3, 4]: sim.

[2, 2, 0, 3, 4] e [4, 3, 2, 0, 2]: sim.

[2, 2, 0, 3, 4] e [4, 3, 4, 0, 2]: na˜o.

[3, 0, 5] e [3, 0, 5, 3]: na˜o.

Implemente treˆs verso˜es deste problema:

• ordenando os vetores para em seguida compara´-los;
• sem ordenar os vetores;
• crie uma func¸a˜o que retorna 0 se x na˜o pertence a v e caso contra´rio retorna

o ı´ndice do vetor onde x se encontra. Use esta func¸a˜o para resolver este
problema.

4. Fac¸a um programa que leia duas sequeˆncias de inteiros, na˜o necessariamente
contendo a mesma quantidade de nu´meros. Seu programa devera´:

• dizer se a segunda sequeˆncia esta´ contida na primeira. Exemplo:
v1: 7 3 2 3 2 6 4 7

v2: 3 2 6

Saı´da: sim

• constrir um terceiro vetor, sem destruir os originais, que e´ a concatenac¸a˜o
do primeiro com o segundo;

v1: 7 3 2 6

v2: 5 1 8 4 9

Saı´da: 1 2 3 4 5 6 7 8 9

• ordena´-los, e em seguida imprimir todos os nu´meros ordenados em ordem
crescente. Exemplo:

v1: 7 3 2 6

v2: 5 1 8 4 9

Saı´da: 1 2 3 4 5 6 7 8 9

164 CAPI´TULO 10. ESTRUTURAS DE DADOS

5. Crie uma func¸a˜o em que receba um vetor de inteiros de tamanho n e devolva o
valor true se o vetor estiver ordenado e false em caso contra´rio.

6. Aproveitando as soluc¸o˜es dos problemas anteriores, escreva um programa em
que leia dois vetores de inteiros v e w, de dimenso˜es m e n respectivamente,
verifique se eles esta˜o ordenados, ordene-os em