apostila

grau n \u2265 2. Uma
poss´\u131vel maneira de calcular uma raiz do polino\u2c6mio e´ pelo \u201cme´todo de Newton\u201d.
Este me´todo consiste em se fornecer uma aproximac¸a\u2dco inicial para a raiz, isto
e´, um valor que na\u2dco e´ a raiz exata, mas e´ um valor pro´ximo. Assim, se x0 e´
esta aproximac¸a\u2dco inicial, p(x0) na\u2dco e´ zero mas espera-se que seja pro´ximo de
zero. A obtenc¸a\u2dco da raiz pelo me´todo de Newton e´ feita pelo refinamento desta
soluc¸a\u2dco inicial, isto e´, pela tentativa de minimizar o erro cometido. Isto e´ feito
pela expressa\u2dco seguinte:
xn+1 = xn \u2212 p(xn)
p\u2032(xn) ,
n = 0, 1, 2, . . ., e onde p\u2032(x) e´ a primeira derivada de p(x). Usualmente, repete-se
este refinamento ate´ que |xn+1 \u2212 xn| < \ufffd, \ufffd > 0, ou ate´ que m iterac¸o\u2dces tenham
sido executadas.
Construa um programa em que receba como dados de entrada um polino\u2c6mio
p(x) = a0 + a1x + a2x
2 + . . . + anx
n e uma aproximac¸a\u2dco inicial x0 da raiz de
p(x), \ufffd > 0 e o nu´mero ma´ximo de iterac¸o\u2dces, e calcule uma aproximac¸a\u2dco da raiz
de p(x) pelo me´todo de Newton. Utilize obrigatoriamente um procedimento que
receba como para\u2c6metro um polino\u2c6mio p(x) (incluindo a informac¸a\u2dco sobre o grau
do polino\u2c6mio) e que calcule e retorne a func¸a\u2dco derivada p\u2032(x). Utilize tambe´m
uma func¸a\u2dco que receba como para\u2c6metros um polino\u2c6mio p(x) e um valor real x
e retorne o valor do polino\u2c6mio no ponto x, isto e´ p(x). Use esta func¸a\u2dco para
calcular, a cada iterac¸a\u2dco do me´todo de Newton, os valores de p(xn) e de p\u2032(xn).
23. Fac¸a um programa em que leia uma seque\u2c6ncia de 10 letras (caracteres de A a
Z), as armazene em um vetor de 10 posic¸o\u2dces e imprima a lista de letras repetidas
no vetor. Sendo assim, para os dados: A J G A D F G A A, a sa´\u131da deve ser:
A G.
24. Escreva o programa da busca bina´ria de um valor x num vetor de inteiros que,
ao inve´s de achar a primeira ocorre\u2c6ncia do valor na lista, identifique e imprima
168 CAPI´TULO 10. ESTRUTURAS DE DADOS
o menor \u131´ndice do vetor no qual o valor ocorra.
25. Escreva um programa em que leia uma seque\u2c6ncia de co´digo de operac¸a\u2dco e valor,
onde o co´digo de operac¸a\u2dco e´ um inteiro com os seguintes valores:
\u2022 0 (zero): fim
\u2022 1 (um): inserc¸a\u2dco
\u2022 2 (dois): remoc¸a\u2dco
O valor lido e´ um real que deve ser inserido em um vetor (caso a operac¸a\u2dco seja 1),
ou removido do vetor (caso a operac¸a\u2dco seja 2). As inserc¸o\u2dces no vetor devem ser
realizadas de forma que o vetor esteja sempre ordenado. No final do programa
o vetor resultante deve ser impresso.
Detalhamento:
\u2022 a quantidade ma´xima de valores que pode ser inserida e´ 100;
\u2022 se a quantidade ma´xima for ultrapassada o programa deve dar uma men-
sagem de erro;
\u2022 se for requisitada a remoc¸a\u2dco de um nu´mero na\u2dco existente o programa deve
dar uma mensagem de erro;
\u2022 se o co´digo de operac¸a\u2dco for inva´lido o programa deve continuar lendo um
novo co´digo ate´ que ele seja 0 (zero), 1 (um) ou 2 (dois).
Exemplo de execuc¸a\u2dco:
Entre com operacao (0=fim, 1=insercao, 2=remocao): 1
Valor: 45.3
Entre com operacao (0=fim, 1=insercao, 2=remocao): 1
Valor: 34.3
Entre com operacao (0=fim, 1=insercao, 2=remocao): 1
Valor: 40.8
Entre com operacao (0=fim, 1=insercao, 2=remocao): 2
Valor: 34.3
Entre com operacao (0=fim, 1=insercao, 2=remocao): 0
Vetor resultante
40.8 45.3
1 2 3 4 5 6
in´\u131cio
45.3 apo´s inserc¸a\u2dco de 45.3
34.3 45.3 apo´s inserc¸a\u2dco de 34.3
34.3 40.8 45.3 apo´s inserc¸a\u2dco de 40.8
40.8 45.3 apo´s remoc¸a\u2dco de 34.3
10.1. VETORES 169
26. Escreva um programa que leia duas seque\u2c6ncias de caracteres e verifica se a
segunda seque\u2c6ncia e´ subpalavra da primeira. Por exemplo, todo e´ subpalavra
de metodo e ar e´ subpalavra de farmacia. Pore´m, todo na\u2dco e´ subpalavra de
todavia. A leitura das seque\u2c6ncias deve ser feita caracter por caracter e o final
de cada seque\u2c6ncia e´ sinalizada pelo caracter \u2019.\u2019. Se a segunda seque\u2c6ncia e´ uma
subpalavra, a sa´\u131da do programa deve ser a posic¸a\u2dco na qual ela comec¸a. Caso
contra´rio, escrever a mensagem \u201cNao eh subpalavra.\u201d. Observac¸o\u2dces:
\u2022 cada seque\u2c6ncia tem no ma´ximo 80 caracteres.
\u2022 voce\u2c6 na\u2dco pode utilizar func¸o\u2dces de manipulac¸a\u2dco de cadeias de caracteres
existentes no compilador, mas somente as func¸o\u2dces para o tipo char.
Exemplo de execuc¸a\u2dco:
Entre com duas palavras terminadas por ponto:
metodo.todo.
A segunda subpalavra comeca na posicao 3 da primeira.
27. Escreva um programa em que leia uma seque\u2c6ncia de n valores reais (n \u2264 100) e
os insira num vetor. A seque\u2c6ncia termina quando o valor lido for 0. O programa
deve escrever o valor da divisa\u2dco da soma dos valores positivos pela soma dos valores
negativos que esta\u2dco armazenados no vetor. Cuidado com diviso\u2dces por zero.
28. Escreva uma func¸a\u2dco em que substitui em um texto a primeira ocorre\u2c6ncia de uma
palavra por outra. A func¸a\u2dco deve retornar true se a substituic¸a\u2dco for bem sucedida
e false caso a palavra na\u2dco seja encontrada no texto. O texto e as palavras sa\u2dco
representados por vetores do tipo char. Por exemplo:
+---+---+---+---+---+---+---+---+---+---+
texto1 | e | x | e | m | p | r | o | | u | n |
+---+---+---+---+---+---+---+---+---+---+
+---+---+---+---+---+
palavra1 | r | o | | u | n |
+---+---+---+---+---+
+---+---+---+---+---+---+---+
palavra2 | l | o | | d | o | i | s |
+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+---+---+---+---+
texto2 | e | x | e | m | p | l | o | | d | o | i | s |
+---+---+---+---+---+---+---+---+---+---+---+---+
A func¸a\u2dco recebe como para\u2c6metros o texto, a palavra a ser substitu´\u131da e a nova palavra.
No exemplo, texto1 mostra o estado inicial do texto e texto2 o estado do texto apo´s
a substituic¸a\u2dco da palavra1 pela palavra2.
Voce\u2c6 pode usar, caso seja necessa´rio, a func¸a\u2dco:
buscachar(texto, pos, letra);
170 CAPI´TULO 10. ESTRUTURAS DE DADOS
que busca um caractere (letra) a partir de uma determinada posic¸a\u2dco (pos) em um
vetor que conte´m o texto (texto). A func¸a\u2dco buscaletra retorna a posic¸a\u2dco no vetor
texto da primeira ocorre\u2c6ncia de letra, se letra na\u2dco aparece no texto a func¸a\u2dco
retorna -1.
29. Um algoritmo gene´tico e´ um procedimento computacional de busca, inspirado no pro-
cesso biolo´gico de evoluc¸a\u2dco, que otimiza a soluc¸a\u2dco de um problema. O problema e´
modelado por: uma populac¸a\u2dco de indiv´\u131duos que representam poss´\u131veis soluc¸o\u2dces; uma
func¸a\u2dco que avalia a qualidade da soluc¸a\u2dco representada por cada indiv´\u131duo da populac¸a\u2dco
e um conjunto de operadores gene´ticos. Os indiv´\u131duos sa\u2dco dados por seque\u2c6ncias de
genes que representam caracter´\u131sticas da soluc¸a\u2dco do problema. O procedimento con-
siste em aplicar os operadores gene´ticos sobre a populac¸a\u2dco, gerando novos indiv´\u131duos
e selecionar os mais aptos para constituirem uma nova populac¸a\u2dco. Esse processo e´
repetido ate´ que uma soluc¸a\u2dco adequada seja obtida. Dentre os operadores gene´ticos,
o mais importante e´ o de recombinac¸a\u2dco gene´tica (crossover) de dois indiv´\u131duos. Esse
operador corta em duas partes as seque\u2c6ncias de genes de dois indiv´\u131duos pais (pai1
e pai2) e gera dois novos indiv´\u131duos filhos (filho1 e filho2). filho1 e´ dado pela
contatenac¸a\u2dco da primeira parte dos genes de pai1 com a segunda parte de pai2 e
filho2 pela concatenac¸a\u2dco da primeira parte de pai2 com a segunda parte de pai1.
O diagrama abaixo exemplifica a operac¸a\u2dco em indiv´\u131duos representados por vetores
de nu´meros inteiros onde a primeira posic¸a\u2dco conte´m o tamanho do vetor:
corte1
+----+---+---+---#---+---+---+---+---+---+---+---+
pai1 | 11 | 1 | 1 | 1 # 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
+----+---+---+---#---+---+---+---+---+---+---+---+
corte2
+----+---+---+---+---+---#---+---+---+---+---+
pai2 | 10 | 3 | 3 | 3 | 3 | 3 # 4 | 4 | 4 | 4 | 4 |
+----+---+---+---+---+---#---+---+---+---+---+
+----+---+---+---+---+---+---+---+---+
filho1 | 8 | 1 | 1 | 1 | 4 | 4 | 4 | 4 | 4 |
+----+---+---+---+---+---+---+---+---+