Resolvendo problemas

Resolvendo problemas
(Aula 5)
Nesta aula vamos nos dedicar a resolver problemas interessantes e escrever programas utilizando os comandos da linguagem Pascal aprendidos nas aulas anteriores. A melhor forma de aprender as coisas � praticando e com a programa��o n�o � nada diferente. Por isso, neste curso voc� vai encontrar muitos exemplos e exerc�cios para treinar.
Problema 1: Roland Garros
No torneio de Roland Garros, um dos mais tradicionais torneios de t�nis do mundo, realizado em Paris, participaram 128 tenistas. Em cada partida, participam dois jogadores, sendo que o vencedor passa para a pr�xima fase, e o perdedor � eliminado do torneio. A cada rodada, os tenistas que ainda continuam no torneio participam de exatamente uma partida. Qual o n�mero total de partidas deste torneio?
Solu��o
Como h� 128 participantes, na primeira rodada acontecem 64 jogos. Portanto na segunda rodada tem apenas 32 jogos, depois 16 e assim sucessivamente at� ficar apenas um jogo na final. Como podemos perceber, a cada rodada temos a metade de jogos da rodada anterior. Portanto, somando o n�mero de partidas a cada rodada teremos a resposta para o problema. Ou seja, 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127
Se quisermos resolver este problema no computador, qual seria o algoritmo? Vamos supor que N � o n�mero de participantes (inicialmente N=128), P o n�mero de partidas em cada rodada e S a soma total de partidas. Vejamos o que acontece com o valor de cada uma destas vari�veis.
O n�mero de partidas em cada rodada e igual a metade do numero de participantes, ou seja P=N/2
O n�mero total de rodadas � calculado acrecentando as partidas jogadas em cada rodada da seguinte forma S=S+P
No final de cada rodada ficam apenas a metade do n�mero de participantes, ou seja N=N/2
A cada rodada os c�lculos se repetem, e isso acontece enquanto o n�mero de participantes for maior que 1. Levando em conta estas considera��es o algoritmo para este problema seria o seguinte:
Algoritmo
1. Inicializar N: N = 128
2. Repetir enquanto N > 1
3. Calcular P: P = N/2
4. Atualizar S: S = S + P
5. Atualizar N: N = N/2
6 Fim da repeti��o
7. Mostrar S

O programa correspondente a este algoritmo � o seguinte:
Programa
Program PartidasTenis;
Var N,P,S: Real;
Begin
N:=128;
While(N>1) do
Begin
P:=N/2;
S:=S+P;
N:=N/2;
End;
Writeln('O n�mero total de partidas �: ',S);
End.
Problema 2: Calculando
A dissemina��o dos computadores se deve principalmente � capacidade de eles se comportarem como outras m�quinas, vindo a substituir muitas destas. Esta flexibilidade � poss�vel porque podemos alterar a funcionalidade de um computador, de modo que ele opere da forma que desejarmos: essa � a base do que chamamos programa��o.
Tarefa
Sua tarefa � escrever um programa que fa�a com que o computador opere como uma calculadora simples. O seu programa deve ler express�es aritm�ticas e produzir como sa�da o valor dessas express�es, como uma calculadora faria. O programa deve implementar apenas um subconjunto reduzido das opera��es dispon�veis em uma calculadora: somas e subtra��es.
Entrada
A entrada � composta de um n�mero inteiro m (1 ≤ m ≤ 100), indicando o n�mero de operandos da express�o a ser avaliada, uma seq��ncia de n�mero, simbolo e n�mero, indicando o operando, opera��o e operando, no seguinte formato:
X1
s1
X2
s2
...
Xm-1
sm-1
Xm

onde
Xi , 1 ≤ i ≤ m, � um operando (0 ≤ Xi ≤ 100);
sj, 1 ≤ j < m, � um operador, representado pelos s�mbolos `+' ou `-'; Exemplo de Entrada 3 4 + 7 - 22 Exemplo de Sa�da -11 Solu��o Seja m o n�mero de operandos, x o operando, s o operador e res o resultado do c�lculo. Inicialmente, lemos o valor de m, depois o primeiro operando e inicializamos o valor res com o primeiro operando. Para saber o n�mero de operandos lidos vamos usar um contador i. Um poss�vel algoritmo para este problema seria: Algoritmo 1. Ler m 2. Iniciar o contador: i=1 3. Ler x 4. Iniciar o resultado: res=x 5. Enquanto i < m fazer 6. Ler s 7. Ler x 8. Se s='+' ent�o 9. res=res+x 10. Se s='-' ent�o 11. res=res-x 12. Atualizar o contador: i=i+1 13. Fim enquanto 14. Mostrar res Programa Programa Program calculadora; Var i,m: integer; x,res: real; s: char; Begin Readln(m); i:=1; Readln(x); res:=x; While(i

Programa indentado corretamente
Program calculadora;
Var m: integer;
x,res: real;
s: char;
Begin
Readln(m);
i:=1;
Readln(x);
res:=x;
While(i Begin
Readln(s);
Readln(x);
If (s = '+') Then
res:=res+x;
If (s = '-') Then
res:=res-x;
i:=i+1;
End;
Writeln(res);
End.

Exerc�cios
Jogo de adivinhar
Fa�a um programa para voc� jogar com o computador. O computador escolhe um n�mero inteiro entre 1 e 1000 e voc� o adivinha. Se voc� acertar o n�mero em menos de 10 tentativas, voc� ganha o jogo. A cada tentativa o computador informa se o n�mero esta acima ou abaixo do n�mero chutado. Utilize o comando random do Pascal para o computador gerar um n�mero aleat�rio.
exemplo de como usar random:
x:=random; {o computador gera um n�mero real aleat�rio entre 0 e 1}
use o round para converter um n�mero real em um n�mero inteiro, exemplo:
n:=round(x);
Bits Trocados
As Ilhas Weblands formam um reino independente nos mares do Pac�fico. Como � um reino recente, a sociedade � muito influenciada pela inform�tica. A moeda oficial � o Bit; existem notas de B$ 50,00, B$10,00, B$5,00 e B$1,00. Voc� foi contratado(a) para ajudar na programa��o dos caixas autom�ticos de um grande banco das Ilhas Weblands.
tarefa
Os caixas eletr�nicos das Ilhas Weblands operam com todos os tipos de notas dispon�veis, mantendo um estoque de c�dulas para cada valor (B$ 50,00, B$10,00, B$5,00 e B$1,00). Os clientes do banco utilizam os caixas eletr�nicos para efetuar retiradas de um certo n�mero inteiro de Bits.

Sua tarefa � escrever um programa que, dado o valor de Bits desejado pelo cliente, determine o n�mero de cada uma das notas necess�rio para totalizar esse valor, de modo a minimizar a quantidade de c�dulas entregues. Por exemplo, se o cliente deseja retirar B$50,00, basta entregar uma �nica nota de cinquenta Bits. Se o cliente deseja retirar B$72,00, � necess�rio entregar uma nota de B$50,00, duas de B$10,00 e duas de B$1,00.
exemplo de entrada
72
exemplo de sa�da
1 2 0 2

Numeros bin�rios
Voc� sabia que o computador internamente trabalha apenas con os n�meros 0 e 1?. Quando nos escrevemos o programa em pascal, o compilador ainda precisa transformar o programa num codigo que contem apenas os digitos 0 e 1. Os n�mero compostos apenas por estes dois digitos s�o chamados de n�meros binarios, e cada digito � chamado de bit. Os n�meros que estamos acostumados usar contem digitos de 0 at� 9 e s�o chamados de n�meros em base 10. Como faz o compilador para tranformar um n�mero base 10 num n�mero bin�rio?. Vejamos alguns exemplo de convers�o em n�meros bin�rios.
52 = 110100
20 = 10100
10 = 1010
Um n�mero X em base 10 pode ser expresso em termos de um n�mero bin�rio com os digitos ...b5b4b3b2b1b0. Da seguinte forma:
X = b0*20 + b1*21 + b2*22 + b3*23 + b4*24 + ...
por exemplo, o n�mero 20 pode ser expresso em n�mero bin�rio como:
20 = 1 0 1 0 0
| | | | |
b4 b3 b2 b1 b0
20 = 1*24 + 0*23 + 1*22 + 0*21 + 0*20
Tarefa
Escreva um programa que l� um n�mero N, correspondente ao n�mero de entradas. E para cada entrada X (X<256), que corresponde a um n�mero inteiro, o programa deve imprimir a representa��o em n�mero bin�rio com 8 digitos (8 bits).
Exemplo de Entrada
3
5 10 25
Exemplo de sa�da
00000101
00001010
00011001
A solu��o dos exerc�cios voc� encontra aqui.

Posted in: Aulas Tutorias