Lembre-se de atualizar o seu repositório usando git pull e responda às questões abaixo criando os arquivos necessários na pasta da tarefa.

Escrita de algoritmos

Nesta tarefa, faremos dois exercícios que exercitam escrita e compreensão de algoritmos com especial atenção ao uso de variáveis e estruturas de controle de fluxo. No segundo exercício, isso será intermediado por algoritmos escritos já em linguagem de programação!

1. O problema 3n+1

Neste exercício, vamos calcular o comprimento da Sequência de Collatz de um número inteiro positivo. Imagine a seguinte transformação que podemos realizar sobre um inteiro positivo $n$ qualquer: se $n$ for par, divida-o por 2, mas, se $n$ for ímpar, multiplique-o por 3 e ao final some 1. Em outras palavras, a transformação é uma função $f(n)$ definida como

$$ f(n) = \begin{cases} n/2 & \mbox{se $n$ é par,} \\ 3n + 1 & \mbox{se $n$ é ímpar.} \end{cases} $$

Começando com um inteiro positivo $n$ qualquer e aplicando a transformação repetidas vezes, geramos uma sequência que em algum momento chega ao número $1$. Isso é verdade pelo menos sempre que o número $n$ é menor ou igual a $2^{68}$, mas ainda não se provou que é uma propriedade de todos os inteiros positivos. Trata-se de um importante problema em aberto na Matemática.

O comprimento de uma sequência de Collatz de um inteiro positivo $n$ é o número de vezes que precisamos realizar a transformação antes de obter o número $1$. O problema que queremos resolver é, dado um inteiro positivo $n$, calcular o comprimento de sua Sequência de Collatz. Por exemplo, a sequência de Collatz do número 6 é

6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

e tem comprimento 8 e a sequência de Collatz do número 9 é

9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

e tem comprimento 19. Observe que contamos apenas o número de vezes que a transformação é aplicada até chegar em $1$. Se continuássemos aplicando a transformação, nunca iríamos parar

1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> ...

a) Desenhe o fluxograma de um algoritmo que resolva o problema acima. Utilize apenas instruções elementares fundamentais, como operações aritméticas, comparações, etc. A resposta deste item deve estar em uma imagem collatz.png ou collatz.jpg com o desenho do diagrama, que pode ser elaborado no computador ou pode ser uma fotografia.

b) Expresse o algoritmo que você usou como resposta no item anterior em forma de texto de maneira clara e precisa. Em seguida, diga quais são as estruturas de controle que você utilizou nesse algoritmo. As respostas a este item devem estar em um arquivo collatz.md.

2. Linguagens de programação

Sabemos que, para resolver um problema usando computador, precisamos descrever precisamente o problema e elaborar um algoritmo que o resolva. Também sabemos que, além disso, precisamos implementar o algoritmo usando uma linguagem de programação. A compreensão de algoritmos expressos como linguagem de programação é uma habilidade fundamental para a programação de computadores.

Considere os algoritmos a seguir, escritos na linguagem de programação Python. O primeiro calcula o valor mínimo de uma lista de números pré-determinada. O segundo é um jogo interativo de adivinhação. Você responderá a algumas perguntas sobre esses algoritmos, escrevendo as respostas em um arquivo programas.md.

lista = [3, 2, -1, 8, 0, 7]
minimo = lista[0]
for valor in lista:
    if valor < minimo:
        minimo = valor
print(minimo)

numero_pensado = 42
numero_digitado = int(input('Em que número pensei? '))
while numero_digitado != numero_pensado:
    if numero_digitado < numero_pensado:
        print('Pensei em um número maior.')
    else:
        print('Pensei em um número menor.')
    numero_digitado = int(input('Tente de novo. Em que número pensei? '))
print('Você é demais!')

a) Identifique todas as variáveis nos dois programas e diga o tipo de cada uma delas.

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 terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor. Você deverá apresentar esta tarefa a algum PED. Para isso, procure atendimento em algum horário com monitor PED e digite apresentar 2 no canal fila-apresentar. O monitor irá verificar sua tarefa no Gitlab e chamará você para uma videoconferência depois de alguns minutos. Ele irá pedir que você explique sua tarefa ou parte dela de maneira muito concisa e vocês irão conversar brevemente sobre suas respostas, apontando acertos e indicando problemas e sugestões de melhoria.

← Anterior Voltar Próximo →