1. Escrita de algoritmos

O primeiro passo do projeto de algoritmos consiste em definir formalmente o problema que tentamos resolver. Para isso, é necessário entender quais são as entradas do problema e quais são as saídas que devemos produzir. Depois disso, precisamos colocar em prática o nosso conhecimento sobre as estruturas de controle, estruturas de dados, algoritmos fundamentais, técnicas de análise etc. Temos que combinar todo esse aprendizado com nossa criatividade para então resolvermos o problema. Vamos exercitar o projeto de algoritmos utilizando o que aprendemos até aqui para os dois problemas a seguir.

O dragão de muitas cabeças

Um dragão muito peculiar está causando o terror em uma pequena cidade. O dragão possui várias cabeças e, a cada minuto, cada uma de suas cabeças restantes é duplicada. Um guerreiro muito famoso consegue arrancar $x$ cabeças com sua espada no primeiro minuto de batalha. No entanto, devido ao cansaço, no segundo minuto ele consegue arrancar apenas $x - 1$ cabeças, no terceiro minuto apenas $x - 2$ e assim por diante. Passados $x$ minutos, ele fica cansado demais e não consegue mais arrancar cabeças.

Vejamos um exemplo. Suponha que inicialmente o dragão possui $6$ cabeças e que o guerreiro consegue arrancar $4$ no primeiro minuto. Terminado primeiro minuto, o guerreiro terá arrancado 4 cabeças, mas o dragão terá duplicado cada uma das 2 cabeças restantes, passando a ter 4 cabeças no início do segundo minuto. Nesse momento, o guerreiro arranca 3 cabeças, o dragão duplica a cabeça restante e passa a ter 2 no início do terceiro minuto. Finalmente, o guerreiro arranca 2 cabeças deixando o dragão sem cabeças e derrotado-o após 3 minutos.

Seu objetivo é escrever um algoritmo que determine quantos minutos são necessários para o guerreiro derrotar o dragão. Observe que o guerreiro nem sempre conseguirá derrotá-lo.

a) Identifique o conjunto de entradas e o conjunto de saídas do problema. Além disso, para cada entrada, especifique uma saída correspondente que seja coerente com o problema descrito. Neste item, você deve definir apenas um problema; não descreva um algoritmo para resolvê-lo. A definição do problema deve ser escrita em um arquivo dragao.md.

b) Construa um algoritmo para este problema na forma de um diagrama de fluxo. A sua resposta deve estar em uma imagem dragao.png ou dragao.jpg contendo o desenho do diagrama de fluxo, que pode ser elaborado no computador ou pode ser uma fotografia.

2. Linguagens de programação

Após resolvermos um problema computacional chega-se a hora de implementarmos um programa executável por um computador. Para isso é necessário traduzir nosso algoritmo para alguma linguagem de programação. Resolva as questões a seguir e escreva as respostas em um arquivo maximo.md.

Considere os algoritmos a seguir escritos na linguagem Python. O primeiro determina o valor máximo de uma lista de cinco números conhecidos. O segundo determina o valor máximo de uma sequência de números não negativos digitados por um usuário.

lista = [1, -3, 4, 2, -5]
maximo = lista[0]
for valor in lista:
    if valor > maximo:
        maximo = valor
print(maximo)

numero_digitado = int(input())
maximo = numero_digitado
while numero_digitado >= 0:
    if numero_digitado > maximo:
        maximo = numero_digitado
    numero_digitado = int(input())
print(maximo)

a) Identifique todas as variáveis e diga que tipo cada uma delas tem.

b) Para entendermos um programa de computador é necessário conhecer a sintaxe e a semântica da linguagem de programação. Em Python, as palavras-chaves (for, in, if, while, etc.) foram escolhidas para que seus significados fossem os mesmos daqueles em inglês (use um dicionário, se necessário). Identifique as estruturas de controle presentes e determine se elas correspondem a execução condicional, iteração condicional ou iteração limitada. Depois, descreva de maneira precisa qual o formato geral de cada uma dessas estruturas.

c) Em qual exemplo utilizamos iteração condicional? Explique se poderíamos reescrever os dois algoritmos usando while ou for.

Correção

Depois de submetida a tarefa, você deverá apresentá-la a um monitor PED. Para isso, você deve procurar atendimento em algum horário com monitor PED e digitar apresentar 2 no canal fila-apresentar para entrar na fila. Assim que possível, o monitor irá verificar sua tarefa no Gitlab e chamará você para uma videoconferência dentro de poucos minutos para que você explique sua tarefa ou parte dela de maneira muito concisa. O monitor irá conversar brevemente para dar um feedback construtivo para suas respostas, mostrando acertos, indicando possíveis problemas e sugerindo melhorias.

← Anterior Voltar Próximo →