Dadas tres arrays A, B y C, encuentre si C es un producto de A y B.
Ejemplos:
Input : A = 1 1 1 1 B = 1 1 1 1 C = 2 2 2 2 Output : Yes C = A x B Input : A = 1 1 1 1 1 1 1 1 1 B = 1 1 1 1 1 1 1 1 1 C = 3 3 3 3 1 2 3 3 3 Output : No
Una solución simple es encontrar el producto de A y B y luego verificar si el producto es igual a C o no. Una posible complejidad temporal de este método es O(n 2.8874 ) usando la multiplicación de arrays de Stression .
El algoritmo de Freivalds es un algoritmo aleatorio probabilístico que trabaja en el tiempo O(n 2 ) con alta probabilidad. En tiempo O(kn 2 ) el algoritmo puede verificar un producto matricial con probabilidad de falla menor a 2 -k . Dado que la salida no siempre es correcta, es un algoritmo aleatorio de Monte Carlo .
Pasos :
- Genere un vector aleatorio n × 1 0/1 r⃗ .
- Calcule P⃗ = A × (Br)⃗ – Cr⃗ .
- Devuelve verdadero si P⃗ = ( 0, 0, …, 0 ) T , de lo contrario devuelve falso.
La idea se basa en el hecho de que si C es realmente un producto, entonces el valor de A × (Br)⃗ – Cr⃗ siempre será 0. Si el valor es distinto de cero, entonces C no puede ser un producto. La condición de error es que el valor puede ser 0 incluso cuando C no es un producto.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code to implement Freivald’s Algorithm #include <bits/stdc++.h> using namespace std; #define N 2 // Function to check if ABx = Cx int freivald(int a[][N], int b[][N], int c[][N]) { // Generate a random vector bool r[N]; for (int i = 0; i < N; i++) r[i] = random() % 2; // Now compute B*r for evaluating // expression A * (B*r) - (C*r) int br[N] = { 0 }; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) br[i] = br[i] + b[i][j] * r[j]; // Now compute C*r for evaluating // expression A * (B*r) - (C*r) int cr[N] = { 0 }; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cr[i] = cr[i] + c[i][j] * r[j]; // Now compute A* (B*r) for evaluating // expression A * (B*r) - (C*r) int axbr[N] = { 0 }; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) axbr[i] = axbr[i] + a[i][j] * br[j]; // Finally check if value of expression // A * (B*r) - (C*r) is 0 or not for (int i = 0; i < N; i++) if (axbr[i] - cr[i] != 0) false; return true; } // Runs k iterations Freivald. The value // of k determines accuracy. Higher value // means higher accuracy. bool isProduct(int a[][N], int b[][N], int c[][N], int k) { for (int i=0; i<k; i++) if (freivald(a, b, c) == false) return false; return true; } // Driver code int main() { int a[N][N] = { { 1, 1 }, { 1, 1 } }; int b[N][N] = { { 1, 1 }, { 1, 1 } }; int c[N][N] = { { 2, 2 }, { 2, 2 } }; int k = 2; if (isProduct(a, b, c, k)) printf("Yes"); else printf("No"); return 0; }
Java
// Java code to implement // Freivald's Algorithm import java.io.*; import java.util.*; import java.math.*; class GFG { static int N = 2; // Function to check if ABx = Cx static boolean freivald(int a[][], int b[][], int c[][]) { // Generate a random vector int r[] = new int[N]; for (int i = 0; i < N; i++) r[i] = (int)(Math.random()) % 2; // Now compute B*r for evaluating // expression A * (B*r) - (C*r) int br[] = new int[N]; Arrays.fill(br, 0); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) br[i] = br[i] + b[i][j] * r[j]; // Now compute C*r for evaluating // expression A * (B*r) - (C*r) int cr[] = new int[N]; Arrays.fill(cr, 0); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cr[i] = cr[i] + c[i][j] * r[j]; // Now compute A* (B*r) for evaluating // expression A * (B*r) - (C*r) int axbr[] = new int[N]; Arrays.fill(axbr, 0); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) axbr[i] = axbr[i] + a[i][j] * br[j]; // Finally check if value of expression // A * (B*r) - (C*r) is 0 or not for (int i = 0; i < N; i++) if (axbr[i] - cr[i] != 0) return false; return true; } // Runs k iterations Freivald. The value // of k determines accuracy. Higher value // means higher accuracy. static boolean isProduct(int a[][], int b[][], int c[][], int k) { for (int i = 0; i < k; i++) if (freivald(a, b, c) == false) return false; return true; } // Driver code public static void main(String args[]) { int a[][] = { { 1, 1 }, { 1, 1 } }; int b[][] = { { 1, 1 }, { 1, 1 } }; int c[][] = { { 2, 2 }, { 2, 2 } }; int k = 2; if (isProduct(a, b, c, k)) System.out.println("Yes"); else System.out.println("No"); } } /*This code is contributed by Nikita Tiwari.*/
Python3
# Python3 code to implement Freivald’s Algorithm import random N = 2 # Function to check if ABx = Cx def freivald(a, b, c) : # Generate a random vector r = [0] * N for i in range(0, N) : r[i] = (int)(random.randrange(509090009) % 2) # Now compute B*r for evaluating # expression A * (B*r) - (C*r) br = [0] * N for i in range(0, N) : for j in range(0, N) : br[i] = br[i] + b[i][j] * r[j] # Now compute C*r for evaluating # expression A * (B*r) - (C*r) cr = [0] * N for i in range(0, N) : for j in range(0, N) : cr[i] = cr[i] + c[i][j] * r[j] # Now compute A* (B*r) for evaluating # expression A * (B*r) - (C*r) axbr = [0] * N for i in range(0, N) : for j in range(0, N) : axbr[i] = axbr[i] + a[i][j] * br[j] # Finally check if value of expression # A * (B*r) - (C*r) is 0 or not for i in range(0, N) : if (axbr[i] - cr[i] != 0) : return False return True # Runs k iterations Freivald. The value # of k determines accuracy. Higher value # means higher accuracy. def isProduct(a, b, c, k) : for i in range(0, k) : if (freivald(a, b, c) == False) : return False return True # Driver code a = [ [ 1, 1 ], [ 1, 1 ] ] b = [ [ 1, 1 ], [ 1, 1 ] ] c = [ [ 2, 2 ], [ 2, 2 ] ] k = 2 if (isProduct(a, b, c, k)) : print("Yes") else : print("No") # This code is contributed by Nikita Tiwari
C#
// C# code to implement // Freivald's Algorithm using System; class GFG { static int N = 2; // Function to check // if ABx = Cx static bool freivald(int [,]a, int [,]b, int [,]c) { // Generate a // random vector Random rand = new Random(); int []r = new int[N]; for (int i = 0; i < N; i++) r[i] = (int)(rand.Next()) % 2; // Now compute B*r for // evaluating expression // A * (B*r) - (C*r) int []br = new int[N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) br[i] = br[i] + b[i, j] * r[j]; // Now compute C*r for // evaluating expression // A * (B*r) - (C*r) int []cr = new int[N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cr[i] = cr[i] + c[i, j] * r[j]; // Now compute A* (B*r) for // evaluating expression // A * (B*r) - (C*r) int []axbr = new int[N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) axbr[i] = axbr[i] + a[i, j] * br[j]; // Finally check if value // of expression A * (B*r) - // (C*r) is 0 or not for (int i = 0; i < N; i++) if (axbr[i] - cr[i] != 0) return false; return true; } // Runs k iterations Freivald. // The value of k determines // accuracy. Higher value // means higher accuracy. static bool isProduct(int [,]a, int [,]b, int [,]c, int k) { for (int i = 0; i < k; i++) if (freivald(a, b, c) == false) return false; return true; } // Driver code static void Main() { int [,]a = new int[,]{ { 1, 1 }, { 1, 1 }}; int [,]b = new int[,]{ { 1, 1 }, { 1, 1 }}; int [,]c = new int[,]{ { 2, 2 }, { 2, 2 }}; int k = 2; if (isProduct(a, b, c, k)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed // by Manish Shaw(manishshaw1)
PHP
<?php // PHP code to implement // Freivald’s Algorithm $N = 2; // Function to check // if ABx = Cx function freivald($a, $b, $c) { global $N; // Generate a // random vector $r = array(); $br = array(); $cr = array(); $axbr = array(); for ($i = 0; $i < $N; $i++) { $r[$i] = mt_rand() % 2; $br[$i] = 0; $cr[$i] = 0; $axbr[$i] = 0; } // Now compute B*r for // evaluating expression // A * (B*r) - (C*r) for ($i = 0; $i < $N; $i++) { for ($j = 0; $j < $N; $j++) $br[$i] = $br[$i] + $b[$i][$j] * $r[$j]; } // Now compute C*r for // evaluating expression // A * (B*r) - (C*r) for ($i = 0; $i < $N; $i++) { for ($j = 0; $j < $N; $j++) $cr[$i] = $cr[$i] + $c[$i][$j] * $r[$j]; } // Now compute A* (B*r) for // evaluating expression // A * (B*r) - (C*r) for ($i = 0; $i < $N; $i++) { for ($j = 0; $j < $N; $j++) $axbr[$i] = $axbr[$i] + $a[$i][$j] * $br[$j]; } // Finally check if value // of expression A * (B*r) - // (C*r) is 0 or not for ($i = 0; $i < $N; $i++) if ($axbr[$i] - $cr[$i] != 0) return false; return true; } // Runs k iterations Freivald. // The value of k determines // accuracy. Higher value // means higher accuracy. function isProduct($a, $b, $c, $k) { for ($i = 0; $i < $k; $i++) if (freivald($a, $b, $c) == false) return false; return true; } // Driver code $a = array(array(1, 1), array(1, 1)); $b = array(array(1, 1), array(1, 1)); $c = array(array(2, 2), array(2, 2)); $k = 2; if (isProduct($a, $b, $c, $k)) echo ("Yes"); else echo ("No"); // This code is contributed // by Manish Shaw(manishshaw1) ?>
Javascript
<script> // JavaScript code to implement Freivald’s Algorithm let N = 2; // Function to check if ABx = Cx function freivald(a,b,c) { // Generate a random vector let r = new Array(N); for (let i = 0; i < N; i++) r[i] = Math.random() % 2; // Now compute B*r for evaluating // expression A * (B*r) - (C*r) let br = new Array(N); br.fill(0); for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) br[i] = br[i] + b[i][j] * r[j]; // Now compute C*r for evaluating // expression A * (B*r) - (C*r) let cr = new Array(N); cr.fill(0); for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) cr[i] = cr[i] + c[i][j] * r[j]; // Now compute A* (B*r) for evaluating // expression A * (B*r) - (C*r) let axbr = new Array(N); axbr.fill(0); for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) axbr[i] = axbr[i] + a[i][j] * br[j]; // Finally check if value of expression // A * (B*r) - (C*r) is 0 or not for (let i = 0; i < N; i++) if (axbr[i] - cr[i] != 0) false; return true; } // Runs k iterations Freivald. The value // of k determines accuracy. Higher value // means higher accuracy. function isProduct(a,b,c,k) { for (let i=0; i<k; i++) if (freivald(a, b, c) == false) return false; return true; } // Driver code let a = [[ 1, 1 ], [ 1, 1 ]]; let b = [[ 1, 1 ], [ 1, 1 ]]; let c = [[ 2, 2 ], [ 2, 2 ]]; let k = 2; if (isProduct(a, b, c, k)) document.write("Yes"); else document.write("No"); </script>
Yes
Complejidad temporal: O(N ^ 2)
Espacio auxiliar: O(N ^ 2)
Publicación traducida automáticamente
Artículo escrito por nickhilrawat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA