Questão 6: Crie uma função soma_quadrados ( n ) que retorne a soma de todos os quadrados perfeitos
que sejam menores que n . (O resultado é um único número, não uma lista).
Exemplo: soma_quadrados (30) deve retornar
.
Passo 1
O enunciado pede que eu crie uma função chamada e retorne a soma de todos os quadrados perfeitos menores que
. As informações relevantes são:
soma_quadrados que recebe um número inteiro
- Entrada: um número inteiro
. - Queremos somar os quadrados perfeitos
que satisfazem . - Resultado: um único número (a soma), não uma lista.
- Exemplo dado: para
a soma deve ser .
Passo 2
Entendendo o que é um quadrado perfeito (aula rápida): um número é quadrado perfeito quando ele pode ser escrito como o quadrado de um inteiro. Ou seja,
é quadrado perfeito se existe um inteiro
tal que
. Exemplos:
,
,
,
,
, etc.
Se queremos todos os quadrados perfeitos menores que
, estamos procurando todos os inteiros
tais que
O conjunto desses
é
, onde
é o maior inteiro que satisfaz
. Em outras palavras,
(ou equivalentemente o maior inteiro com
).
Passo 3
Escolha do método: vou apresentar dois jeitos (um simples para implementar à mão na prova e um um pouco mais “matemático” e rápido).
- Método direto (iterativo/loop): percorro
somando enquanto . Este método é simples, não exige fórmulas e é fácil de implementar sem erros. - Método fechado (fórmula): se
é o maior inteiro com , existe uma fórmula conhecida para a soma dos primeiros quadrados:
Nesse método basta calcular
e aplicar a fórmula — é O(1) em tempo, mas precisa lembrar a fórmula e calcular
corretamente.
Pela regra do nosso algoritmo de escolha (usar métodos mais básicos primeiro), vou priorizar o método iterativo na implementação principal porque é elementar e robusto; depois mostro a versão com a fórmula como alternativa eficiente.
Passo 4
Descrevendo passo a passo o método iterativo (a forma que eu faria na prova se não quiser arriscar erro com fórmulas):
- Inicializo um acumulador
. - Faço
. - Enquanto
: faço e . - Quando
eu paro e retorno .
Explicação das variáveis:
-
: entrada (limite superior, não incluso). -
: índice dos quadrados perfeitos . -
: soma acumulada dos quadrados menores que .
Esse procedimento garante que somamos exatamente os quadrados
com
.
Passo 5
Atenção a casos particulares (detalhes importantes para não errar na prova):
- Se
, não existe quadrado perfeito positivo menor que . Logo a soma deve ser . - Se
for pequeno, o loop termina rápido porque já pode ser maior ou igual a . - A condição do loop deve ser estrita
, pois se esse quadrado não deve ser contado (o enunciado pede "menores que ").
Passo 6
Versão alternativa com fórmula (útil de conhecer e usar se tiver boa precisão aritmética):
- Primeiro calculo
(o maior inteiro com ). - Uso a fórmula
- Retorno esse valor.
Exemplo rápido: paratemos e
que bate com
.
Passo 7
Complexidade (explicando sem jargões difíceis): no método iterativo você faz um passo por cada
até
, e
é aproximadamente
. Portanto o número de operações cresce na ordem de
. No método com fórmula você faz um número fixo de operações independentemente de
, então é muito mais rápido para
grande, mas exige a fórmula e que você calcule
corretamente.
Passo 8
Exemplo prático passo a passo com o método iterativo para
:
-
: . -
: . -
: . -
: . -
: . -
: → paro e retorno .
Isso coincide com o exemplo do enunciado.
Passo 9
Implementação prática (explicação do que o código faz, linha a linha, para você poder escrever na prova):
- Defina a função
soma_quadrados(n). - Trate o caso
retornando . - Use um acumulador
s = 0e um índicek = 1. - Enquanto
k*k < n: faças += k*kek += 1. - No final retorne
s.
Resposta
def soma_quadrados(n):
if n <= 1:
return 0
s = 0
k = 1
while k * k < n:
s += k * k
k += 1
return s
if n <= 1:
return 0
s = 0
k = 1
while k * k < n:
s += k * k
k += 1
return s