apostila

por um vetor com TAM_RODOVIA posic¸o\u2dces;
\u2022 A simulac¸a\u2dco ocorre durante MAX_TEMPO iterac¸o\u2dces;
174 CAPI´TULO 10. ESTRUTURAS DE DADOS
\u2022 Atrave´s da chamada do procedimento
detecta_entrada(VAR tipo, placa, velocidade:INTEGER),
o programador e´ informado sobre a ocorre\u2c6ncia ou na\u2dco da entrada de um ve´\u131culo
na rodovia, bem como o tipo do ve´\u131culo, sua placa e sua respectiva velocidade,
onde:
\u2013 tipo: 0 - nenhuma nova entrada, 1 - entrou automo´vel, 2 - entrou caminha\u2dco;
\u2013 placa: um nu´mero inteiro;
\u2013 velocidade: a velocidade de deslocamento do ve´\u131culo (em posic¸o\u2dces/unidade
de tempo).
\u2022 Ve´\u131culos do tipo automo´vel ocupam uma posic¸a\u2dco da rodovia. Caminho\u2dces ocupam
duas posic¸o\u2dces.
\u2022 Quando ve´\u131culos mais ra´pidos alcanc¸am ve´\u131culos mais lentos, os primeiros devem
andar mais devagar, pois na\u2dco podem ultrapassar.
A cada unidade de tempo em que algum ve´\u131culo sair da rodovia, seu programa deve
imprimir esta unidade de tempo e o nu´mero da placa do ve´\u131culo que saiu.
Exemplo: (TAM_RODOVIA=7, MAX_TEMPO=10)
\u2022 Entrada:
\u2013 t=1: tipo = 2, placa = 35, velocidade = 1
\u2013 t=2: tipo = 0
\u2013 t=3: tipo = 1, placa = 27, velocidade = 4
\u2013 t=4: tipo = 0
\u2013 t=5: tipo = 0
\u2013 t=6: tipo = 1, placa = 16, velocidade = 2
\u2013 t=7: tipo = 0
\u2013 t=8: tipo = 0
\u2013 t=9: tipo = 0
\u2013 t=10: tipo = 0
\u2022 Representac¸a\u2dco gra´fica:
\u2013 t=1: 351 351
\u2013 t=2: 351 351
\u2013 t=3: 274 351 351
\u2013 t=4: 274 351 351
\u2013 t=5: 274 351 351
\u2013 t=6: 162 274 351 351
\u2013 t=7: 162 274 351
\u2013 t=8: 162 274
\u2013 t=9: 162
\u2013 t=10:
\u2022 Sa´\u131da:
10.1. VETORES 175
\u2013 t=8: 35
\u2013 t=9: 27
\u2013 t=10: 16
39. Voce\u2c6 deve incluir no enunciado da questa\u2dco anterior a existe\u2c6ncia de uma pista de
ultrapassagem. Agora, ve´\u131culos mais ra´pidos podem mover-se para a pista de ultra-
passagem ao alcanc¸arem ve´\u131culos mais lentos, desde que na\u2dco haja ningue´m ocupando
aquele trecho de pista. Eles devem retornar a` pista original assim que tiverem com-
pletado a ultrapassagem, retomando a velocidade original. Voce\u2c6 deve escrever apenas
os procedimentos modificados ou novos que levam em conta este novo fato.
Exemplo da nova sa´\u131da para a entrada original:
\u2022 Representac¸a\u2dco gra´fica:
\u2013 t=1:
351 351
\u2013 t=2:
351 351
\u2013 t=3:
274 351 351
\u2013 t=4:
274
351 351
\u2013 t=5:
351 351 274
\u2013 t=6:
162 351 351
\u2013 t=7:
162 351
\u2013 t=8:
162
\u2013 t=9:
162
\u2013 t=10:
\u2022 Sa´\u131da:
\u2013 t=6: 27
\u2013 t=8: 35
\u2013 t=10: 16
40. Mateus, um engenheiro novato, esta´ desenvolvendo uma notac¸a\u2dco posicional original
para representac¸a\u2dco de nu´meros inteiros. Ele chamou esta notac¸a\u2dco de UMC (Um
me´todo curioso). A notac¸a\u2dco UMC usa os mesmos d´\u131gitos da notac¸a\u2dco decimal, isto
e´, de 0 a 9. Para converter um nu´mero A da notac¸a\u2dco UMC para a notac¸a\u2dco decimal
deve-se adicionar K termos, onde K e´ o nu´mero de d´\u131gitos de A (na notac¸a\u2dco UMC). O
176 CAPI´TULO 10. ESTRUTURAS DE DADOS
valor do i-e´simo termo correspondente ao i-e´simo d´\u131gito ai, contando da direita para
a esquerda e´ ai × i!.
Por exemplo, 719UMC e´ equivalente a 5310, pois 7× 3! + 1× 2! + 9× 1! = 53.
Mateus esta´ apenas comec¸ando seus estudos em teoria dos nu´meros e provavelmente
na\u2dco sabe quais as propriedades que um sistema de numerac¸a\u2dco deve ter, mas neste
momento ele esta´ apenas interessado em converter os nu´meros da notac¸a\u2dco UCM para
a notac¸a\u2dco decimal. Voce\u2c6 pode ajuda´-lo?
Entrada: cada caso de teste e´ fornecido em uma linha simples que conte´m um nu´mero
na\u2dco vazio de no ma´ximo 5 d´\u131gitos, representando um nu´mero em notac¸a\u2dco UMC. Este
nu´mero na\u2dco conte´m zeros a esquerda. O u´ltimo teste e´ sequido por uma linha contendo
um zero.
Sa´\u131da: para cada caso de teste imprimir uma linha simples contendo a representac¸a\u2dco
em notac¸a\u2dco decimal do correspondente nu´mero em UMC seguido do ca´lculo feito para
a conversa\u2dco.
O programa: seu programa deve, para cada nu´mero da entrada, converte\u2c6-lo em um
vetor de inteiros, sendo que cada d´\u131gito do nu´mero e´ um elemento do vetor, e fazer os
ca´lculos usando este vetor.
Exemplos de entrada e sa´\u131da:
ENTRADA SAI´DA
719 53 = 7 x 3! + 1 x 2! + 9 x 1!
1 1 = 1 x 1!
15 7 = 1 x 2! + 5 x 1!
110 8 = 1 x 3! + 1 x 2! + 0 x 1!
102 8 = 1 x 3! + 0 x 2! + 2 x 1!
0
41. Sabemos que nos compiladores mais recentes, nos quais existe o tipo string, podemos
realizar de maneira simples operac¸o\u2dces com palavras. Imagine, no entanto, que estamos
usando um compilador Pascal no qual na\u2dco existe este tipo. Neste caso o programa-
dor deve implementar por sua pro´pria conta os procedimentos com palavras. Neste
exerc´\u131cio iremos considerar a seguinte declarac¸a\u2dco alternativa para o tipo string:
type palavra = array[1..MaxTam] of char;
Implemente uma func¸a\u2dco em Pascal que receba como para\u2c6metros duas varia´veis do
tipo MeuString e retorne -1 se a primeira palavra for lexicograficamente menor que a
segunda, 0 se forem iguais, e +1 no caso que resta.
42. Fac¸a um programa que leia um certo nu´mero indefinido de vetores e que imprima
o vetor original (O) e um vetor gerado (G) apo´s um processo de compactac¸a\u2dco que
consiste na eliminac¸a\u2dco de todos os elementos repetidos em cada vetor. Considere que
a entrada de dados e´ feita em um vetor por linha, sendo que o primeiro elemento da
linha e´ o tamanho de cada vetor e os elementos restantes da linha sa\u2dco os elementos
do vetor. Quando o tamanho for zero significa que terminou a entrada de dados. Por
exemplo, considere a seguinte entrada:
10.1. VETORES 177
5 2 4 7 -1 2
3 1 1 1
7 3 4 5 3 4 5 1
0
Devera´ produzir como sa´\u131da o seguinte:
O: 2 4 7 -1 2
G: 2 4 7 -1
O: 1 1 1
G: 1
O: 3 4 5 3 4 5 1
G: 3 4 5 1
43. Considere uma seque\u2c6ncia de d´\u131gitos bina´rios como:
011100011
Uma maneira de criptografar essa seque\u2c6ncia de bits e´ adicionar a` cada d´\u131gito a soma
dos seus d´\u131gitos adjacentes. Por exemplo, a seque\u2c6ncia acima se tornaria:
123210122
Se P e´ a seque\u2c6ncia original e Q e´ a seque\u2c6ncia criptografada, enta\u2dco Q[i] = P [i \u2212 1] +
P [i] + P [i + 1] para todas as posic¸o\u2dces i da seque\u2c6ncia. Considerando uma seque\u2c6ncia
de tamanho n e seus \u131´ndices variando de 0 a n\u2212 1, os d´\u131gitos P [\u22121] e P [n] na\u2dco fazem
parte da seque\u2c6ncia original e sa\u2dco tratados como zeros na operac¸a\u2dco de codificac¸a\u2dco.
Assumindo P [0] = 0 temos:
\u2022 Q[0] = P [0] + P [1] = 0 + P [1] = 1, logo P [1] = 1.
\u2022 Q[1] = P [0] + P [1] + P [2] = 0 + 1 + P [2] = 2, logo P [2] = 1.
\u2022 Q[2] = P [1] + P [2] + P [3] = 1 + 1 + P [3] = 3, logo P [3] = 1.
\u2022 Repetindo a operac¸a\u2dco temos: P [4] = 0, P [5] = 0, P [6] = 0, P [7] = 1 e P [8] = 1.
Agora repetindo o mesmo processo para P [0] = 1 temos:
\u2022 Q[0] = P [0] + P [1] = 1 + P [1] = 1, logo P [1] = 0.
\u2022 Q[1] = P [0] + P [1] + P [2] = 1 + 0 + P [2] = 2, logo P [2] = 1.
\u2022 Q[2] = P [1] + P [2] + P [3] = 0 + 1 + P [3] = 3, o que nos leva a conclusa\u2dco
que P [3] = 2. Entretanto isso viola o fato da seque\u2c6ncia original ser bina´ria.
Portanto na\u2dco existe uma decodificac¸a\u2dco poss´\u131vel considerando o primeiro d´\u131gito
da seque\u2c6ncia original valendo 1.
Note que este algoritmo pode gerar ou decodificar uma seque\u2c6ncia criptografada em
ate´ duas poss´\u131veis seque\u2c6ncias originais, uma iniciando com 0 e outra iniciando com 1.
Escreva um procedimento em que receba como para\u2c6metros um vetor de nu´meros
inteiros contendo a seque\u2c6ncia criptografada e a decodifica em dois outros vetores de
nu´meros inteiros. Caso uma das decodificac¸o\u2dces na\u2dco seja poss´\u131vel, como no caso do
178 CAPI´TULO 10. ESTRUTURAS DE DADOS
exemplo para P [0] = 1, o vetor correspondente deve ser preenchido com -1 na posic¸a\u2dco
inicial.
Outros exemplos:
\u2022 123210122 = 011100011,\u22121
\u2022 11 = 01, 10
\u2022 22111 = \u22121, 11001
\u2022 123210120 = \u22121,\u22121
\u2022 3 = \u22121,\u22121
\u2022 12221112222221112221111111112221111 =
01101001101101001101001001001101001,
10110010110110010110010010010110010
44. Escrever um programa para ler um texto e imprimir uma distribuic¸a\u2dco