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 ]