apostila

o seu respectivo grau (ni). As outras in-
formac¸o\u2dces sa\u2dco os ni coeficientes (ai0 , ai1 , ..., ain);
Exemplo:
P (x) = 8.1\u2212 3.4x+ x2 =\u21d2 2 8.1 -3.4 1.0
\u2022 A seque\u2c6ncia de polino\u2c6mios se encerra quando for fornecido um polino\u2c6mio
de grau zero;
\u2022 Apo´s a leitura de todos os polino\u2c6mios, o programa deve ler uma seque\u2c6ncia
de nu´meros reais x. Para cada nu´mero real lido, o programa deve imprimir
o resultado de Pi(x), para todos os polino\u2c6mios lidos anteriormente (i =
1, 2, ..., k);
\u2022 A seque\u2c6ncia de nu´meros reais se encerra quando for lido o nu´mero 0.0, para
o qual na\u2dco se deve calcular os valores de Pi(x).
Exemplo:
Entrada:
2 -1.0 0.0 1.0
3 1.0 2.0 0.0 -1.0
0
4.5
1.0
0.0
Sa\u131´da:
P_1(2.0) = 3.0
P_2(2.0) = -3.0
P_1(1.0) = 0.0
P_2(1.0) = 2.0
33. Fac¸a um programa para:
\u2022 ler um inteiro N e uma matriz quadrada de ordem N contendo apenas 0\u2019s
e 1\u2019s.
10.2. MATRIZES 207
\u2022 encontrar a maior submatriz quadrada da matriz de entrada que conte´m
apenas 1\u2019s.
\u2022 imprimir as coordenadas dos cantos superior esquerdo e inferior direito da
submatriz encontrada no item anterior. Havendo mais de uma submatriz
ma´xima, imprimir as coordenadas de qualquer uma delas.
Exemplo: Considere a seguinte matriz quadrada de ordem 6:
1 2 3 4 5 6
1 0 1 0 1 1 1
2 0 1 1 1 1 0
3 0 1 1 1 0 1
4 1 1 1 1 0 1
5 0 0 1 0 1 0
6 0 1 0 1 0 1
A t´\u131tulo de ilustrac¸a\u2dco, esta matriz tem:
\u2022 22 submatrizes quadradas de ordem 1 que conte´m apenas 1\u2019s;
\u2022 5 submatrizes quadradas de ordem 2 que conte´m apenas 1\u2019s. Por exemplo,
para duas delas: uma e´ dada pelas coordenadas (1,4) e (2,5) e outra pelas
coordenadas (2,2) e (3,3);
\u2022 1 submatriz quadrada de ordem 3 que conte´m apenas 1\u2019s, as coordenadas
sa\u2dco (2,2) e (4,4).
Como a maior submatriz quadrada que conte´m apenas 1\u2019s e´ a de ordem 3, enta\u2dco
a sa´\u131da do programa deve imprimir, para este exemplo, as coordenadas (2,2) e
(4,4).
34. Escreva um programa que, dado um tabuleiro e uma lista de sub-partes retangu-
lares do tabuleiro, retorna o nu´mero de posic¸o\u2dces que na\u2dco pertencem a nenhuma
sub-parte. Quando uma posic¸a\u2dco na\u2dco pertence a nenhuma sub-parte dizemos que
ela esta´ perdida.
Entrada
A entrada consiste de uma se´rie de conjuntos de teste.
Um conjunto de teste comec¸a com uma linha com tre\u2c6s nu´meros W , H e N ,
indicando, respectivamente, a largura e a altura do tabuleiro e o nu´mero de sub-
partes deste. Estes valores satisfazem as seguintes restric¸o\u2dces: 1 \u2264 W , H \u2264 500
e 0 \u2264 N \u2264 99.
208 CAPI´TULO 10. ESTRUTURAS DE DADOS
Seguem N linhas, compostas de quatro inteiros X1, Y1, X2 e Y2, tais que (X1, Y1)
e (X2, Y2) sa\u2dco as posic¸o\u2dces de dois cantos opostos de uma sub-parte. Estes valores
satisfazem as seguintes restric¸o\u2dces: 1 \u2264 X1, X2 \u2264 W e 1 \u2264 Y1, Y2 \u2264 H.
O fim da entrada acontece quando W = H = N = 0. Esta u´ltima entrada na\u2dco
deve ser considerada como um conjunto de teste.
Sa´\u131da
O programa deve imprimir um resultado por linha, seguindo o formato descrito
no exemplo de sa´\u131da.
Exemplo
Entrada:
1 1 1
1 1 1 1 {fim do primeiro conjunto de testes}
2 2 2
1 1 1 2
1 1 2 1 {fim do segundo conjunto de testes }
493 182 3
349 148 363 146
241 123 443 147
303 124 293 17 {fim do terceiro conjunto de testes}
0 0 0 {fim do conjunto de testes}
Sa\u131´da
N~ao ha´ posic¸~oes perdidas.
Existe uma posic¸~ao perdida.
Existem 83470 posic¸~oes perdidas.
10.3. REGISTROS 209
10.3 Registros
Ate´ agora vimos, como estruturas de dados, apenas vetores e matrizes. Estas estru-
turas sa\u2dco ditas homoge\u2c6neas, no sentido que as diversas posic¸o\u2dces de memo´ria alocadas
sa\u2dco sempre do mesmo tipo.
Para completarmos nosso estudo ba´sico de algoritmos, resta ainda introduzir a
noc¸a\u2dco de registros, que sa\u2dco estruturas heteroge\u2c6nas, isto e´, pode-se alocar va´rias posic¸o\u2dces
de memo´ria cada uma delas de um tipo potencialmente diferente.
10.3.1 Introduc¸a\u2dco aos registros
Assim como em um vetor ou em uma matriz, pode-se acessar diversas posic¸o\u2dces de
memo´ria com um u´nico nome da varia´vel, o que e´ diferente e´ que com um registro
podemos misturar diversos tipos diferentes.
Por exemplo, suponhamos que seja necessa´rio implementar um cadastro de um
cliente em um banco. Normalmente, este cadastro conte´m: nome do cliente, telefone,
enderec¸o, sexo, idade, RG e CPF. Usando-se um registro, podemos agrupar todos os
dados diferentes em uma so´ varia´vel. Por exemplo, em Pascal podemos declarar tal
varia´vel assim:
var r : record
nome: string [50 ] ;
fone : longint ;
endereco : string ;
sexo : char;
idade , rg , cpf : integer ;
end;
Cada linguagem de programac¸a\u2dco tem sua sintaxe pro´pria para a declarac¸a\u2dco e acesso
aos dados. Nos vetores e matrizes, o acesso e´ feito usando-se o nome da varia´vel e um
\u131´ndice (ou um par no caso das matrizes). Para os registros, em Pascal, usa-se o nome
da varia´vel, um ponto, e o nome do campo, que e´ escolhido pelo programador.
Por exemplo, e´ va´lido em Pascal a seguinte seque\u2c6ncia de comandos:
r .nome:= \u2019Fulano de Tal\u2019 ;
r . fone:= 32145678;
r . endereco:= \u2019Rua dos bobos, no 0\u2019 ;
r . sexo:= \u2019M\u2019 ;
r . idade:= 75;
r . rg:= 92346539;
r . cpf:= 11122233344;
Tambe´m seria va´lido ler a partir do teclado da seguinte maneira:
read (r .nome) ;
read (r . fone) ;
read (r . endereco) ;
read (r . sexo) ;
read (r . idade) ;
read (r . rg) ;
read (r . cpf) ;
210 CAPI´TULO 10. ESTRUTURAS DE DADOS
Contudo, assim como se da´ para o tipo array, para se passar um para\u2c6metro de
procedimento ou func¸a\u2dco em Pascal e´ necessa´rio antes a declarac¸a\u2dco de um novo tipo,
que poderia ser assim:
type cliente = record
nome: string [50 ] ;
fone : longint ;
endereco : string ;
sexo : char;
idade : integer ;
rg : longint ;
cpf : qword;
end;
var r : cliente ;
Na verdade a linguagem Pascal permite uma facilidade para se economizar alguma
digitac¸a\u2dco atrave´s do comando with. A figura 10.59 ilustra uma forma de se imprimir
todo o conteu´do de um registro usando-se um procedimento. O comando with pode
ser usado para leitura ou atribuic¸a\u2dco tambe´m.
procedure imprime reg (r : cliente ) ;
begin
with r do
begin
writeln (nome) ;
writeln (fone) ;
writeln (endereco) ;
writeln (sexo) ;
writeln (idade) ;
writeln (rg) ;
writeln (cpf) ;
end;
end;
Figura 10.59: Imprimindo registros.
10.3.2 Vetores de registros
O leitor pode ter observado ou pensado: um registro na\u2dco faz um arquiva\u2dco. . .
De fato, normalmente e´ mais comum ver os registros integrados a outras estrututas,
tais como vetores, matrizes ou arquivos em disco11
Considerando ainda o exemplo do cliente do banco, e´ natural imaginar que o banco
tem muitos clientes. Claro, se tiver um so´, melhor fechar as portas. Uma maneira
ainda um pouco preca´ria de se manipular muitos clientes e´ usando a estrutura de
vetores em combinac¸a\u2dco com a de registros.
A t´\u131tulo de exemplo, consideremos enta\u2dco as seguintes definic¸o\u2dces:
11O tipo file esta´ fora do escopo desta disciplina no primeiro semestre de 2009.
10.3. REGISTROS 211
const MAX= 10000;
type cliente = record
nome: string [50 ] ;
fone : longint ;
endereco : string ;
sexo : char;
idade : integer ;
rg : longint ;
cpf : qword;
end;
bd = array [ 1 . .MAX] of cliente ;
var r : cliente ;
v: bd;
tam v: integer ;
Isto e´, temos um vetor de tam v clientes!
Vamos imaginar que o banco e´ novo na prac¸a e que e´ preciso criar o banco de dados
contendo os clientes. Podemos usar o procedimento que e´ mostrado na figura 10.60.
procedure ler cl iente (var r : cliente ) ;
begin
with r do
begin
readln (nome) ;
readln (fone) ;
readln (endereco) ;
readln (sexo) ;
readln (idade) ;
readln (rg) ;
readln (cpf) ;
end;
end;
procedure carregar todos clientes (var v: bd; var tam v: integer) ;
begin
readln (tam v) ;
for i := 1 to tam v do
ler cl iente (v[ i ]