Tema 6
Álgebra básica aplicada a programación
Patrón de examen
Busca fórmulas cerradas antes de usar ciclos. Si necesitas aⁿ mod m, usa exponenciación rápida. Las sumatorias cerradas convierten O(n) en O(1).
Explicación
Expresiones y precedencia
En C++ las expresiones algebraicas siguen la misma precedencia que en matemáticas:
- Paréntesis
() - Potencia (no hay operador, usar
pow()) - Multiplicación
*, división/, módulo% - Suma
+, resta-
Despeje de fórmulas (razonamiento algebraico)
En olimpiadas frecuentemente necesitas despejar antes de programar:
| Fórmula original | Despejando x |
|---|---|
| y = mx + b | x = (y - b) / m |
| ax² + bx + c = 0 | x = (-b ± √(b²-4ac)) / 2a |
| d = v × t | t = d / v |
Sumatorias útiles
| Sumatoria | Fórmula cerrada |
|---|---|
| 1 + 2 + ... + n | n(n+1)/2 |
| 1² + 2² + ... + n² | n(n+1)(2n+1)/6 |
| 1 + 2 + 4 + ... + 2ⁿ | 2ⁿ⁺¹ - 1 |
Estas fórmulas permiten calcular sumas en O(1) en vez de O(n).
Progresiones
Aritmética: a, a+d, a+2d, ... → Término n: a + (n-1)*d, Suma: n*(2a + (n-1)*d)/2
Geométrica: a, a×r, a×r², ... → Término n: a * r^(n-1), Suma: a*(r^n - 1)/(r - 1)
Exponenciación rápida
Calcular aⁿ mod m en O(log n) en vez de O(n). Esencial para números grandes con módulo.