ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I717 materiais7.909 seguidores
Pré-visualização50 páginas
do canto superior esquerdo da matriz, no sentido hora´rio, em espiral, a posic¸a\u2dco
seguinte na ordem e´ o inteiro consecutivo da posic¸a\u2dco anterior. Por exemplo, as
matrizes abaixo sa\u2dco incas:
1 2 3 4 1 2 3 4 5
12 13 14 5 16 17 18 19 6
11 16 15 6 15 24 25 20 7
10 9 8 7 14 23 22 21 8
13 12 11 10 9
O programa deve ler do teclado a dimensa\u2dco da matriz (um inteiro N , 1 \u2264
N \u2264 100) e em cada uma das pro´ximas N linhas, os inteiros correspondentes a`s
entradas da matriz naquela linha. A sa´\u131da do programa deve ser \u201cA matriz eh
inca\u201d ou \u201cA matriz nao eh inca\u201d.
204 CAPI´TULO 10. ESTRUTURAS DE DADOS
28. Escreva um programa em Pascal que leia do teclado uma matriz A (N ×M)
de inteiros e imprima uma segunda matriz B de mesma dimenso\u2dces em que cada
elemento B[i, j] seja constitu´\u131do pela soma de todos os 8 elementos vizinhos do
elemento A[i, j], excetuando-se o pro´prio A[i, j].
29. Nesta questa\u2dco voce\u2c6 tera´ que providenciar ligac¸o\u2dces par-a-par entre diversos pontos
distribu´\u131dos ao longo de uma rota qualquer. A entrada de dados consiste de um
conjunto de pares (x, y), 1 \u2264 x, y \u2264MAX, sendo que o u´ltimo par a ser lido e´ o
(0,0), que na\u2dco deve ser processado, apenas indicando final da entrada de dados.
Para cada par (x, y) dado como entrada, voce\u2c6 deve providenciar uma conexa\u2dco
f´\u131sica entre eles. As linhas de uma matriz podem representar a \u201caltura\u201d das
linhas de conexa\u2dco, enquanto que as colunas da matriz podem representar os
pontos (x, y) sendo conectados. Um s´\u131mbolo de \u201c+\u201d pode ser usado para se
representar alterac¸a\u2dco na direc¸a\u2dco de uma conexa\u2dco. O s´\u131mbolo \u201c|\u201d pode ser usado
para representar um trecho de conexa\u2dco na vertical. Finalmente o s´\u131mbolo \u201c-\u201d
pode ser usado para se representar um trecho de conexa\u2dco na direc¸a\u2dco horizontal.
Quando um cruzamento de linhas for inevita´vel, deve-se usar o s´\u131mbolo \u201cx\u201d para
representa´-lo. Considere que na\u2dco existem trechos de conexo\u2dces na diagonal.
Por exemplo, suponha que a entrada e´ dada pelos seguintes pares:
3 5
2 9
0 0
Uma poss´\u131vel sa´\u131da para seu programa seria a impressa\u2dco da seguinte matriz:
4
3
2 +-------------+
1 | +---+ |
1 2 3 4 5 6 7 8 9
Outra poss´\u131vel matriz soluc¸a\u2dco para este problema seria esta:
4
3
2 +---+
1 +-x---x-------+
1 2 3 4 5 6 7 8 9
Note que nesta u´ltima versa\u2dco foi preciso inserir dois cruzamentos.
Ainda como exemplo, se o par (6,8) tambe´m fosse dado como entrada no exemplo
anterior, a sa´\u131da do programa poderia ser assim exibida:
10.2. MATRIZES 205
4
3 +---+
2 +-------x---x-+
1 | +---+ | | |
1 2 3 4 5 6 7 8 9
Voce\u2c6 deve implementar um programa em Pascal que seja capaz de ler uma
seque\u2c6ncia de pares terminada em (0, 0) (como no exemplo acima) e que imprima
o desenho das conexo\u2dces como sa´\u131da, tambe´m conforme o diagrama acima.
30. Modifique o programa anterior com o objetivo de minizar o nu´mero de cruza-
mentos da matriz gerada como soluc¸a\u2dco do problema anterior. Assim, a matriz
ideal para ser dada como resposta do u´ltimo exemplo seria a seguinte:
4
3
2 +-------------+
1 | +---+ +---+ |
1 2 3 4 5 6 7 8 9
31. Considere o seguinte programa:
program prova final ;
CONSTMAX=100;
TYPE matriz = array [ 1 . .MAX,1 . .MAX] of integer ;
VAR n lin , n col : integer ; (\u2217 dimensoes da matriz \u2217)
m: matriz ; (\u2217 matriz \u2217)
(\u2217 espaco reservado para os procedimentos \u2217)
begin
read (n lin , n col ) ;
le matriz (m, n lin , n col ) ;
acha maior sequencia (m, n lin , n col , l in i , c ini , l fim , c fim) ;
writeln (\u2019A maior sequencia de numeros repetidos na matriz \u2019) ;
writeln (\u2019inicia na coordenada \u2019 , l in i , c ini ) ;
writeln (\u2019 e termina na coordenada \u2019 , l fim , c fim) ;
end.
Implemente os procedimentos indicados para que o programa leia uma matriz
de inteiros e imprima as coordenadas de in´\u131cio e te´rmino da maior seque\u2c6ncia
de nu´meros repetidos da matriz. Esta seque\u2c6ncia pode estar tanto nas linhas
quanto nas colunas. No caso de existir mais de uma seque\u2c6ncia repetida de
mesmo tamanho, voce\u2c6 pode imprimir as coordenadas de qualquer uma delas,
desde que imprima as de uma so´.
206 CAPI´TULO 10. ESTRUTURAS DE DADOS
Exemplo 1:
Entrada: Sa\u131´da
4 3 1 2
1 2 3 3 2
2 2 1
3 2 5
Exemplo 2:
Entrada: Sa\u131´da
4 5 2 2
1 2 3 1 2 2 4
1 2 2 2 3
2 3 4 5 6
8 7 6 4 2
32. Fac¸a um programa para:
\u2022 ler uma seque\u2c6ncia de polino\u2c6mios Pi(x) = ai0 +ai1x+ai2x2 + ...+ainxn, i =
1, 2, ..., k;
\u2022 A leitura deve considerar que cada linha de entrada conte´m um polino\u2c6mio
Pi. A primeira informac¸a\u2dco e´ 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