[Problema Reto C/C++] Sumatoria de Rangos de Impares

[AlbertoBSD]

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:

Código [Seleccionar] Expandir

2
5
10
1
5

Ejemplo de salida

Código [Seleccionar] Expandir

Caso 1: 21
Caso 2: 8




La solucion que muchos aplican es codigo:

Código (c) [Seleccionar] Expandir


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:

Código (c) [Seleccionar] Expandir


#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

[ivancea96]

Yo si no está ofuscado, no me parece correcto.

Código (cpp) [Seleccionar] Expandir

#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));
}

[AlbertoBSD]

Yo si no está ofuscado, no me parece correcto.

Código (cpp) [Seleccionar] Expandir

#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!!

[jvm1994]

Me gustaría saber si podrían explicarme el código de la función que compartió ivancea96

Disculpen la molestia.

[ivancea96]

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

[AlbertoBSD]

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!