apostila

o seu respectivo grau (ni). As outras in-
formac¸o˜es sa˜o os ni coeficientes (ai0 , ai1 , ..., ain);
Exemplo:
P (x) = 8.1− 3.4x+ x2 =⇒ 2 8.1 -3.4 1.0
• A sequeˆncia de polinoˆmios se encerra quando for fornecido um polinoˆmio
de grau zero;
• Apo´s a leitura de todos os polinoˆmios, o programa deve ler uma sequeˆncia
de nu´meros reais x. Para cada nu´mero real lido, o programa deve imprimir
o resultado de Pi(x), para todos os polinoˆmios lidos anteriormente (i =
1, 2, ..., k);
• A sequeˆncia de nu´meros reais se encerra quando for lido o nu´mero 0.0, para
o qual na˜o 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ı´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:
• ler um inteiro N e uma matriz quadrada de ordem N contendo apenas 0’s
e 1’s.
10.2. MATRIZES 207
• encontrar a maior submatriz quadrada da matriz de entrada que conte´m
apenas 1’s.
• 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´ıtulo de ilustrac¸a˜o, esta matriz tem:
• 22 submatrizes quadradas de ordem 1 que conte´m apenas 1’s;
• 5 submatrizes quadradas de ordem 2 que conte´m apenas 1’s. Por exemplo,
para duas delas: uma e´ dada pelas coordenadas (1,4) e (2,5) e outra pelas
coordenadas (2,2) e (3,3);
• 1 submatriz quadrada de ordem 3 que conte´m apenas 1’s, as coordenadas
sa˜o (2,2) e (4,4).
Como a maior submatriz quadrada que conte´m apenas 1’s e´ a de ordem 3, enta˜o
a sa´ıda 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˜es que na˜o pertencem a nenhuma
sub-parte. Quando uma posic¸a˜o na˜o 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ˆs 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˜es: 1 ≤ W , H ≤ 500
e 0 ≤ N ≤ 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˜o as posic¸o˜es de dois cantos opostos de uma sub-parte. Estes valores
satisfazem as seguintes restric¸o˜es: 1 ≤ X1, X2 ≤ W e 1 ≤ Y1, Y2 ≤ H.
O fim da entrada acontece quando W = H = N = 0. Esta u´ltima entrada na˜o
deve ser considerada como um conjunto de teste.
Sa´ıda
O programa deve imprimir um resultado por linha, seguindo o formato descrito
no exemplo de sa´ıda.
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ı´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˜o ditas homogeˆneas, no sentido que as diversas posic¸o˜es de memo´ria alocadas
sa˜o sempre do mesmo tipo.
Para completarmos nosso estudo ba´sico de algoritmos, resta ainda introduzir a
noc¸a˜o de registros, que sa˜o estruturas heterogeˆnas, isto e´, pode-se alocar va´rias posic¸o˜es
de memo´ria cada uma delas de um tipo potencialmente diferente.
10.3.1 Introduc¸a˜o aos registros
Assim como em um vetor ou em uma matriz, pode-se acessar diversas posic¸o˜es 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˜o tem sua sintaxe pro´pria para a declarac¸a˜o e acesso
aos dados. Nos vetores e matrizes, o acesso e´ feito usando-se o nome da varia´vel e um
ı´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ˆncia de comandos:
r .nome:= ’Fulano de Tal’ ;
r . fone:= 32145678;
r . endereco:= ’Rua dos bobos, no 0’ ;
r . sexo:= ’M’ ;
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ˆmetro de
procedimento ou func¸a˜o em Pascal e´ necessa´rio antes a declarac¸a˜o 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˜o 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˜o 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˜o faz um arquiva˜o. . .
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˜o com a de registros.
A t´ıtulo de exemplo, consideremos enta˜o as seguintes definic¸o˜es:
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 ]