Rompecabezas | Programa para encontrar el número de casillas en un tablero de ajedrez

Rompecabezas : se le proporciona un tablero de ajedrez y se le pide que encuentre el número de cuadrados en él. Un tablero de ajedrez es un tablero con cuadrículas de 8 x 8 como se representa a continuación. 

Solución : Mirando de cerca el tablero de ajedrez podemos ver que además del cuadrado de 1 x 1, puede haber una combinación de 2 x 2, 3 x 3, 4 x 4, 5 x 5, 6 x 6, 7 x 7, y 8 x 8 cuadrados también. Para obtener el número total de cuadrados necesitamos encontrar todos los cuadrados formados. 

1 x 1: 8 * 8 = 64 squares.
2 x 2: 7 * 7 = 49 squares.
3 x 3: 6 * 6 = 36 squares.
4 x 4: 5 * 5 = 25 squares.
5 x 5: 4 * 4 = 16 squares.
6 x 6: 3 * 3 = 9 squares.
7 x 7: 2 * 2 = 4 squares.
8 x 8: 1 * 1 = 1 square.

Por tanto, tenemos en total = 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1 = 204 casillas en un tablero de ajedrez.
 

Proceso general
Dada una cuadrícula de nxn, cuente los cuadrados en ella. 

Ejemplos: 

Input: n = 2
Output: 5 (4 squares of 1 unit + 1 square of 2 units)

Input: n = 3
Output: 14 (9 squares of 1 unit + 4 square of 2 units 
                                + 1 square of 1 unit) 

Para una cuadrícula de tamaño n*n, el número total de cuadrados formados es: 

1^2 + 2^2 + 3^2 + ... + n^2 = n(n+1)(2n+1) / 6 

A continuación se muestra la implementación de la fórmula anterior. Dado que el valor de n*(n+1)*(2n+1) puede causar un desbordamiento para valores grandes de n, a continuación se presentan algunos trucos interesantes utilizados en el programa. 

1. long int se usa a cambio.
2. n * (n + 1) / 2 se evalúa primero ya que el valor n*(n+1) siempre será un múltiplo de 2.

Tenga en cuenta que aún puede ocurrir un desbordamiento, pero los trucos anteriores solo reducen las posibilidades de un desbordamiento.  

// C++  find number of squares in a
// chessboard
#include <bits/stdc++.h>
using namespace std;
 
// Function to return count of squares;
long long int countSquares(int n)
{
  return (n * (n + 1) / 2) * (2 * n + 1) / 3;
}
 
// Driver Code
int main()
{
 
  int n = 4;
  cout << countSquares(n);
  return 0;
}
 
//vermay87    `

// Java  find number of squares in a
// chessboard
 
 
class GFG
{
    // Function to return count of squares;
    static int countSquares(int n)
    {
        // A better way to write n*(n+1)*(2n+1)/6
        return (n * (n + 1) / 2) * (2 * n + 1) / 3;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 3;
        System.out.println("Count of squares is "
                           +countSquares(n));
    }
}
 
// This code is contributed by Anant Agarwal.

# python code to find number
# of squares in a chessboard
 
# Function to return count
# of squares;
def countSquares(n):
     
    # better way to write
    # n*(n+1)*(2n+1)/6
    return ((n * (n + 1) / 2)
           * (2 * n + 1) / 3)
     
# Driver code
n = 4
print("Count of squares is ",
              countSquares(n))
 
# This code is contributed by sam007.

// C# find number of squares in a
// chessboard
using System;
 
public class GFG {
     
    static int countSquares(int n)
    {
        // A better way to write
        // n*(n+1)*(2n+1)/6
        return (n * (n + 1) / 2)
                * (2 * n + 1) / 3;
    }
     
    // Driver code
    public static void Main ()
    {
        int n = 4;
        Console.WriteLine("Count of"
                     + "squares is "
                 + countSquares(n));
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP program to find number
// of squares in a chessboard
 
// Function to return
// count of squares;
function countSquares($n)
{
    // A better way to
    // write n*(n+1)*(2n+1)/6
    return ($n * ($n + 1) / 2) *
               (2 * $n + 1) / 3;
}
 
// Driver Code
$n = 4;
echo "Count of squares is " ,
            countSquares($n);
 
// This code is contributed
// by nitin mittal.
?>

<script>
 
// Java  find number of squares in a
// chessboard
 
// Function to return count of squares;
function countSquares( n)
{
    // A better way to write n*(n+1)*(2n+1)/6
    return (n * (n + 1) / 2) * (2*n + 1) / 3;
}
 
// Driver Code
 
let n = 4;
document.write("Count of squares is " + countSquares(n));
 
</script>

Producción:  

Count of squares is 30

Este artículo es una contribución de Rishabh . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.