Texto e fórmulas
Um exemplo simples, escrito em Markdown.
Uma ideia de cada vez
Um apontamento pode ter definições, exemplos e pequenos exercícios. Usa as tuas palavras e liga às fontes que consultaste.
Neste exemplo, vamos somar os inteiros de 1 até , com inteiro não negativo. Para , a soma não tem termos e vale zero. O resultado é:
Para , temos .
Para perceber a fórmula, escreve a soma por ordem crescente e depois por ordem decrescente. Ao somar as duas linhas coluna a coluna, cada coluna dá . Há colunas, por isso o dobro da soma é . Dividir por 2 recupera a soma original. Este argumento também funciona quando é ímpar.
Um pequeno programa
def soma_naturais(n):
return n * (n + 1) // 2
print(soma_naturais(4)) # 10Em Python, // faz a divisão inteira. Aqui não perdemos uma parte decimal: de dois inteiros consecutivos, e , um é par. O produto é sempre divisível por 2.
Uma tabela
| n | Soma |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 6 |
| 4 | 10 |
Para calcular a média de pontos por fila, divide o total pelo número de filas. Com quatro filas, temos pontos por fila em média. A média pode não ser inteira, mesmo quando cada fila tem um número inteiro de pontos.
Limites de um ciclo
Em Python, range(1, n + 1) percorre os inteiros de 1 até n. O limite superior fica excluído. Começa com total = 0 e, para cada k, soma k ao total. Antes dessa atualização, total contém a soma de 1 até k - 1; depois, contém a soma de 1 até k.
Se n for zero, range(1, 1) está vazio. O total continua a zero, que é o valor da soma vazia.
Contar as operações
O ciclo faz n atualizações. A fórmula faz um número fixo de operações aritméticas. Se cada operação tiver custo constante, os custos são Θ(n) e Θ(1), respetivamente. Com inteiros de precisão arbitrária, como os de Python, o custo também depende do número de bits dos valores.
Uma imagem
A imagem representa a mesma soma. É um SVG local e inclui uma descrição para quem usa um leitor de ecrã.
Experimenta: quantos pontos teria a figura com cinco filas?
Links e próximos passos
A documentação do Markdown no Astro explica como escrever páginas. As fórmulas usam KaTeX.
Na página seguinte, juntamos gráficos, diagramas e vídeo num ficheiro MDX.
Notas de rodapé
As notas de rodapé servem para uma fonte ou uma explicação que pode ficar para depois.1
Uma afirmação com uma fonte.[^fonte]
[^fonte]: Autor, título e ligação à fonte.Avisos em Markdown
Ver uma solução
Para somar os primeiros quatro naturais, podemos juntar os extremos: e . A soma é .
Notas de rodapé
Exercícios
1. Justificar a fórmula
Justifica a fórmula da soma de 1 até n sem indução. O teu argumento deve funcionar também para n ímpar.
Pista
Escreve a soma uma vez por ordem crescente e outra por ordem decrescente.
Mais uma pista
Soma as duas linhas coluna a coluna. Quantas colunas tens e quanto vale cada uma?
Solução
Se S = 1 + 2 + … + n, então 2S = (1 + n) + (2 + n − 1) + … + (n + 1). Há n colunas, cada uma com soma n + 1. Logo S = n(n + 1)/2, incluindo n ímpar.
Confere a tua resposta:
- Associei o primeiro termo ao último.
- Cada par soma n + 1.
- Expliquei como contar os termos sem falhar quando n é ímpar.
Erros frequentes
Dizer que há n/2 pares sem tratar o termo central quando n é ímpar. A soma das duas linhas evita esse problema.
2. Calcular sem enumerar
Quanto vale a soma de todos os inteiros de 1 até 20, incluindo ambos os extremos?
Pista
Mais uma pista
Solução
20 × 21 / 2 = 210. Como a soma é inteira e exata, a tolerância é zero.
Erros frequentes
Usar 19 como último termo ou esquecer a divisão por 2.
3. Interpretar uma média
Uma figura tem seis filas, com 1, 2, 3, 4, 5 e 6 pontos. Qual é o número médio de pontos por fila? Arredonda a duas casas decimais.
Pista
Mais uma pista
Solução
A média é 21/6 = 3,50 pontos por fila. A média não precisa de ser um número inteiro de pontos.
Erros frequentes
Dividir pelo último valor da soma parcial ou arredondar prematuramente para um inteiro.
4. Prever a saída
Qual é o valor que este programa escreve?
total = 0
for k in range(1, 4):
total += k
print(total)Pista
range não é incluído.Mais uma pista
Solução
Erros frequentes
5. Escolher o estado certo
No ciclo anterior, o que representa total imediatamente antes de executar
total += k?
total += k, não antes.Só é zero antes da primeira iteração. As seguintes conservam o total acumulado.Pista
Segue as duas primeiras iterações, antes de cada atualização.
Mais uma pista
Quando k = 2, total já contém 1, mas ainda não contém 2.
Solução
Antes da atualização, total contém a soma de 1 até k − 1. Depois, contém a soma de 1 até k. O instante a que o estado se refere faz parte da resposta.
- A soma de 1 até k − 1. Antes da soma de k, só foram processados os inteiros anteriores. Para k = 1, a soma vazia vale zero.
- A soma de 1 até k. Essa é a situação depois de executar
total += k, não antes. - Sempre zero. Só é zero antes da primeira iteração. As seguintes conservam o total acumulado.
Erros frequentes
Descrever a variável sem indicar se estás antes ou depois da atualização.
6. Corrigir uma função
Corrige soma_naturais(n) para devolver a soma de 1 até n,
incluindo n. Recebe um inteiro não negativo; não deve imprimir.
def soma_naturais(n):
total = 0
for k in range(1, n):
total += k
return totalVerifica o código para comparar o resultado com os testes.
Testes
Soma vazia
Código do testeprint(soma_naturais(0))Esperado:0
Primeiro termo
Código do testeprint(soma_naturais(1))Esperado:1
Quatro termos
Código do testeprint(soma_naturais(4))Esperado:10
Vinte termos
Código do testeprint(soma_naturais(20))Esperado:210
print(soma_naturais(0))0
print(soma_naturais(1))1
print(soma_naturais(4))10
print(soma_naturais(20))210
Pista
Mais uma pista
O limite superior de range é exclusivo. Para incluir n, usa
o inteiro seguinte.
Solução
Substitui range(1, n) por range(1, n + 1).
Para n = 0, não há iterações e o total fica a zero. Para n = 4, somamos 1 +
2 + 3 + 4 = 10. A fórmula n * (n + 1) // 2 também devolve a
soma, sem um ciclo. Passar estes testes não prova o resultado para todos os
inteiros.
Erros frequentes
Excluir n do ciclo, usar print em vez de
return ou devolver um valor fixo que só funciona para uma
entrada.
7. Explicar o caso vazio
Na função corrigida, por que motivo n = 0 devolve zero? Confirma o resultado pela fórmula e pelo ciclo.
Pista
Observa range(1, 1).
Mais uma pista
O conjunto de valores do ciclo é vazio, por isso total conserva o valor inicial.
Solução
O ciclo não executa iterações e total continua a zero. Na fórmula, 0 × (0 + 1)/2 = 0. Os dois métodos concordam sobre a soma vazia.
Confere a tua resposta:
- Indiquei que o ciclo não executa nenhuma iteração.
- Relacionei o resultado com o valor inicial zero.
- Verifiquei que a fórmula também dá zero.
Erros frequentes
Dizer que a função falha por não haver iterações ou confundir soma vazia com produto vazio.
8. Comparar os dois métodos
Compara o custo do ciclo e da fórmula quando n aumenta. Que hipótese sobre o custo das operações estás a usar?
Pista
Conta quantas vezes cada método atualiza ou calcula um valor.
Mais uma pista
O ciclo repete uma soma n vezes. A fórmula não contém um ciclo, mas os inteiros podem crescer.
Solução
Com operações aritméticas de custo constante, o ciclo custa Θ(n) e a fórmula custa Θ(1). Para inteiros de precisão arbitrária, o custo de uma operação depende do número de bits. A conclusão Θ(1) não é uma análise do custo em bits.
Confere a tua resposta:
- Contei n atualizações no ciclo.
- Identifiquei um número fixo de operações aritméticas na fórmula.
- Indiquei que esta comparação assume operações aritméticas de custo constante.
Erros frequentes
Afirmar que qualquer multiplicação demora o mesmo tempo, independentemente do tamanho dos inteiros.