03 - Primeiros algoritmos

Neste roteiro iremos criar nossos primeiros algoritmos em Pseudo-Código e explorar sua "tradução" para Java. Conforme o roteiro avança haverá leituras (curtas) recomendadas sobre sintaxe e semântica de Java.

O esqueleto de um algoritmo

Todo algoritmo é formado pelo seguinte "esqueleto":

• Entrada:
  • lista de parâmetros do algoritmo, incluindo tipos
  • incluir também leitura de dados usando LER_<TIPO>.
  • Inteiro I (parâmetro)
  • String S1 (parâmetro)
• Saída:
  • resumo da saída do algoritmo, incluindo possíveis PRINT
  • pode conter mais de um item se ajudar a entender saídas que são condicionais
  • devolve X caso A
  • devolve Y caso contrário

NOME_DO_ALGORITMO(I, S1)

# Atribuições e operações matemáticas
MAIS_UM := I + 1

# Saída de texto
PRINT(MAIS_UM)

# Entrada de dados
NOVO_INT := LER_INTEIRO()
NOVO_FLOAT := LER_FRACIONARIO()
NOVO_TEXTO := LER_TEXTO()

Vamos aplicar esse formato para dois problemas simples e já implementá-los em Java.

Área do triângulo

Faça uma função que calcula a área de um triângulo de base b e altura h, ela deve receber os valores nesta ordem.

AREA_TRIANGULO(B, H)

DEVOLVE B * H / 2

Lançamento de Projétil

Faça uma função que calcule a distância alcançada por um projétil lançado com velocidade $v$ em um ângulo $\theta$, de uma altura $y_0$. A distância é dada pela fórmula. Use $g=9.8$.

$$d = \frac{v^2}{2g} \left(1 + \sqrt{1 + \frac{2g y_0 }{ v^2 (\sin(\theta) )^2 }} \right) sin(2\theta)$$

DISTANCIA_LANCAMENTO(V, THETA, Y0)

G := 9.8

PARTE1 := (V * V) / (2 * G)

SENO_THETA := SENO(THETA)
PARTE2_1 := (2 * G * Y0) / (V * V * SENO_THETA * SENO_THETA)
PARTE2_2 := 1 + RAIZ(1 + PARTE2_1)

PARTE3 := SENO(2 * THETA)

DEVOLVE PARTE1 * PARTE2_2 * PARTE_3

Reparou que no algoritmo acima usei V * V? Isso é feito pois os operadores Python // e ** são específicos dessa linguagem e queremos descrever nossa solução de maneira independente de linguagem. Assim, vamos levar em conta os seguintes pontos ao escrever algoritmos:

1. podemos usar a fórmula matemática mesmo ($V^2$)
2. podemos ser explícitos e escrever tudo com detalhes
3. no caso da divisão inteira, dividir dois tipos inteiro sempre causa uma divisão inteira.

Condicionais

Expressamos a ideia de condicional em Pseudo código como abaixo. A tradução Java está na aba seguinte.

SE <CONDIÇÃO AQUI> ENTÃO
    FAZ ALGO AQUI
SENÃO
    FAZ OUTRA COISA
FIM

if (condicao) {
    // faz algo aqui
} else {
    // faz outra coisa aqui
}

FizzBuzz

Faça uma função que recebe como entrada um número inteiro e testa a divisibilidade por 2 e 3. Se for divisível por 2, sua função deve retornar a string "Ins". Se for por 3, retorna "per". Porém, se for por 2 e 3 ao mesmo tempo retorna "Insper". Para outros casos, sua função deve devolver a string vazia.

DIVISIBILIDADE(N)

SE N é divisível por 2 E N não é divisível por 3 ENTÃO
    DEVOLVE "Ins"
FIM

SE N não é divisível por 2 E N é divisível por 3 ENTÃO
    DEVOLVE "per"
FIM

SE N é divisível por 2 E N é divisível por 3 ENTÃO
    DEVOLVE "Insper"
FIM

DEVOLVE ""

Jaca Wars

Você mora no sítio, e está em guerra com seu vizinho. Você dispõe de uma catapulta de lançamento de jacas, onde você consegue escolher a velocidade v e o ângulo $\theta$, em graus, de lançamento da jaca. Uma jaca quando cai se espalha por um raio de 2 metros. Seu alvo é a catapulta do vizinho, que está à 100 metros da sua.

Faça um programa que pede a velocidade e o ângulo de lançamento da sua jaca, e diz se ela cairá muito perto, muito longe, ou acertará o alvo. Considere que a jaca acerta o alvo se cai à uma distância do alvo menor que o seu raio de espalhamento. A fórmula da distância alcançada por um projétil (na ausência de efeitos de arrasto da atmosfera) é:

$$ d = \frac{v^2\sin(2\theta)}{g} $$

onde $g=9.8 m/s^2$. Os possíveis valores de retorno são 'Muito perto', 'Muito longe' e 'Acertou!'. Considere "Muito perto" se não chegou no alvo, e "Muito longe" se passou do alvo. O seu programa deve devolver exatamente essas strings, caso contrário ele será considerado errado (mesmo que a fórmula esteja correta).

ACERTOU_JACA(V, THETA)

G := 9.8
DISTANCIA := (V*V * SENO(2*THETA)) / G

SE DISTANCIA < 98 ENTÃO
    DEVOLVA "Muito perto"
FIM

SE DISTANCIA > 102 ENTÃO
    DEVOLVA "Muito longe"
FIM

DEVOLVA "Acertou!"        

Loops (I)

Loops ENQUANTO representam a ideia de repetição até que uma condição seja verdadeira. Tipicamente usamos esse loop quando não temos certeza do número de vezes que o loop executará. Veja abaixo as sintaxes para pseudo-código e Java.

ENQUANTO <CONDIÇÃO> FAÇA
    FAZ ALGO REPETIDAMENTE AQUI
FIM

while (condicao) {
    // faz algo repetidamente aqui
} 

Vamos agora direto para exercícios que usem essa construção.

Quantos uns

Escreva uma função que recebe um número e devolve a quantidade de vezes que o algarismo 1 ocorre nesse número.

QUANTOS UNS(N)
    CONTADOR := 0

    ENQUANTO N > 0 FAÇA
        DIGITO = N % 10 # resto da divisão de N por 10 
        SE DIGITO = 1 ENTÃO
            CONTADOR := CONTADOR + 1
        FIM
        N = N / 10
    FIM

    DEVOLVE CONTADOR

Loops (II)

Loops PARA CADA representam a ideia de repetição em um conjunto conhecido de valores. Tipicamente usamos esse loop para contagens ou para percorrer os elementos de uma coleção de valores. Veja abaixo as sintaxes para pseudo-código e Java.

PARA CADA I=0 ATÉ 10 FAÇA
    # FAZ ALGO COM I
FIM

for (int i = 0; i < 10; i++) {
    // faz algo com i
} 

Vamos agora direto para exercícios que usem essa construção.

Estimando o valor de pi

O valor de $\pi$ pode ser aproximado a partir da seguinte fórmula:

$$\pi = \sqrt{\frac{6}{1^2} + \frac{6}{2^2} + \frac{6}{3^2} + \dots + \frac{6}{n^2}}$$

Faça uma função que recebe o valor de $n$ e retorna o resultado da fórmula acima utilizando os $n$ termos.

CALCULA_PI(N)
    PI_2 := 0

    PARA CADA I:=1 ATÉ N+1 FAÇA
        PI_2 := PI_2 + 6 / (I * I)
    FIM 

    DEVOLVE RAIZ(PI_2)

Fatorial

Escreva uma função que recebe um número $n$ e devolve o valor de $n! = 1\cdot 2\cdot 3\cdot\dots\cdot n$.

FATORIAL(N)
    FAT := 1

    PARA CADA I=1 ATÉ N+1 FAÇA
        FAT := FAT * I
    FIM

    DEVOLVE FAT