Vetores (Aula 6)

Vetores
(Aula 6)
Nas aulas anteriores j� vimos como armazenar alguns tipos de dados na mem�ria do computador. Como fazer para armazenar um conjunto de dados do mesmo tipo? Nesta aula vamos tratar deste problema.
Em Pascal, para declarar uma vari�vel que armazena um conjunto de dados do mesmo tipo � utilizado a palavra array. Vamos supor que desejamos declarar uma vari�vel para armazenar o nome de uma pessoa. Sabemos que um nome � constituido de caracteres, portanto a declara��o seria:
Var nome: array [1..100] of char
Esta declara��o informa ao computador para reservar 100 caxinhas do tipo char para armazenar o nome de uma pessoa. Na declara��o entre parenteses � colocado o n�mero m�ximo de elementos do array, neste caso, como n�o sabemos antecipadamente qual vai ser o tamanho do nome, colocamos um n�mero grande. Vamos resolver um problema aplicando arrays.
Problema:
Dado o nome de uma pessoa, determinar o n�mero de vogais contidos no nome.
Solu��o
Para determinar o n�mero de vogais vamos utilizar um contador. A cada passo vamos comparando os caracteres um por um e quando achar uma vogal vamos acrescentar 1 ao contador. Para acessar cada caractere dentro do array, vamos tamb�m precisar de um contador. Vejamos como seria o algoritmo.
Algoritmo
Inicializar o contador=0;
Inicializar o indice: i=1;
Ler o nome
Enquanto indice<=100 se nome[i] for igual a 'a' acrecentar o contador se nome[i] for igual a 'e' acrecentar o contador se nome[i] for igual a 'i' acrecentar o contador se nome[i] for igual a 'o' acrecentar o contador se nome[i] for igual a 'u' acrecentar o contador acrecentar o indice i Fim enquanto Programa Program Vogais; Var nome : array [1..100] of char; contador, i : integer; Begin contador:= 0; i:= 1; Readln (nome); While (i <=100) do Begin if (nome[i] = 'a') then contador:=contador + 1; if (nome[i] = 'e') then contador:=contador + 1; if (nome[i] = 'i') then contador:=contador + 1; if (nome[i] = 'o') then contador:=contador + 1; if (nome[i] = 'u') then contador:=contador + 1; i:=i+1; End; Writeln ('O n�mero de vogais presentes no nome �:', contador); end. Alguns compiladores de Pascal j� incluem o tipo string definido como um array de carateres. Portanto o a vari�vel nome pode ser declarado tamb�m da seguinte forma: Var nome:string[100]; Como um vetor � uma pilha de caixas, para acessar a uma determinada caixa precisamos de um �ndice. O �ndice � um n�mero que vai de 1 at� o n�mero de elementos do vetor. Se quisermos acessar a todas as caixas vamos alterando em cada passo o valor do �ndice, como mostra o programa. Para ler ou alterar o conte�do da caixa i de um vetor, simplemente escrevemos o nome seguido do �ndice entre chaves. Por exemplo, no programa a linha If (nome[i]='a') contador:=contador+1; indica que vamos comparar o conte�do da caixa i no vetor nome com o caractere 'a' e se forem iguais acrecentamos o contador. Usando o comando FOR Temos visto que em muitos casos conhecemos o n�mero de repeti��es de um bloco de comandos, para tanto temos usado o comando while juntament com um contador. Por exemplo, no programa anterior o bloco dentro do comando while � repitido enquanto o indice i � menor ou igual a 100 e em cada passo acrecentamos o valor do indice. Para estas situa��es em Pascal existe o comando FOR que deixa o trabalho mais simples. O formato do comando � o seguinte: FOR i:=valor inicial TO valor final DO BEGIN comandos END Este comando pode ser utilizado somente se i for declarado como n�mero inteiro e conhecermos seus valores inicial e final. Vejamos como seria o programa anterior usando o comando FOR. Programa Program Vogais; Var nome : string[100]; contador, i : integer; Begin contador:= 0; Readln (nome); For i:=1 to 100 do Begin if (nome[i] = 'a') then contador:=contador + 1; if (nome[i] = 'e') then contador:=contador + 1; if (nome[i] = 'i') then contador:=contador + 1; if (nome[i] = 'o') then contador:=contador + 1; if (nome[i] = 'u') then contador:=contador + 1; End; Writeln ('O n�mero de vogais presentes no nome �:', contador); end. O comando for � bastante usado principalmente para acessar aos elementos de um vetor. Problema: Temperatura Lunar Sem as prote��es da atmosfera e do cintur�o magn�tico que existem na Terra, a Lua fica exposta ao ataque do Sol, que � um astro em constante explos�o at�mica. As explos�es do Sol emitem ondas letais de part�culas. Uma pessoa que ficasse desprotegida na superf�cie da Lua, num lugar onde o Sol incidisse diretamente, sofreria um bombardeio radioativo t�o intenso quanto se estivesse nas imedia��es da usina russa de Chernobyl no momento do acidente que matou 31 pessoas em 1986. Al�m da radia��o solar, outro efeito desta falta de prote��o contra o Sol que existe na Lua � a enorme varia��o de temperatura. Nas regi�es pr�ximas do equador lunar, a varia��o de temperatura � brutal, passando de cerca de 130 graus positivos durante o dia a 129 graus negativos � noite. Para estudar com mais precis�o as varia��es de temperatura na superf�cie da Lua, a NASA enviou � Lua uma sonda com um sensor que mede a temperatura de 1 em 1 minuto. Um dado importante que os pesquisadores desejam descobrir � como se comporta a m�dia da temperatura, considerada em intervalos de uma dada dura��o (uma hora, meia hora, oito horas, etc.). Por exemplo, para a seq��ncia de medi��es 8, 20, 30, 50, 40, 20, -10, e intervalos de quatro minutos, as m�dias s�o respectivamente 108/4=27, 140/4=35, 140/4=35 e 100/4=25. Tarefa Voc� foi recentemente contratado pela NASA, e sua primeira tarefa �, a partir de algumas seq��ncias de temperaturas medidas pelo sensor e do tamanho do intervalo, informar qual a maior e qual a menor temperatura m�dia observadas, considerando o tamanho do intervalo dado. Dados de entrada e sa�da Os dados de entrada tem o seguinte formato A primeira linha cont�m dois n�meros inteiros positivos N e M, que indicam respectivamente o n�mero total de medi��es de temperatura de uma seq��ncia obtida pelo sensor, e o tamanho dos intervalos, em minutos, em que as m�dias devem ser calculadas. As N linhas seguintes cont�m um n�mero inteiro cada, representando a seq��ncia de medidas do sensor. Exemplo de entrada de dados: 4 2 -5 -12 0 6 o resultado de sa�da para o teste de entrada -8 3 Solu��o Como n�o sabemos com anteced�ncia o n�mero m�ximo de medi��es vamos reservar um n�mero bem grande de caixas para o vetor (por exemplo, 100). As medi��es vamos lendo e armazenando no vetor. Em primeiro lugar devemos calcular a m�dia a cada M medi��es e guardar em outro vetor TM. Depois, no vetor de medias TM vamos procurar qual � o maior e o menor valor. Vejamos como seria o algoritmo inicial. Algoritmo Ler o n�mero de medi��es N Ler o tamanho do intervalo M Para i=1 at� i=N repetir Ler a medi��o i e guardar em T[i] Fim Para Calcular a media a cada intervalo Calcular o valor m�ximo do vetor Calcular o valor m�nimo do vetor Mostrar resultados Para calcular a m�dia a cada M medi��es podemos fazer o seguinte: Vamos utilizar um la�o para ler cada elemento do vetor e vamos ir sumando os valores em uma variavel S. Um contador dentro do la�o sera utilizado para contar o n�mero de leituras. Quando o contador chegar a M vamos calcular a m�dia, guardar o resultado no vetor TM e zerar o contador. Vejamos como fica o algoritmo. Algoritmo Ler o n�mero de medi��es N Ler o tamanho do intervalo M Para i=1 at� i=N repetir Ler a medi��o i e guardar em T[i] Fim Para Inicializar: S=0,contador=0,j=1 Para i=1 at� i=N repetir acrecentar o contador somar a medi��o i: S=S+T[i] Se contador = M Entao Calcular a media: TM[j]=S/M acrecentar j zerar o contador zerar a soma Fim Se Fim Para Calcular o valor m�ximo do vetor Calcular o valor m�nimo do vetor Mostrar resultados O m�todo mais simples de calcular o valor m�ximo de um vetor � inicialmente considerar o primeiro valor como m�ximo e logo ir comparando com os demais valores, caso encontrar alguem maior, o valor do maximo sera substitutido pelo novo maior valor, assim sucessivamente at� chegar ate o final do vetor. O valor m�nimo do vetor pode ser calculado de forma similar. Vejamos como fica o algoritmo final. Algoritmo Ler o n�mero de medi��es N Ler o tamanho do intervalo M Para i=1 at� i=N repetir Ler a medi��o i e guardar em T[i] Fim Para Inicializar: S=0,contador=0,j=1 Para i=1 at� i=N repetir acrecentar o contador somar a medi��o i: S=S+T[i] Se contador = M Entao calcular a media: TM[j]=S/M acrecentar j zerar o contador zerar a soma Fim Se Fim Para Max=TM[1], Min=TM[i] Para i=2 at� i=j-1 fazer Se (TM[i] > Max) Entao Max = TM[i]
Se (TM < Min) Entao Min = TM[i] Fim Para Mostrar Max e Min Programa Program Temp; Var T: array [100] of integer TM: array [100] of integer M,N: integer i,j,contador: integer S,Max,Min: integer Begin Readln(N); Readln(M); For i=1 to N do Begin Readln(T[i]); End S:=0;contador:=0;j:=0; For i=1 to N do Begin contador=contador+1; S=S+T[i]; if(contador=M) Begin j:=j+1; TM[j]:=S/M; contador:=0; S:=0; End End Max=TM[1]; Min=TM[1]; For i=1 to i=j do Begin If(TM[i]>Max) Max:=TM[i];
If(TM[] End
Writeln(Max, Min);
End.
Exerc�cios
Um CPF tem nove d�gitos e mais dois para verifica��o. A verifica��o se d� da seguint forma: Primeiro, multiplicamos cada um dos nove d�gitos por um peso:
d1 d2 d3 d4 d5 d6 d7 d8 d9 <--- digitos
x 10 9 8 7 6 5 4 3 2 <--- pesos
--------------------------
a1 a2 a3 a4 a5 a6 a7 a8 a9
E depois calculamos S1, a soma de todos os n�meros resultantes. O d�cimo d�gito, d10, ser� [ 11-(resto de S1/11) ] (ou zero, se esta conta der mais que nove). Para calcular d11, fazemos como antes, mas levamos em conta tamb�m d10:
d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 <--- digitos
x 11 10 9 8 7 6 5 4 3 2 <--- pesos
------------------------------
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
Somamos agora todos os n�meros obtidos. O d�gito d11 ser� [ 11-(resto de S2/11) ], ou zero se esta conta der mais que nove.
Fa�a um programa que verifique se um CFP est� correto.

Temos um vetor com 20 n�meros. Queremos reorganizar o vetor de forma que dois n�meros pares n�o sejam vizinhos. Fa�a um programa que reorganize o vetor desta forma, ou diga que n�o � poss�vel.
Palindromes
Uma cadeia de caracteres � dita pal�ndrome se a seq��ncia dos caracteres da cadeia de esquerda para direita � igual a seq��ncia de caracteres da direita para esquerda. Por exemplo as seguintes cadeias de caracteres s�o pal�ndromes: ARARA, RADAR, AKASAKA, ANNA. Fa�a um programa que reconhe�a se uma cadeia de caracteres � palindrome. Use a fun��o Length(s) para saber o tamanho da cadeia s.
Quermesse.
Os alunos do �ltimo ano resolveram organizar uma quermesse para arrecadar fundos para a festa de formatura. A festa prometia ser um sucesso, pois o pai de um dos formandos, Te�filo, dono de uma loja de inform�tica, decidiu doar um computador para ser sorteado entre os que comparecessem. Os alunos prepararam barracas de quent�o, pipoca, doces, ensaiaram a quadrilha e colocaram � venda ingressos numerados sequencialmente a partir de 1. O n�mero do ingresso serviria para o sorteio do computador. Ficou acertado que Te�filo decidiria o m�todo de sorteio; em princ�pio o sorteio seria, claro, computadorizado.

O local escolhido para a festa foi o gin�sio da escola. A entrada dos participantes foi pela porta principal, que possui uma roleta, onde passa uma pessoa por vez. Na entrada, um funcion�rio inseriu, em uma lista no computador da escola, o n�mero do ingresso, na ordem de chegada dos participantes. Depois da entrada de todos os participantes, Te�filo come�ou a trabalhar no computador para preparar o sorteio. Verificando a lista de presentes, notou uma caracter�stica not�vel: havia apenas um caso, em toda a lista, em que o participante que possuia o ingresso numerado com i, havia sido a i-�sima pessoa a entrar no gin�sio. Te�filo ficou t�o encantado com a coincid�ncia que decidiu que o sorteio n�o seria necess�rio: esta pessoa seria o ganhador do computador.
Tarefa
Conhecendo a lista de participantes, por ordem de chegada, sua tarefa � determinar o n�mero do ingresso premiado, sabendo que o ganhador � o �nico participante que tem o n�mero do ingresso igual � sua posi��o de entrada na festa.
Entrada
como entrada o programa recebe o n�mero de participantes N (N<=1000), e a seq��ncia, em ordem de entrada, dos N ingressos das pessoas que participaram da festa.
ejemplo de entrada:
8
3 5 9 4 6 2 10 1
Sa�da
4
Sorvete
Jo�ozinho � um menino que costuma ir � praia todos os finais de semana com seus pais. Eles freq�entam sempre a mesma praia, mas cada semana o pai de Jo�ozinho estaciona o carro em um local diferente ao longo da praia, e instala sua fam�lia em um ponto na praia em frente ao carro. Jo�ozinho � muito comil�o, e adora de tomar sorvete na praia. Contudo, alguns dias acontece de nenhum sorveteiro passar pelo local onde eles est�o. Intrigado com isto, e n�o querendo mais ficar sem tomar seu sorvete semanal, Jo�ozinho foi at� a Associa��o dos Sorveteiros da Praia (ASP), onde ficou sabendo que cada sorveteiro passa o dia percorrendo uma mesma regi�o da praia, indo e voltando. Al�m disto, cada sorveteiro percorre todos os dias a mesma regi�o. J�aozinho conseguiu ainda a informa��o dos pontos de in�cio e fim da regi�o percorrida por cada um dos sorveteiros.

Com base nestes dados, Jo�ozinho quer descobrir os locais da praia onde o pai dele deve parar o carro, de forma que pelo menos um sorveteiro passe naquele local. S� que o volume de dados � muito grande, e Jo�ozinho est� pensando se seria poss�vel utilizar o computador para ajud�-lo nesta tarefa. No entanto Jo�ozinho n�o sabe programar, e est� pedindo a sua ajuda.
Tarefa
Voc� deve escrever um programa que leia os dados obtidos pelo Jo�ozinho e imprima uma lista de intervalos da praia por onde passa pelo menos um sorveteiro.
Entrada
Seu programa deve ler v�rios conjuntos de teste. A primeira linha de um conjunto de teste cont�m dois inteiros n�o negativos, P e S, que indicam respectivamente o comprimento em metros da praia e o n�mero de sorveteiros. Seguem-se S linhas, cada uma contendo dois n�meros inteiros U e V que descrevem o intervalo de trabalho de cada um dos sorveteiros, em metros contados a partir do in�cio da praia (U < V, 0 ≤U ≤P e 0≤V ≤ P). O final da entrada � indicado por S=0 e P=0.
Exemplo de entrada
200 2
0 21
110 180
1000 3
10 400
80 200
400 1000
10 2
1 4
5 6
0 0
Sa�da
Para cada conjunto de teste da entrada seu programa deve produzir uma lista dos intervalos da praia que s�o servidos por pelo menos um sorveteiro. A lista deve ser precedida de uma linha que identifica o conjunto de teste, no formato "Teste n", onde n � numerado a partir de 1. Cada intervalo da lista deve aparecer em uma linha separada, sendo descrito por dois n�meros inteiros U e V, representando respectivamente o in�cio e o final do intervalo (U < V). O final da lista de intervalos deve ser indicado por uma linha em branco. A grafia mostrada no Exemplo de Sa�da, abaixo, deve ser seguida rigorosamente.
Exemplo de sa�da
Teste 1
0 21
110 180

Teste 2
10 1000

Teste 3
1 4
5 6
A solu��o dos exercicios voce encontra aqui.

Posted in: Aulas Tutorias