El Proyecto Euler: Problema 6

19/02/2009

El Proyecto Euler es una serie de problemas de programación, si quieres enterarte de que va esto, lee la introducción.

Problema 6

La suma de los cuadrados de los 10 primeros números naturales es,
1^(2) + 2^(2) + … + 10^(2) = 385

El cuadrado de la suma de los 10 primeros números naturales es,
(1 + 2 + … + 10)^(2) = 55^(2) = 3025

Por lo tanto la diferencia entre la suma de los cuadrados de los 10 primeros números naturales y el cuadrado de la suma es 3025 – 385 = 2640.

Encuentra la diferencia entre la suma de los cuadrados de los primeros 100 números naturales y el cuadrado de la suma.

Respuesta “programador ocioso”. Iteramos sobre 100 números tal cual dice el problema, primero calculando la suma de los cuadrados y enseguida el cuadrado de la suma.

Hacemos la resta final y listo.

#include <stdio.h>
#define LIMIT 100
 
int main()
{
	int i, sum = 0, square = 0;
 
	for ( i = 1; i <= LIMIT; i++ )
        {
		sum += i * i;
		square += i;
	}
 
	square *= square;
 
	printf("%d\n", square - sum);
	return 0;
}

Program exited with code #0 after 0.16 seconds.

«Anterior | Siguiente»

Hay 10 comentarios:

19/02/2009El Proyecto Euler | Pablasso dice:

[...] Problema 6 – ¿Cuál es la diferencia entre la suma de los cuadrados y el cuadrado de las sumas? «Anterior | Siguiente» Temas SimilaresEl Proyecto Euler: Problema 6 [...]
19/02/2009ceronne dice:

y por qué no haces un solo ciclo?
19/02/2009pablasso dice:

Por tonto :-P *cambiado*
20/02/2009Gunnar dice:

Umh… Hice esto para decir “para que vean la diferencia en rendimiento”… Pero me sorprende cuánto tiempo te tomó esto en C. Ira, copiando exactamente tu procedimiento:

$ time ruby -e ’sum=0;square=0;(1..100).each {|i| sum += i*i;square += i};square *= square; puts “Suma de cuadrados: %d Cuadrado de sumas: %d Diferencia: %d” % [sum, square, square-sum]‘
Suma de cuadrados: 338350 Cuadrado de sumas: 25502500 Diferencia: 25164150

real 0m0.009s
user 0m0.008s
sys 0m0.000s

Y en Perl:
$ time perl -e ‘$sum=0; += $i} $square *= $square; printf “Suma de cuadrados: %d Cuadrado de sumas: %d Diferencia: %d\n”, $sum, $square, $square – $sum;’
Suma de cuadrados: 338350 Cuadrado de sumas: 25502500 Diferencia: 25164150

real 0m0.006s
user 0m0.004s
sys 0m0.000s

Los tiempos son tan bajos que a cada ejecución llegan a variar muy fuertemente, aunque se ‘real’ mantiene alrededor de los .009 y .006.
20/02/2009pablasso dice:

mmm.. Ahora que lo mencionas, el tiempo lento de arriba creo que se debe a algún proceso extra ya que lo estaba corriendo dentro de textmate (shame on me, ahora lo evitaré).

Los tiempos con time desde la consola son estos:

real 0m0.003s
user 0m0.001s
sys 0m0.002s

16/05/2010fitorec dice:

Remplanteando el problema con N=100 a mi entender la suma de los cuadrados de los N primeros números naturales seria:

sum = 1^(2) + 2^(2) + … + N^(2)

Y el cuadrado de la suma de los 10 primeros números naturales es:

square = (1 + 2 + … + N)^(2)
donde ’sum’ y ’square’ refieren a las variables del código inicial de Pablasso, donde para quare se puede evitar las iteraciones al sustituir por una expresión algebraica:

Empezando por la parte de (1 + 2 + … + N) esto es N *(N+1)/2 ) lo cual al sustiuir en square:

square = (1 + 2 + … + N)^2 = (N *(N+1)/2)^2
= ((N+1)*(N/2))^2 = (N+1)*(N+1)*(N/2)*(N/2)
Al insertar el trinomio (N+1)*(N+1) = N*N+2N+1 esto queda:
square = (N*N+2N+1) * (N*N /4)

Creo que se puede optimizar un poco mas si analizamos la parte de sum pero por el momento no se me ocurre nada, sin mas dejo una solución la cual considero q todavía se puede mejorar.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include 
#define TOP 100
 
int main()
{
        int i, sum = 0, square = 0;
 
        for ( i = 1; i <= TOP; i++ )
                sum += i * i;
 
        square = (TOP*TOP + 2*TOP+1) * (TOP*TOP/4);
        printf("%d\n", square - sum);
        return 0;
}

16/05/2010pablasso dice:

Eres grande fitorec! muchas gracias por tus dos respuestas :)

4/06/2010luis alfosno jimenez mejia dice:

porque no utilizar la formula n(n+1)/2 y n(n+1)(2n+1)/6

#include
#include
#include
 
using namespace std;
 
int main()
{
int k,n,l,m;
 
cout<<"introducir el limite de laserie"<<n;
k=n(n+1)/2;
l=n(n+1)(2n+1)/6
m=k*k-l;
cout<<"el rersultado de la sumatoria de los numeros enteros  al cuadrado menos la sumatoria de los cuadrados es"<<", "<<m<<endl;
getch();
return 0;
}

6/06/2010fitorec dice:
Así es como bien lo comenta Luis Mejia la suma de los cuadrados (que era la parte que me creaba dudas) se puede optimizar con la formula de dicha sucesión, que yo creo que es el punto clave para resolver este problema(si es que no esta resuelta ya):

En mi ultimo comentario habia dejado el cuadrado de la sumas de 1 a N como:

square = (N*N+2N+1) * (N^2 /4)

Y como bien menciona Mejia la suma de los cuadrados seria:

sum = 1^(2) + 2^(2) + … + N^(2) = N(N+1)(2N+1)/6

Por lo tanto la diferencia entre la suma de los cuadrados de los N primeros números naturales y el cuadrado de la suma seria:

square – sum = [(N^2+2N+1) * (N^2 /4)] – [N(N+1)(2N+1)/6]

Si simplificamos esta diferencia asta llevarlo a una expresión polinomial.
square – sum = [(N^2+2N+1) * (N^2 /4)] – [N(N+1)(2N+1)/6]

= N/2 ( [ (N /2) (N^2+2N+1)] – [(1/3)(N+1)(2N+1)] )
= N/2( [(1/2)N^3 + N^2 + N/2] – [(1/3)(2N^2 + 3N +1)])
= N/2[(1/2)N^3 + (1-2/3)N^2 + (1/2 - 1)N - 1/3]
= N/2[(1/2)N^3 + (1/3)N^2 - (1/2)N - 1/3]

Al codificar esto en C quedaría como:
1 2 3 4 5 6
#define TOP 100 int main() { printf("%d\n", (TOP*TOP*TOP/2 + TOP*TOP/3 - TOP/2 - 1/3)*TOP/2); return 0; }
9/06/2010pablasso dice:

Hey, gracias por sus contribuciones Luis y Fito. Mi tonto sistema de comentarios capa los textos con código (algún día lo arreglare.. algún día) pero ya están arreglados los suyos

Escribe tu comentario:

Los mas frikis pueden suscribirse a los comentarios por RSS.

El Proyecto Euler: Problema 6

Problema 6

Hay 10 comentarios:

Escribe tu comentario:

Blogs Amigos

Minube