Estatística · FCC · 2022 | Questão sqc-fc067093

Método Congruente Linear (geração de números pseudoaleatórios)

Gabarito: letra C. Aplicando a recorrência $x_n = (a \cdot x_{n-1}) \bmod m$ com $x_0 = 5$ , $a = 3$ e $m = 120$ , obtemos $x_1 = 15$ , $x_2 = 45$ e $x_3 = 15$ , cuja soma é 75 — exatamente o valor da alternativa C.

O Método Congruente Linear é um dos algoritmos mais clássicos para gerar sequências de números pseudoaleatórios. A ideia é simples: a partir de uma semente inicial $x_0$ , cada novo valor é o resto da divisão inteira de $a \cdot x_{n-1}$ por $m$ . Em notação matemática:

x_n = (a \cdot x_{n-1}) \bmod m

Os parâmetros têm nomes consagrados: $a$ é o multiplicador, $m$ é o módulo e $x_0$ é a semente (ou valor inicial). O operador "mod" devolve o resto da divisão — por exemplo, $17 \bmod 5 = 2$ , pois $17 = 3 \times 5 + 2$ .

A pegadinha que a banca explora aqui é dupla: primeiro, o candidato pode esquecer de aplicar o módulo e calcular $3 \times 5 = 15$ como $x_1$ (o que até coincide), mas depois seguir multiplicando sem reduzir — obtendo $x_2 = 45$ e $x_3 = 135$ , e somando $15 + 45 + 135 = 195$ , que não está nas alternativas. Segundo, mesmo aplicando o módulo, é fácil errar o cálculo de $x_3$ : como $x_2 = 45$ , temos $3 \times 45 = 135$ , e $135 \bmod 120 = 15$ (pois $135 = 1 \times 120 + 15$ ). Quem esquece o módulo em $x_3$ soma $15 + 45 + 135 = 195$ ; quem aplica corretamente soma $15 + 45 + 15 = 75$ .

Vamos ao passo a passo completo:

$x_1$ : $x_1 = (3 \times 5) \bmod 120 = 15 \bmod 120 = 15$ (15 é menor que 120, então o resto é o próprio 15).
$x_2$ : $x_2 = (3 \times 15) \bmod 120 = 45 \bmod 120 = 45$ .
$x_3$ : $x_3 = (3 \times 45) \bmod 120 = 135 \bmod 120 = 15$ (pois $135 = 1 \times 120 + 15$ ).

Somando: $x_1 + x_2 + x_3 = 15 + 45 + 15 = 75$ .

NÃO CAIA NESSA!

A banca não quer que você apenas multiplique — ela quer que você aplique o módulo em cada passo. O erro clássico é calcular $x_3 = 135$ sem reduzir por 120, obtendo soma 195 (que nem aparece nas opções). Outro erro comum é achar que o módulo só se aplica quando o produto ultrapassa $m$ — o que é verdade, mas é exatamente o caso de $x_3$ . Fique atento: o resto da divisão por $m$ é obrigatório em toda iteração.

Alternativa A — ❌ Incorreta

120 seria o valor do módulo $m$ , não a soma dos três primeiros números. O candidato que confunde o módulo com o resultado da soma cai aqui. A soma correta é 75.

Alternativa B — ❌ Incorreta

15 é o valor de $x_1$ (e também de $x_3$ ), mas não a soma pedida. Quem calcula apenas o primeiro termo e para, ou soma $x_1 + x_2$ (15 + 45 = 60) e se confunde, pode marcar esta opção. A soma dos três é 75.

Alternativa C — ✅ Correta ⟵ GABARITO

Como demonstrado: $x_1 = 15$ , $x_2 = 45$ , $x_3 = 15$ , e $15 + 45 + 15 = 75$ . A alternativa reproduz exatamente o resultado da aplicação correta da recorrência com módulo.

Alternativa D — ❌ Incorreta

48 não corresponde a nenhum valor da sequência nem à soma. Pode ser resultado de um erro de cálculo, como somar $x_1 + x_2$ (60) e subtrair 12, ou confundir o produto $3 \times 15 = 45$ com outro número. Não há fundamento na recorrência.

Alternativa E — ❌ Incorreta

50 também não aparece na sequência. Poderia ser a soma de $x_1 + x_2$ (60) menos 10, ou um erro de digitação. O valor correto é 75.

PEGA ESSA DICA!

Em questões de congruência linear, sempre escreva cada iteração com o módulo explícito: $x_n = (a \cdot x_{n-1}) \bmod m$ . Isso evita o erro de esquecer o resto. Treine com valores pequenos para internalizar o padrão: o resultado nunca ultrapassa $m-1$ .

Gabarito: letra C