lista03 Algoritmos

Prévia do material em texto

1
ALGORITMOS E PROGRAMAC¸A˜O COMPUTACIONAL
Lista 03 - Vetores e Matrizes
1. A matriz identidade e´ uma matriz diagonal, cuja func¸a˜o e´ de ser o elemento neutro
na multiplicac¸a˜o de matrizes. E´ denotada por In (onde n e´ a ordem da matriz), ou
simplesmente por I. Na matriz identidade, os elementos da diagonal principal teˆm
valor 1, e os demais elementos da matriz sa˜o zero, ou seja,
I = (ij,k)n
ij,k =
{
1 se j = k
0 se j 6= k
Escreva um programa em C que leia um inteiro na˜o-negativo n (a ordem da matriz
identidade) e imprima a matriz identidade.
Exemplo:
Digite a ordem da matriz identidade: 3
Matriz identidade de ordem 3:
1 0 0
0 1 0
0 0 1
2. Para encontrar a raiz de um polinoˆmio p(x) = a0+a1x+ . . .+anx
n (n ≥ 2), pode-
se utilizar o me´todo de Newton-Raphson que consiste em refinar uma aproximac¸a˜o
inicial x0 dessa raiz atrave´s da expressa˜o:
xn+1 = xn − p(xn)
p′(xx)
, n = 0, 1, 2, . . .
onde p′(x) e´ a derivada primeira do polinoˆmio p(x).
Geralmente, o refinamento do ”chute”inicial repete-se ate´ que |xn+1 − xn| < �, ou
ate´ que m iterac¸o˜es tenham sido executadas.
Considere as seguintes definic¸o˜es de constantes:
#define MAX 100 /*dimens~ao ma´xima do vetor coeficientes*/
#define EPS 0.0001 /*precis~ao da estimativa da raiz*/
#define ITER 1000 /*nu´mero ma´ximo de iterac¸~oes*/
(a) Escreva uma func¸a˜o de proto´tipo:
2
double polinomio(double a[], double x, int n);
que recebe um vetor de coeficientes a e retorna o valor do polinoˆmio de grau n em x.
(b) Escreva uma func¸a˜o de proto´tipo:
double derivada(double a[], double x, int n);
que recebe um vetor de coeficientes a e retorna o valor da derivada de um polinoˆmio
de grau n em x.
(c) Escreva um programa que leˆ um inteiro n ≥ 2 que representa o grau de um
polinoˆmio, uma lista de n+ 1 nu´meros reais a0, . . . , an+1 que representam os coefici-
entes do polinoˆmio, um real x0 que representa o ”chute”incial da raiz do polinoˆmio,
e imprime na tela as estimativas das ra´ızes obtidas pelo me´todo de Newton-Raphson
e os erros cometidos em cada iterac¸a˜o (ver exemplo abaixo). Voceˆ deve utilizar a
func¸a˜o polinomio, do item (a), e a func¸a˜o derivada, do item (b). Se desejar, voceˆ
pode usar a func¸a˜o pow(base, expoente), que retorna o valor de uma determinada
base elevado a um determinado expoente, e a func¸a˜o fabs(x), que retorna o valor
absoluto de um nu´mero x, ambas presentes no header math.h.
Exemplo de Sa´ıda 1 (a equac¸a˜o possui duas ra´ızes reais):
Digite o grau do polinomio: 2
Digite os coeficientes do polinomio: 6 -5 1
Digite um valor inicial arbitrario para a raiz: 1
Iter. No. Estimativa raiz erro
01 1.50000 0.50000
02 1.71429 0.21429
...
20 1.99985 0.00008
Exemplo de Sa´ıda 2 (a equac¸a˜o na˜o possui ra´ızes reais):
Digite o grau do polinomio: 2
Digite os coeficientes do polinomio: 10 6 10
Digite um valor inicial arbitrario para a raiz: 1
Iter. No. Estimativa raiz erro
...
1001 -0.67021 1.56228
O metodo de Newton-Raphson nao convergiu. Nao encontrou uma solucao para
o polinomio.
3
3. Em a´lgebra linear, uma matriz de Vandermonde e´ uma matriz quadrada em que
os termos de cada coluna esta˜o em progressa˜o geome´trica. Portanto, uma matriz de
Vandermonde de ordem n× n tem a forma geral:
V =

a01 a
0
2 a
0
3 . . . a
0
n
a11 a
1
2 a
1
3 . . . a
1
n
a21 a
2
2 a
2
3 . . . a
3
n
...
. . .
...
an−11 a
n−1
2 a
n−1
3 . . . a
n−1
n

Os elementos a1, a2, . . . , an sa˜o denominados elementos caracter´ısticos da matriz.
Escreva um programa em C que leia uma sequeˆncia de nu´meros (elementos carac-
ter´ısticos) e imprima a matriz de Vandermonde.
Exemplo:
digite a dimensao da matriz de Vandermonde: 3
digite os elementos caracteristicos: 5 6 7
Matriz de Vandermonde:
1 1 1
5 6 7
25 36 49
4. Em a´lgebra linear, uma matriz tridiagonal e´ uma matriz que possui elementos na˜o-
nulos apenas na diagonal principal e nas duas diagonais vizinhas a ela (imediatamente
abaixo e acima da diagonal principal). Assim, os elementos podem ser definidos por
aij = 0 se |i− j| > 1. Genericamente, uma matriz tridiagonal de ordem n× n pode
ser representada por:
A =

a11 a12 0 0 . . . 0 0
a21 a22 a23 0 . . . 0 0
0 a32 a33 a34 . . . 0 0
...
. . . . . . . . . . . .
...
...
0 0 0 0 . . . an−1n−1 an−1n
0 0 0 0 . . . ann−1 ann

Implementar um programa em C que leia uma sequeˆncia com 3n − 2 elementos e
gere uma matriz tridiagonal de dimenso˜es n× n. Os elementos da sequeˆncia devem
ser colocados na matriz da esquerda para direita e de cima para baixo.
Exemplo:
4
dimensao da matriz tridiagonal: 5
sequencia com 13 elementos: 2 4 6 8 10 12 14 16 18 20 22 24 26
Matriz tridiagonal:
2 4 0 0 0
6 8 10 0 0
0 12 14 16 0
0 0 18 20 22
0 0 0 24 26
5. Dada uma matriz Am×m e uma sequeˆncia com n elementos (n ≤ m), implementar
um programa em C que verifica se a sequeˆncia ocorre ou na˜o em alguma linha da
matriz A. Observac¸o˜es: a) a sequeˆncia esta´ contida na matriz A apenas se os
seus elementos aparecerem na matriz na ordem em que aparecem na sequeˆncia; b)
desconsidere o caso em que o nu´mero de elementos da sequeˆncia ultrapassa o nu´mero
de colunas da matriz A; c) seu programa devera´ tambe´m informar em qual (ou em
quais) linha(s) essa sequeˆncia aparece.
Exemplo 1:
Digite o nu´mero de linhas e colunas da matriz: 3 3
Digite a matriz:
1 2 3
4 5 6
5 6 9
Digite o nu´mero de elementos da sequencia: 2
Digite a sequencia:
5 6
A sequencia digitada aparece nas linhas: 2 3
Exemplo 2:
Digite o nu´mero de linhas e colunas da matriz: 3 3
Digite a matriz:
1 2 3
4 5 6
5 6 9
Digite o nu´mero de elementos da sequencia: 2
Digite a sequencia:
4 6
A sequencia digitada nao aparece em nenhuma linha da matriz
6. Quadrado ma´gico e´ uma matriz quadrada em progressa˜o aritme´tica em que a
soma dos elementos de cada linha, a soma dos elementos de cada coluna e a soma
dos elementos das diagonais principal e secunda´ria sa˜o todas iguais. Exemplos:
5
Exemplo 1:
numero de linhas = 3
numero de colunas = 3
matriz:
2 7 6
9 5 1
4 3 8
A matriz eh um quadrado magico
Soma = 15
Exemplo 2:
numero de linhas = 3
numero de colunas = 3
matriz:
1 0 0
0 1 0
0 0 1
A matriz nao eh um quadrado magico
Escreva um programa em C que leia um inteiro n (1 ≤ n ≤ 100), e uma matriz A de
nu´meros inteiros de dimensa˜o n× n e imprima A matriz eh um quadrado magico
se a matriz A e´ um quadrado ma´gico, ou A matriz nao eh um quadrado magico
caso contra´rio. Voceˆ pode resolver esse exerc´ıcio utilizando func¸o˜es.