Dada una array A[] , la tarea es encontrar la array circulante formada por esta array.
Una array circulante es una array cuadrada de orden N x N , donde cada columna se compone de los mismos elementos, pero cada columna gira un elemento hacia abajo en relación con la columna anterior. Es un tipo particular de array Toeplitz .
Aquí está la forma general de una array circulante.
Estructura general de la Array Circulante
Ejemplos:
Entrada: a[] = {2, 3, 4, 5}.
Salida: Entonces la array circulante resultante debería ser:
2 3 4 5
3 4 5 2
4 5 2 3
5 2 3 4Entrada: a[] = {0, 4, 0, 7, 9, 12, 17}.
Salida: La array circulante resultante debe ser:
0 4 0 7 9 12 17
4 0 7 9 12 17 0
0 7 9 12 17 0 4
7 9 12 17 0 4 0
9 12 17 0 4 0 7
12 17 0 4 0 7 9
17 0 4 0 7 9 12
Enfoque: Este es un problema simple basado en la implementación basado en la siguiente idea:
Para cada i -ésima columna, inserte el primer elemento de la array en la i -ésima fila e inserte todos los demás elementos iterando a través de la columna de manera circular.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array vacía (digamos c[][] ) de orden N .
- Iterar a través de las columnas de i = 0 a N-1 :
- Iterar a través de las filas usando un bucle anidado desde j = 0 hasta N-1 .
- si (i > 0), entonces asigne c[j][i] = c[j – 1][i – 1] .
- de lo contrario, asigne c[j][i] = c[N – 1][i – 1] .
- Iterar a través de las filas usando un bucle anidado desde j = 0 hasta N-1 .
- Por último, muestre la array circulante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <iostream>
using namespace std;
// Circulant function defined here
void circulant(int arr[], int n)
{
// Initializing an empty
// 2D matrix of order n
int c[n][n];
for (int k = 0; k <= n - 1; k++)
c[k][0] = arr[k];
// Forming the circulant matrix
for (int i = 1; i <= n - 1; i++) {
for (int j = 0; j <= n - 1; j++) {
if (j - 1 >= 0)
c[j][i] = c[j - 1][i - 1];
else
c[j][i] = c[n - 1][i - 1];
}
}
// Displaying the circulant matrix
for (int i = 0; i <= n - 1; i++) {
for (int j = 0; j <= n - 1; j++) {
cout << c[i][j] << "\t";
}
cout << "\n";
}
}
// Driver Code
int main()
{
int N = 4;
int A[] = { 2, 3, 4, 5 };
// Function call
circulant(A, N);
return 0;
}
// This code is contributed by Rohit Pradhan
Java
// Java code to implement the approach
import java.io.*;
class GFG {
// Circulant function defined here
public static void circulant(int arr[], int n)
{
// Initializing an empty
// 2D matrix of order n
int c[][] = new int[n][n];
for (int k = 0; k <= n - 1; k++)
c[k][0] = arr[k];
// Forming the circulant matrix
for (int i = 1; i <= n - 1; i++) {
for (int j = 0; j <= n - 1; j++) {
if (j - 1 >= 0)
c[j][i] = c[j - 1][i - 1];
else
c[j][i] = c[n - 1][i - 1];
}
}
// Displaying the circulant matrix
for (int i = 0; i <= n - 1; i++) {
for (int j = 0; j <= n - 1; j++) {
System.out.print(c[i][j] + "\t");
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
int N = 4;
int A[] = { 2, 3, 4, 5 };
circulant(A, N);
}
}
Python3
# Python code to implement the approach # Circulant function defined here def circulant( arr, n): # Initializing an empty # 2D matrix of order n c = [[0 for i in range(n)] for j in range(n)] for k in range(n): c[k][0] = arr[k] # Forming the circulant matrix for i in range(1,n): for j in range(n): if (j - 1 >= 0): c[j][i] = c[j - 1][i - 1] else: c[j][i] = c[n - 1][i - 1] # Displaying the circulant matrix for i in range(n): for j in range(n): print(c[i][j] ,end="\t") print() # Driver code N = 4 A = [2, 3, 4, 5 ] circulant(A, N) # This code is contributed by rohitsingh07052
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Circulant function defined here
public static void circulant(int[] arr, int n)
{
// Initializing an empty
// 2D matrix of order n
int[,] c = new int[n, n];
for (int k = 0; k <= n - 1; k++)
c[k, 0] = arr[k];
// Forming the circulant matrix
for (int i = 1; i <= n - 1; i++) {
for (int j = 0; j <= n - 1; j++) {
if (j - 1 >= 0)
c[j, i] = c[j - 1, i - 1];
else
c[j, i] = c[n - 1, i - 1];
}
}
// Displaying the circulant matrix
for (int i = 0; i <= n - 1; i++) {
for (int j = 0; j <= n - 1; j++) {
Console.Write(c[i, j] + "\t");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main()
{
int N = 4;
int[] A = { 2, 3, 4, 5 };
circulant(A, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code to implement the approach
// Circulant function defined here
function circulant(arr, n)
{
// Initializing an empty
// 2D matrix of order n
let c = new Array(n).fill(0).map(()=>new Array(n));
for (let k = 0; k <= n - 1; k++)
c[k][0] = arr[k];
// Forming the circulant matrix
for (let i = 1; i <= n - 1; i++) {
for (let j = 0; j <= n - 1; j++) {
if (j - 1 >= 0)
c[j][i] = c[j - 1][i - 1];
else
c[j][i] = c[n - 1][i - 1];
}
}
// Displaying the circulant matrix
for (let i = 0; i <= n - 1; i++) {
for (let j = 0; j <= n - 1; j++) {
document.write(`${c[i][j]} \t`)
}
document.write("</br>")
}
}
// Driver Code
let N = 4
let A = [ 2, 3, 4, 5 ]
// Function call
circulant(A, N)
// This code is contributed by shinjanpatra
</script>
2 5 4 3 3 2 5 4 4 3 2 5 5 4 3 2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por srimandutta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA