Solución a la Tarea 2: Los Triángulos
Las desigualdades del triángulo dicen que tres números
positivos a, b y c son las longitudes de los lados
de un triángulo si y sólo si a+b
> c, b+c
> a y c+a
> b. Sabiendo esto,
existen diversas formas de resolver este problema. La más simple
de ellas consiste en efectuar tres ciclos, uno para cada uno de los
lados a, b y c desde el valor de m hasta el valor de n, y preguntar si los valores de a, b y c producidos satisfacen todas las
condiciones, es decir, si están ordenados y cumplen las
desigualdades del triángulo.
for
(a = m; a <= n; a++)
for (b = m; b <= n; b++)
for (c = m; c
<= n; c++)
if
(a <= b && b <= c && a+b > c && b+c
> a && c+a > b)
t++;
Aunque esto es correcto, resulta demasiado lento, ya que produce ternas
desordenadas. Una forma de aumentar la velocidad de nuestro programa
es, como ya vimos en clase, haciendo que b comience con el valor de a y que c comience con el valor de b:
for
(a = m; a <= n; a++)
for (b = a; b <= n; b++)
for (c = b; c
<= n; c++)
if
(a+b > c)
t++;
Observe que ya no es necesario preguntar si a, b y c están ordenados.
Además, ya no es necesario preguntar si b+c
> a ni si c+a
> b.
¿Porqué? Como la condición resultante es muy
simple, eso nos indica que puede haber una forma más
rápida de verificarla. Si cuenta con algo de tiempo libre, trate
de averiguar porqué funciona el siguiente programa
(¿Habrá uno más rápido?,
¿Habrá una fórmula?):
#include
<stdio.h>
int main(void)
{
long int a, b, c;
long int m, n, s, t = 0;
scanf("%ld%ld", &m,
&n);
for (a = m; a <= n; a++)
for (b = a; b
<= n; b++) {
s
= n - b + 1;
t
+= (a < s) ? a : s;
}
printf("%ld\n", t);
return 0;
}
Los valores de entrada y salida empleados para la evaluación
fueron los siguientes:
Entrada
Salida
2 2
1
2 5 17
5 10 55
10 20 285
20 50 5295
50 100 23425
100 200 176850
200 500 4500825
500 1000 21084250
1 1000 83708750
Para probar su tarea en UNIX, escriban la instrucción gcc triangNN.c -o triang para
compilar su programa, y la instrucción ./triang para correrlo. Algunos
errores comúnes fueron: (a) suponer que la
expresión a <= b <=
c significa lo mismo
que la expresión a <=
b && b <=
c (b) no usar variables de tipo long int (c) tratar de hacer en
un ciclo lo que se debía hacer en dos o tal vez tres.