elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: 4n4lDetector v1.3: herramienta de análisis estático de malware


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse)
| | |-+  [Problema Reto C/C++] Sumatoria de Rangos de Impares
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Problema Reto C/C++] Sumatoria de Rangos de Impares  (Leído 232 veces)
AlbertoBSD
💻🌎🌍🌏🌐 NWO📱
Colaborador
***
Desconectado Desconectado

Mensajes: 2.998


Yo soy malo, y eso es bueno.


Ver Perfil WWW
[Problema Reto C/C++] Sumatoria de Rangos de Impares
« en: 8 Marzo 2017, 22:24 »

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:
2
5
10
1
5

Ejemplo de salida

Código:
Caso 1: 21
Caso 2: 8




La solucion que muchos aplican es codigo:

Código
  1. int T= 0,a = 0,b= 0,i,suma;
  2. scanf("%d\n",&T);
  3. i = 0;
  4. while(i < T) {
  5. scanf("%d\n",&a);
  6. scanf("%d\n",&b);
  7. suma = 0;
  8. while(a <= b) {
  9. if(a % 2 == 1) {
  10. suma += a;
  11. }
  12. a++;
  13. }
  14. printf("Case %i:%i\n",i+1,suma);
  15. i++;
  16. }
  17.  

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
  1. #include<stdio.h>
  2.  
  3. int main() {
  4. int T= 0,a = 0,b= 0,i;
  5. int rango_a,rango_b;
  6. scanf("%d\n",&T);
  7. i = 0;
  8. while(i < T) {
  9. scanf("%d\n",&a);
  10. scanf("%d\n",&b);
  11. if(a % 2 != 0) {
  12. a-=1;
  13. }
  14. rango_a = (((a/2)*a)/2); // Suma de Impares desde 0 hasta a-1
  15. if(b % 2 == 0) {
  16. rango_b = (((b/2)*b)/2); //Suma de Impares desde 0 hasta b
  17. }
  18. else {
  19. rango_b = ((((b+1)/2)*(b+1))/2); //Suma de Impares desde 0 hasta b
  20. }
  21. printf("Case %i:%i\n",i+1,rango_b-rango_a);
  22. i++;
  23. }
  24. return 0;
  25. }
  26.  



Consideren el siguiente archivo de Entrada 10000 veces rangos de [0,10000]
http://pastebin.com/raw/nK0xQ6cz


En línea

ivancea96


Conectado Conectado

Mensajes: 2.925


ASMático


Ver Perfil WWW
Re: [Problema Reto C/C++] Sumatoria de Rangos de Impares
« Respuesta #1 en: 8 Marzo 2017, 23:09 »

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

Código
  1. #include <cstdio>
  2.  
  3. int getResult(int a, int b){
  4. return (b*b+(b&1)*(b*2+1)-a*a+(a&1)*(a*2-1))>>2;
  5. }
  6.  
  7. int main(){
  8. printf("%i\n",getResult(5, 20));
  9. printf("%i\n",getResult(5, 19));
  10. printf("%i\n",getResult(4, 20));
  11. printf("%i\n",getResult(4, 20));
  12. }


En línea

AlbertoBSD
💻🌎🌍🌏🌐 NWO📱
Colaborador
***
Desconectado Desconectado

Mensajes: 2.998


Yo soy malo, y eso es bueno.


Ver Perfil WWW
Re: [Problema Reto C/C++] Sumatoria de Rangos de Impares
« Respuesta #2 en: 9 Marzo 2017, 00:12 »

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

Código
  1. #include <cstdio>
  2.  
  3. int getResult(int a, int b){
  4. return (b*b+(b&1)*(b*2+1)-a*a+(a&1)*(a*2-1))>>2;
  5. }
  6.  

Barbaro y con Operadores de bits!!! Bravo!!
En línea

jvm1994

Desconectado Desconectado

Mensajes: 26



Ver Perfil
Re: [Problema Reto C/C++] Sumatoria de Rangos de Impares
« Respuesta #3 en: 14 Marzo 2017, 01:46 »

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

Disculpen la molestia.
En línea

"La posibilidad de crear tu mundo."
Código
  1. int main()
  2. {
  3. eMundo * Own = world_new();
  4. if(Own != NULL)
  5. {
  6.    world_create(Own);
  7. }
  8.  
  9. return 0;
  10. }
ivancea96


Conectado Conectado

Mensajes: 2.925


ASMático


Ver Perfil WWW
Re: [Problema Reto C/C++] Sumatoria de Rangos de Impares
« Respuesta #4 en: 14 Marzo 2017, 13:37 »

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
En línea

AlbertoBSD
💻🌎🌍🌏🌐 NWO📱
Colaborador
***
Desconectado Desconectado

Mensajes: 2.998


Yo soy malo, y eso es bueno.


Ver Perfil WWW
Re: [Problema Reto C/C++] Sumatoria de Rangos de Impares
« Respuesta #5 en: 14 Marzo 2017, 17:16 »

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!
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Problema con programa numeros pares e impares:P « 1 2 »
.NET
<sylar> 18 19,688 Último mensaje 17 Abril 2009, 03:41
por <sylar>
sumatoria « 1 2 »
Programación C/C++
mapers 12 5,078 Último mensaje 6 Julio 2009, 18:38
por Choclito
Sumatoria con while,,,
Java
solNegr0; 7 2,580 Último mensaje 28 Noviembre 2010, 19:16
por solNegr0;
[RETO+Python] Buscando rangos « 1 2 »
Scripting
Novlucker 13 3,581 Último mensaje 31 Enero 2011, 18:30
por Karcrack
Sumatoria c++
Programación C/C++
Ezeqro 2 279 Último mensaje 27 Septiembre 2016, 19:41
por MAFUS
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines