# Ciclos for

## Ciclo for del primer tipo

Si tenemos un ciclo for de la forma:

for(int i = a; i <= b; i += c){
	...
}

Donde $a \leq b$, entonces se cumple que $a \leq i \leq b$. Como va incrementando de $c$ en $c$, entonces podríamos decir que $i = a + c \cdot (n-1)$ para $n$ un entero positivo ($n = 1, 2, \ldots$). De esta forma, $n$ nos indica cuántas veces se ejecuta el ciclo $\texttt{for}$. Entonces el objetivo es hallar el rango de $n$.

Tenemos que $a \leq a + c \cdot (n-1) \leq b$, separando:

$$
\begin{align}
a + c \cdot (n-1) &\leq b \\
c \cdot (n-1) &\leq b-a \\
n - 1 &\leq \dfrac{b-a}{c} \\
n &\leq 1 + \dfrac{b-a}{c}
\end{align}
$$

$$
\begin{align}
a &\leq a + c \cdot (n-1) \\
0 &\leq c \cdot (n-1) \\
0 &\leq n-1 \\
1 &\leq n \\
n &\geq 1
\end{align}
$$

Por lo tanto, el valor máximo que puede tomar $n$ es $1 + \dfrac{b-a}{c}$, más precisamente, el número de iteraciones es $\lfloor 1 + \dfrac{b-a}{c} \rfloor$.

Ejemplo: el siguiente código:

for(int i = 3; i <= 50; i += 2){
	cout << "Holi\n";
}

Imprimirá $\lfloor 1 + \dfrac{50-3}{2} \rfloor = 24$ veces la palabra "holi".

**Trucazo:** el siguiente ciclo for:

for(int i = a; i < b; i += c){
	....
}

es equivalente a:

for(int i = a; i <= b-1; i += c){
	....
}

## Ciclo for del segundo tipo
Si tenemos un ciclo for de la forma:

for(int i = a; i <= b; i *= c){
	...
}

Ahora vemos que $i$ se multiplica de $c$ en $c$, entonces proponemos algo muy similar: $i = a \cdot c^{n-1}$. Ahora tenemos que:
$$
\begin{align}
i &\leq b \\
a \cdot c^{n-1} &\leq b \\
c^{n-1} &\leq \dfrac{b}{a} \\
n &\leq 1 + \log_c \left( \dfrac{b}{a} \right)
\end{align}
$$

Y bajo el argumento del primer tipo de ciclo for, tenemos que el número de repeticiones es $\left\lfloor 1 + \log_c \left( \dfrac{b}{a} \right) \right\rfloor$.

Ejemplo, ¿cuántas veces se imprimirá la palabra "Algoritmos" en el siguiente ciclo for?:

for(int i = 10; i < n*5; i *= 2){
	printf("Algoritmos\n");
}

Tenemos que $a = 10$, $b=5n-1$ y $c=2$, entonces las repeticiones son $\left\lfloor 1 + \log_2 \left( \dfrac{5n-1}{10} \right) \right\rfloor$.

## Ciclo for del tercer tipo

for(int i = a; i >= b; i -= c){
	...
}

Donde $a \geq b$, es casi equivalente al del primer tipo, pero falla en algunos casos. Tenemos que $a \geq i \geq b$. Entonces podemos proponer $i = a - c \cdot (n-1)$, pues va decrementando de $c$ en $c$. Entonces:
$$
\begin{align}
a - c \cdot (n-1) &\geq b \\
a - b &\geq c \cdot (n-1) \\
1 + \dfrac{a - b}{c} &\geq n \\
n &\leq 1 + \dfrac{a - b}{c}
\end{align}
$$
Por lo tanto, el número de repeticiones es $\left\lfloor 1 + \dfrac{a - b}{c} \right\rfloor$.

**Trucazo:** el siguiente ciclo for:

for(int i = a; i > b; i -= c){
	....
}

es equivalente a:

for(int i = a; i >= b+1; i -= c){
	....
}

## Ciclo for del cuarto tipo

for(int i = a; i >= b; i /= c){
	...
}

**Warning**: notemos que en C y en C++ la división siempre se hace entera, es decir, una instrucción del tipo $\texttt{int a = b/c;}$, donde $b$ y $c$ son enteros, realmente hace $a := \left\lfloor \dfrac{b}{c} \right\rfloor$.

Veamos cómo se comporta la $i$ al final de algunas iteraciones:
- 1°: $i := \left\lfloor \dfrac{i}{c} \right\rfloor$
- 2°: $i := \left\lfloor \dfrac{\left\lfloor \dfrac{i}{c} \right\rfloor}{c} \right\rfloor$
- 3°: ...
Pero afortunadamente, tenemos la siguiente propiedad: $\left\lfloor \dfrac{\left\lfloor \dfrac{x}{y} \right\rfloor}{z} \right\rfloor = \left\lfloor \dfrac{x}{yz} \right\rfloor$, donde $x,y,z$ son enteros.

Por lo tanto, podemos proponer que $i = \left\lfloor \dfrac{a}{c^{n-1}} \right\rfloor$. Entonces:
$$
\begin{align}
\left\lfloor \dfrac{a}{c^{n-1}} \right\rfloor &\geq b \\
b &\leq \left\lfloor \dfrac{a}{c^{n-1}} \right\rfloor \\
\end{align}
$$

Tenemos que $\lfloor x \rfloor \leq x$ para cualquier $x \in \mathbb{R}$. Entonces:
$$
\begin{align}
b &\leq \left\lfloor \dfrac{a}{c^{n-1}} \right\rfloor \leq \dfrac{a}{c^{n-1}} \\
b &\leq \dfrac{a}{c^{n-1}} \\
b \cdot c^{n-1} &\leq a \\
c^{n-1} &\leq \dfrac{a}{b} \\
n &\leq 1 + \log_c \left( \dfrac{a}{b}\right)
\end{align}
$$
Por lo tanto, el número de repeticiones es $\left\lfloor 1 + \log_c \left( \dfrac{a}{b}\right) \right\rfloor$.

## Ejemplo de for anidado

for(int j = n; j > 1; j /= 2){
	if(j < n/2){
		for(int i = 0; i < n; i += 2){
			printf("Ti amo Tafnes\n");
		}
	}
}

**Observación:** Los dos ciclos for son independientes entre sí, por lo tanto, los podemos analizar de forma independiente.

Analicemos el segundo for: vemos que es del primer tipo con $a=0$, $b=n-1$ y $c=2$, entonces el número de repeticiones es $\left\lfloor 1 + \dfrac{b-a}{c} \right\rfloor = \left\lfloor 1 + \dfrac{n-1}{2} \right\rfloor = \left\lfloor \dfrac{n+1}{2} \right\rfloor$.

Ahora veamos el for exterior: es un for del cuarto tipo pero con una condición adicional: $j < \lfloor n/2 \rfloor$, y con la condición inicial de $j > 1$, entonces vemos que $1 < j < \lfloor n/2 \rfloor$, que se puede reexpresar como $2 \leq j \leq \lfloor n/2 \rfloor-1$.

Como es un for del cuarto tipo, podemos proponer que $j = \left\lfloor \dfrac{n}{2^{m-1}} \right\rfloor$, donde ahora $m$ controla el número de iteración. Entonces:
$$
\begin{align}
\dfrac{n}{2^{m-1}} &\leq \lfloor n/2 \rfloor-1 \\
n &\leq 2^{m-1} (\lfloor n/2 \rfloor-1) \\
\dfrac{n}{\lfloor n/2 \rfloor-1} &\leq 2^{m-1} \\
m &\geq 1 + \log_2 \left( \dfrac{n}{\lfloor n/2 \rfloor-1} \right) \\
m &\geq 3 \quad \mbox{se comprobó por al ahí se va :v}
\end{align}
$$

Y también:
$$
\begin{align}
2 &\leq \dfrac{n}{2^{m-1}} \\
2 \cdot 2^{m-1} &\leq n \\
2^m &\leq n \\
m &\leq \log_2(n)
\end{align}
$$

Por lo tanto, $3 \leq m \leq \log_2(n)$, es decir, el número de iteraciones válidas del for exterior es $\lfloor \log_2(n) \rfloor - 2$.

Finalmente, el número de impresiones totales se obtiene multiplicando: $\left\lfloor \dfrac{n+1}{2} \right\rfloor \cdot (\lfloor \log_2(n) \rfloor - 2)$. Esta fórmula es válida para $n \geq 4$, pues para $n \leq 3$ hay cero iteraciones exteriores.

## Ejemplo de for anidado
Hallar el número de veces que se imprime la palabra *Algoritmos* en el siguiente código:

for(int i = 0; i < n*5; i += 2){
	for(int j = 0; j < 2*n; ++j){
		for(int k = j; k < n; ++k){
			printf("Algoritmos\n");
		}
	}
}

Analicemos los ciclos for desde el más interno hasta el más externo:
- El tercer ciclo es del primer tipo con parámetros $a=j$, $b=n-1$ y $c=1$, entonces el número de repeticiones es $n-j$. Vemos que depende del parámetro $j$ del segundo ciclo, entonces necesitamos que $j \leq n$.
- El segundo ciclo cumple que $0 \leq j \leq 2n-1$, pero ya sabíamos del tercer ciclo que $j \leq n$, por lo tanto nos quedamos con $j \leq n$, y de esa forma vemos que las iteraciones que cumplen con $n+1 \leq j \leq 2n-1$ no alcanzarán a ejecutar el tercer ciclo. Por lo tanto, el número de impresiones hasta este ciclo es de:
$$
\begin{align}
\sum_{j=0}^{n} (n-j) &= n + (n-1) + \cdots + 1 + 0 \\
&= \sum_{j=0}^{n} j \\
&= \dfrac{n(n+1)}{2}
\end{align}
$$
- El primer ciclo es del primer tipo con parámetros $a=0$, $b=5n-1$ y $c=2$, por lo que el número de iteraciones es $\left\lfloor \dfrac{5n+1}{2} \right\rfloor$. Como es independiente de los otros dos, basta con multiplicar el número de iteraciones de este ciclo con el resultado anterior.
- Por lo tanto, el número de impresiones en total es: $\left\lfloor \dfrac{5n+1}{2} \right\rfloor \times \dfrac{n(n+1)}{2}$.

## Ejemplo de for anidado
Hallar el número de veces que se imprime la palabra *Algoritmos* en el siguiente código:

for(int i = 1; i < 4*n; i *= 2){
	for(int j = i; j < 5*n; j += 3){
		printf("Algoritmos\n");
	}
}

- El segundo ciclo es del primer tipo con parámetros $a=i$, $b=5n-1$ y $c=3$. Entonces, el número de impresiones aquí será de $\left\lfloor \dfrac{5n+2-i}{3} \right\rfloor$.
- El primer ciclo es del tercer tipo con parámetros $a=1$, $b=4n-1$ y $c=2$. Vamos a proponer $i=2^{m-1}$, donde $m$ es el número de iteración. Como $i < 4n$, pero $i < 5n$ por el segundo ciclo, entonces nos quedamos con $i < 4n$. Sabemos entonces que $1 \leq m \leq 1 + \left\lfloor \log_2(4n-1) \right\rfloor$. Sea $l=1 + \left\lfloor \log_2(4n-1) \right\rfloor$, entonces la respuesta es:
$$
\begin{align}
\sum_{m=1}^{l} \left\lfloor \dfrac{5n+2-2^{m-1}}{3} \right\rfloor
\end{align}
$$
No hay una fórmula exacta, pero podemos aproximar como:
$$
\begin{align}
\sum_{m=1}^{l} \dfrac{5n+2-2^{m-1}}{3} &= \sum_{m=1}^{l} \dfrac{5n+2}{3} - \sum_{m=1}^{l} \dfrac{2^{m-1}}{3} \\
&= l \cdot \dfrac{5n+2}{3} - \dfrac{2^{l}-1}{3} \\
&= \dfrac{1}{3}[l \cdot (5n+2)-2^l+1] \\
&\approx \left\lfloor \dfrac{1}{3} \left[ (1 + \left\lfloor \log_2(4n-1) \right\rfloor) \cdot (5n+2) - 2^{1 + \left\lfloor \log_2(4n-1) \right\rfloor} + 1 \right] \right\rfloor
\end{align}
$$