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 ]