Buenas!
Este problema lo vi en otro Foro, pero me gustaria ampliarlo y Discutir sobre la eficiencia del codigo contra la "FORMA FACIL".
Problema
Tu tienes que proporcionar la Suma de Todos los numeros Impares contenidos en un rango de numeros dados [a,b]
Ejemplo:
a = 5
b = 10
Numeros impares en el rango [5,10] = { 5,7,9 };
Sumatoria 5 +7 + 9 = 21
Ejemplo
a = 1
b = 5
Numeros impares en el rango [1,5] = { 1,3,5 };
Sumatoria 1+3 +5 = 9
Entrada del programa:
Pueden existir multiples casos para probar, La primera Linea contiene el valor T Donde T es el numero de casos a realizar, 1 <= T <= 100000
Y seguido de T Casos, Cada Caso consiste en dos Numeros enteros a, b donde 0 <= a <=b <=10000. En dos lineas sepaadas (1 linea por numero entero)
Ejemplo de Entrada:
2
5
10
1
5
Ejemplo de salida
Caso 1: 21
Caso 2: 8
La solucion que muchos aplican es codigo:
int T= 0,a = 0,b= 0,i,suma;
scanf("%d\n",&T);
i = 0;
while(i < T) {
scanf("%d\n",&a);
scanf("%d\n",&b);
suma = 0;
while(a <= b) {
if(a % 2 == 1) {
suma += a;
}
a++;
}
printf("Case %i:%i\n",i+1,suma);
i++;
}
Sin embargo en mi punto de vista es bastante ineficiente, ya que si te dan 10000 Veces el peor de los casos de [0,10000] (Pongo 10000 y no 100000 para que no desborde el entero de 32 bits...) En dado caso tu programa ejecutaria un ciclo de 10000 * 10000 = 100'000,000
Claro que para los procesadores modernos no hay tanta direrencia entre 100, Mi aproximacion fue sacar la formula para determinar la sumaria de los impares del rango de 0 a A y del rango de 0 a B
Y En teoria solo entro al ciclo T veces:
#include<stdio.h>
int main() {
int T= 0,a = 0,b= 0,i;
int rango_a,rango_b;
scanf("%d\n",&T);
i = 0;
while(i < T) {
scanf("%d\n",&a);
scanf("%d\n",&b);
if(a % 2 != 0) {
a-=1;
}
rango_a = (((a/2)*a)/2); // Suma de Impares desde 0 hasta a-1
if(b % 2 == 0) {
rango_b = (((b/2)*b)/2); //Suma de Impares desde 0 hasta b
}
else {
rango_b = ((((b+1)/2)*(b+1))/2); //Suma de Impares desde 0 hasta b
}
printf("Case %i:%i\n",i+1,rango_b-rango_a);
i++;
}
return 0;
}
Consideren el siguiente archivo de Entrada 10000 veces rangos de [0,10000]
http://pastebin.com/raw/nK0xQ6cz
Yo si no está ofuscado, no me parece correcto.
#include <cstdio>
int getResult(int a, int b){
return (b*b+(b&1)*(b*2+1)-a*a+(a&1)*(a*2-1))>>2;
}
int main(){
printf("%i\n",getResult(5, 20));
printf("%i\n",getResult(5, 19));
printf("%i\n",getResult(4, 20));
printf("%i\n",getResult(4, 20));
}
Cita de: ivancea96 en 8 Marzo 2017, 23:09 PM
Yo si no está ofuscado, no me parece correcto.
#include <cstdio>
int getResult(int a, int b){
return (b*b+(b&1)*(b*2+1)-a*a+(a&1)*(a*2-1))>>2;
}
Barbaro y con Operadores de bits!!! Bravo!!
Me gustaría saber si podrían explicarme el código de la función que compartió ivancea96
Disculpen la molestia.
Es casi el mismo que el de Alberto, pero en vez de poner los if, sumando (b%2)*(...). Bueno, y luego cambié el b%2 por b&1.
Se resuelve la ecuación, y dará (.....)/4, que es lo mismo que (....)>>2.
A veces, resolver una ecuación, ofusca mucho el código jaja
Cita de: ivancea96 en 14 Marzo 2017, 13:37 PM
A veces, resolver una ecuación, ofusca mucho el código jaja
A muchas personas no se le dan las matematicas, asi que por si sola una ecuacion podria considerarse ofuscada, ahora una ecuacion plasmada en un lenguaje y con operadores a nivel de bits ni de diga.
Cabe añadi que la ecuacion que puso ivancea96, lo hace en un solo paso. Yo lo dividi en 2 pasos para sacar el rango de 0 a A y de 0 a B para posteriormente realizar la resta.
Saludos!