Conteo de celdas en una array que da un número de Fibonacci cuando se agrega el conteo de celdas adyacentes

Dada una array M x N mat[][] . La tarea es contar el número de celdas buenas en la array. Una celda será buena si la suma del valor de la celda y el número de celdas adyacentes es un número de Fibonacci.
Ejemplos: 
 

Entrada: mat[][] = { 
{1, 2}, 
{3, 4}} 
Salida:
Solo las celdas mat[0][0] y mat[1][0] son ​​buenas. 
es decir, (1 + 2) = 3 y (3 + 2) = 5 son números de Fibonacci.
Entrada: mat[][] = { 
{1, 0, 5, 3}, 
{2, 17, 5, 6}, 
{5, 8, 15, 11}}; 
Salida:
 

Enfoque: iterar toda la array y para cada celda encontrar el recuento de celdas adyacentes. Puede haber 3 tipos de celdas, uno con 2 celdas adyacentes, uno con 3 celdas adyacentes y el resto con 4 celdas adyacentes. Sume este recuento con el valor de la celda actual y compruebe si el resultado es un número de Fibonacci. Si es así, entonces incremente el conteo.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define M 3
#define N 4
 
// Function that returns true if
// x is a perfect square
bool isPerfectSquare(long double x)
{
    // Find floating point value of
    // square root of x
    long double sr = sqrt(x);
 
    // If square root is an integer
    return ((sr - floor(sr)) == 0);
}
 
// Function that returns true
// if n is a Fibonacci number
bool isFibonacci(int n)
{
    return isPerfectSquare(5 * n * n + 4)
           || isPerfectSquare(5 * n * n - 4);
}
 
// Function to return the count of good cells
int goodCells(int mat[M][N])
{
 
    // To store the required count
    int count = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
 
            int sum = mat[i][j];
 
            // Corner cells of the matrix
            // have only 2 adjacent cells
            if ((i == 0 && j == 0)
                || (i == M - 1 && j == 0)
                || (i == 0 && j == N - 1)
                || (i == M - 1 && j == N - 1)) {
                sum += 2;
            }
 
            // All the boundary elements
            // except the corner elements
            // have only 3 adjacent cells
            else if (i == 0 || j == 0
                     || i == M - 1 || j == N - 1) {
                sum += 3;
            }
 
            // Rest of the elements have 4 adjacent cells
            else {
                sum += 4;
            }
 
            // If the sum is a Fibonacci number
            if (isFibonacci(sum))
                count++;
        }
    }
 
    return count;
}
 
// Driver code
int main()
{
    int mat[M][N] = { { 1, 0, 5, 3 },
                      { 2, 17, 5, 6 },
                      { 5, 8, 15, 11 } };
    cout << goodCells(mat);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
static int M = 3;
static int N = 4;
 
// Function that returns true if
// x is a perfect square
static boolean isPerfectSquare(long x)
{
    // Find floating point value of
    // square root of x
    double sr = Math.sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function that returns true
// if n is a Fibonacci number
static boolean isFibonacci(int n)
{
    return isPerfectSquare(5 * n * n + 4)
        || isPerfectSquare(5 * n * n - 4);
}
 
// Function to return the count of good cells
static int goodCells(int mat[][])
{
 
    // To store the required count
    int count = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
 
            int sum = mat[i][j];
 
            // Corner cells of the matrix
            // have only 2 adjacent cells
            if ((i == 0 && j == 0)
                || (i == M - 1 && j == 0)
                || (i == 0 && j == N - 1)
                || (i == M - 1 && j == N - 1))
            {
                sum += 2;
            }
 
            // All the boundary elements
            // except the corner elements
            // have only 3 adjacent cells
            else if (i == 0 || j == 0
                    || i == M - 1 || j == N - 1)
            {
                sum += 3;
            }
 
            // Rest of the elements have 4 adjacent cells
            else
            {
                sum += 4;
            }
 
            // If the sum is a Fibonacci number
            if (isFibonacci(sum))
                count++;
        }
    }
 
    return count;
}
 
    // Driver code
    public static void main (String[] args)
    {
        int mat[][] = { { 1, 0, 5, 3 },
                    { 2, 17, 5, 6 },
                    { 5, 8, 15, 11 } };
        System.out.println( goodCells(mat));
    }
}
 
// This code is contributed by anuj_67..

Python

# Python implementation of the approach
from math import ceil,sqrt,floor
M = 3
N = 4
 
# Function that returns true if
# x is a perfect square
def isPerfectSquare(x):
 
    # Find floating povalue of
    # square root of x
    sr = (sqrt(x))
 
    # If square root is an integer
    return ((sr - floor(sr)) == 0)
 
# Function that returns true
# if n is a Fibonacci number
def isFibonacci(n):
    return isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)
 
# Function to return the count of good cells
def goodCells(mat):
 
    # To store the required count
    count = 0
    for i in range(M):
        for j in range(N):
 
            sum = mat[i][j]
 
            # Corner cells of the matrix
            # have only 2 adjacent cells
            if ((i == 0 and j == 0)
                or (i == M - 1 and j == 0)
                or (i == 0 and j == N - 1)
                or (i == M - 1 and j == N - 1)):
                sum += 2
 
            # All the boundary elements
            # except the corner elements
            # have only 3 adjacent cells
            elif (i == 0 or j == 0 or i == M - 1 or j == N - 1):
                sum += 3
 
            # Rest of the elements have 4 adjacent cells
            else:
                sum += 4
 
            # If the sum is a Fibonacci number
            if (isFibonacci(sum)):
                count += 1
 
    return count
 
# Driver code
 
mat = [ [ 1, 0, 5, 3 ],
    [ 2, 17, 5, 6 ],
    [ 5, 8, 15, 11 ] ]
print(goodCells(mat))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
static int M = 3;
static int N = 4;
 
// Function that returns true if
// x is a perfect square
static bool isPerfectSquare(long x)
{
    // Find floating point value of
    // square root of x
    double sr = Math.Sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.Floor(sr)) == 0);
}
 
// Function that returns true
// if n is a Fibonacci number
static bool isFibonacci(int n)
{
    return isPerfectSquare(5 * n * n + 4)
        || isPerfectSquare(5 * n * n - 4);
}
 
// Function to return the count of good cells
static int goodCells(int [,]mat)
{
 
    // To store the required count
    int count = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
 
            int sum = mat[i,j];
 
            // Corner cells of the matrix
            // have only 2 adjacent cells
            if ((i == 0 && j == 0)
                || (i == M - 1 && j == 0)
                || (i == 0 && j == N - 1)
                || (i == M - 1 && j == N - 1))
            {
                sum += 2;
            }
 
            // All the boundary elements
            // except the corner elements
            // have only 3 adjacent cells
            else if (i == 0 || j == 0
                    || i == M - 1 || j == N - 1)
            {
                sum += 3;
            }
 
            // Rest of the elements have 4 adjacent cells
            else
            {
                sum += 4;
            }
 
            // If the sum is a Fibonacci number
            if (isFibonacci(sum))
                count++;
        }
    }
 
    return count;
}
 
// Driver code
public static void Main ()
{
    int [,]mat = { { 1, 0, 5, 3 },
                { 2, 17, 5, 6 },
                { 5, 8, 15, 11 } };
    Console.WriteLine( goodCells(mat));
}
}
 
// This code is contributed by anuj_67..

Javascript

<script>
    // Javascript implementation of the approach
     
    let M = 3;
    let N = 4;
 
    // Function that returns true if
    // x is a perfect square
    function isPerfectSquare(x)
    {
        // Find floating point value of
        // square root of x
        let sr = Math.sqrt(x);
 
        // If square root is an integer
        return ((sr - Math.floor(sr)) == 0);
    }
 
    // Function that returns true
    // if n is a Fibonacci number
    function isFibonacci(n)
    {
        return isPerfectSquare(5 * n * n + 4)
            || isPerfectSquare(5 * n * n - 4);
    }
 
    // Function to return the count of good cells
    function goodCells(mat)
    {
 
        // To store the required count
        let count = 0;
        for (let i = 0; i < M; i++)
        {
            for (let j = 0; j < N; j++)
            {
 
                let sum = mat[i][j];
 
                // Corner cells of the matrix
                // have only 2 adjacent cells
                if ((i == 0 && j == 0)
                    || (i == M - 1 && j == 0)
                    || (i == 0 && j == N - 1)
                    || (i == M - 1 && j == N - 1))
                {
                    sum += 2;
                }
 
                // All the boundary elements
                // except the corner elements
                // have only 3 adjacent cells
                else if (i == 0 || j == 0
                        || i == M - 1 || j == N - 1)
                {
                    sum += 3;
                }
 
                // Rest of the elements have 4 adjacent cells
                else
                {
                    sum += 4;
                }
 
                // If the sum is a Fibonacci number
                if (isFibonacci(sum))
                    count++;
            }
        }
 
        return count;
    }
     
    let mat = [ [ 1, 0, 5, 3 ],
                 [ 2, 17, 5, 6 ],
                 [ 5, 8, 15, 11 ] ];
    document.write( goodCells(mat));
 
</script>
Producción

7

Complejidad de tiempo: O(N*M)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *