formula - ¿Cuál es la prueba de(N – 1)+(N – 2)+(N – 3)+…+1=N*(N – 1)/2

proof

Question

Obtuve esta fórmula de un libro de estructura de datos en el algoritmo de clasificación de burbujas.

Sé que somos (n-1) * (n veces), pero ¿por qué la división por 2?

¿Puede alguien explicarme esto o darme la prueba detallada?

Gracias

Answer 1

Sé que somos (n-1) * (n veces), pero ¿por qué la división por 2?

Es solo (n - 1) * n si usas una burbuja de burbujas ingenua. Puede obtener un ahorro significativo si observa lo siguiente:

• Después de cada comparación e intercambio, el elemento más grande que haya encontrado estará en el último lugar en el que estuvo.

• Después de la primera pasada, el elemento más grande estará en la última posición; después del paso k ^th , el elemento k ^th más grande estará en la k ^th última posición.

Por lo tanto, no tiene que ordenar todo el asunto cada vez: solo necesita ordenar n - 2 elementos la segunda vez, n - 3 elementos la tercera vez, y así sucesivamente. Eso significa que el número total de comparaciones / swaps que tienes que hacer es (n - 1) + (n - 2) + ... Esta es una serie aritmética , y la ecuación para el número total de veces es (n - 1) * n / 2.

Ejemplo: si el tamaño de la lista es N = 5, entonces hace 4 + 3 + 2 + 1 = 10 swaps, y observa que 10 es lo mismo que 4 * 5/2.

Answer 2

Aquí hay una prueba por inducción, considerando los términos de N , pero es lo mismo para N - 1 :

Para N = 0 la fórmula es obviamente verdadera.

Supongamos que 1 + 2 + 3 + ... + N = N(N + 1) / 2 es cierto para algunos N naturales.

Demostraremos que 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 también es cierto al usar nuestro supuesto anterior:

1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2 .

Así que la fórmula se mantiene para todo N

Answer 3

Empieza con el triángulo ...

    *
   **
  ***
 ****

representando 1 + 2 + 3 + 4 hasta ahora. Cortar el triángulo por la mitad a lo largo de una dimensión ...

     *
    **
  * **
 ** **

Gire la parte más pequeña 180 grados y péguela sobre la parte más grande ...

    **
    * 

     *
    **
    **
    **

Cerrar la brecha para obtener un rectángulo.

A primera vista, esto solo funciona si la base del rectángulo tiene una longitud uniforme, pero si tiene una longitud impar, simplemente corta la columna del medio a la mitad; todavía funciona con una media unidad de ancho dos veces más alto ( todavía área entera) tira en un lado de su rectángulo.

Cualquiera que sea la base del triángulo, el ancho de su rectángulo es (base / 2) y la altura es (base + 1) , dando ((base + 1) * base) / 2 .

Sin embargo, mi base es su n-1 , ya que la ordenación de las burbujas compara un par de elementos a la vez y, por lo tanto, itera solo en las posiciones (n-1) del primer bucle.

Answer 4

Esta es una prueba bastante común. Una forma de demostrar esto es usar la inducción matemática. Aquí hay un enlace: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

Answer 5

Intenta hacer pares de números del conjunto. Lo primero + lo último; el segundo + el anterior al último. Significa n-1 + 1; n-2 + 2. El resultado es siempre n. Y como están sumando dos números, solo se pueden hacer pares (n-1) / 2 a partir de números (n-1).

Así que es como (N-1) / 2 * N.

Answer 6

Suma de progresión aritmética.

(A1 + AN) / 2 * N = (1 + (N-1)) / 2 * (N-1) = N * (N-1) / 2

Answer 7

Supongamos que n = 2. Entonces tenemos 2-1 = 1 en el lado izquierdo y 2 * 1/2 = 1 en el lado derecho.

Denote f (n) = (n-1) + (n-2) + (n-3) + ... + 1

Ahora supongamos que hemos probado hasta n = k. Entonces tenemos que probar para n = k + 1.

en el lado izquierdo tenemos k + (k-1) + (k-2) + ... + 1, así que es f (k) + k

En el lado derecho tenemos entonces (k + 1) * k / 2 = (k ^ 2 + k) / 2 = (k ^ 2 + 2k - k) / 2 = k + (k-1) k / 2 = k f (k)

Entonces esto tiene que mantenerse para cada k, y esto concluye la prueba.

Answer 8

Ver los números del triángulo .

Answer 9

(N-1) + (N-2) +...+ 2 + 1 es una suma de N-1 elementos. Ahora reordene los elementos para que después de lo primero venga el último, luego el segundo, luego el segundo para durar, es decir (N-1) + 1 + (N-2) + 2 +.. La forma en que se ordenan los elementos ahora puede ver que cada uno de esos pares es igual a N (N-1 + 1 es N, N-2 + 2 es N). Como hay elementos N-1, hay (N-1) / 2 pares. Entonces, está agregando N (N-1) / 2 veces, por lo que el valor total es N*(N-1)/2 .