Найдите все совместимые и несовместимые края машины
Дана машина на формальном языке из N состояний и M пар выходных комбинаций в виде двумерного массива arr [] [] . Каждая строка (скажем, r ) в arr [] [] обозначает узлы от 'A' до 'Z', а каждая пара столбца (скажем (a, b) ) обозначает изменение состояния узла r на переходное состояние узла a б . Задача состоит в том, чтобы найти совместимые и несовместимые грани формального языка.
Примечание: Edge (A, B) считается совместимым, так как все следующие состояния и выход либо равны, либо не указаны в A, B, соответствующих каждому столбцу.
Пример:
Input: N = 6, M = 4,
arr[][] = { { ‘-‘, ‘-‘, ‘C’, ‘1’, ‘E’, ‘1’, ‘B’, ‘1’ },
{ ‘E’, ‘0’, ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘ },
{ ‘F’, ‘0’, ‘F’, ‘1’, ‘-‘, ‘-‘, ‘-‘, ‘-‘ },
{ ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘B’, ‘1’, ‘-‘, ‘-‘ },
{ ‘-‘, ‘-‘, ‘F’, ‘0’, ‘A’, ‘0’, ‘D’, ‘1’ },
{ ‘C’, ‘0’, ‘-‘, ‘-‘, ‘B’, ‘0’, ‘C’, ‘1’ } }
Output:
Not Compatable Edges
(A, E) (A, F) (B, F) (C, E) (D, E) (D, F)
Compatable Edges
(A, B)(A, C)(A, D)(B, C)(B, D)(B, E)(C, D)(C, F)(E, F)
Input: N = 4, M = 4,
arr[][] = { { ‘-‘, ‘-‘, ‘C’, ‘1’, ‘E’, ‘1’, ‘B’, ‘1’ },
{ ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘B’, ‘1’, ‘-‘, ‘-‘ },
{ ‘-‘, ‘-‘, ‘F’, ‘0’, ‘A’, ‘0’, ‘D’, ‘1’ },
{ ‘C’, ‘0’, ‘-‘, ‘-‘, ‘B’, ‘0’, ‘C’, ‘1’ } }
Output:
Not Compatable Edges
(A, C) (A, D) (B, C) (B, D)
Compatable Edges
(A, B)(C, D)
Подход:
- Для всех возможных комбинаций (скажем, (a, b) ) узлов проверьте, существует ли какой-либо возможный путь на формальном языке через любое количество состояний, например:
- Если состояние через узел a пусто , проверьте следующую пару узлов.
- Если текущее пройденное состояние (скажем, узел b ) через узел a не пусто и если состояние вывода через узел a на узел b не то же самое, то рекурсивно проверьте путь от узла a к узлу b .
- Если состояние выхода такое же, значит, у него есть прямая граница между узлом a и узлом b .
- Если путь найден между любой парой узлов, то пара узлов является частью совместимого узла.
- Сохраните указанную выше пару совместимых узлов в матрице Mat [] [] .
- Просмотрите Mat [] [] для всех возможных пар, и если эта пара присутствует в Mat [] [], то распечатайте ее как Совместимые узлы, иначе это Несовместимый узел.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; const int M = 8; // Function to find the compatible and // non-compatible for a given formal language void findEdges( char arr[][M], int n, int m) { // To store the compatible edges char mat[1000][1000] = { "x" }; // Loop over every pair of nodes in the // given formal language for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Traverse through the output // column and compare it between // each set of pairs of nodes for ( int k = 0; k < 2 * m; k += 2) { // If the the output is not // specified then leave the // edge unprocessed if (arr[i][k + 1] == "-" || arr[j][k + 1] == "-" ) { continue ; } // If the output of states // doesn"t match then not // compatable. if (arr[i][k + 1] != arr[j][k + 1]) { // Mark the not compatable // edges in the maxtrix with // character "v" mat[i][j] = "v" ; mat[j][i] = "v" ; break ; } } } } int nn = n; // Loop over all node to find other non // compatable edges while (nn--) { // Loop over every pair of nodes in // the given formal language for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { int k; for (k = 0; k < m; k += 2) { // If the the output is // not specified then // leave edge unprocessed if (arr[i][k + 1] == "-" || arr[j][k + 1] == "-" ) { continue ; } // If output is not equal // then break as non-compatable if (arr[i][k + 1] != arr[j][k + 1]) { break ; } } if (k < m) { continue ; } for (k = 0; k < m; k += 2) { // If next states are unspecified // then continue if (arr[i][k] == "-" || arr[j][k] == "-" ) { continue ; } // If the states are not equal if (arr[i][k] != arr[j][k]) { int x = arr[i][k] - "A" ; int y = arr[j][k] - "A" ; // If the dependent edge // is not compatable then // this edge is also not // compatable if (mat[x][y] == "v" ) { mat[i][j] = "v" ; mat[j][i] = "v" ; break ; } } } } } } // Output all Non-compatable Edges printf ( "Not Compatable Edges
" ); for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { if (mat[i][j] == "v" ) { printf ( "(%c, %c) " , i + 65, j + 65); } } } printf ( "
" ); // Output all Compatable Edges printf ( "Compatable Edges
" ); for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { if (mat[i][j] != "v" ) { printf ( "(%c, %c)" , i + 65, j + 65); } } } } // Driver Code int main() { int n = 6, m = 4; char arr[][8] = { { "-" , "-" , "C" , "1" , "E" , "1" , "B" , "1" }, { "E" , "0" , "-" , "-" , "-" , "-" , "-" , "-" }, { "F" , "0" , "F" , "1" , "-" , "-" , "-" , "-" }, { "-" , "-" , "-" , "-" , "B" , "1" , "-" , "-" }, { "-" , "-" , "F" , "0" , "A" , "0" , "D" , "1" }, { "C" , "0" , "-" , "-" , "B" , "0" , "C" , "1" } }; findEdges(arr, n, m); return 0; } |
Java
// Java implementation of the above approach import java.util.*; class GFG{ static int M = 8 ; // Function to find the compatible and // non-compatible for a given formal language static void findEdges( char arr[][], int n, int m) { // To store the compatible edges char [][]mat = new char [ 1000 ][ 1000 ]; // Loop over every pair of nodes in the // given formal language for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { // Traverse through the output // column and compare it between // each set of pairs of nodes for ( int k = 0 ; k < 2 * m; k += 2 ) { // If the the output is not // specified then leave the // edge unprocessed if (arr[i][k + 1 ] == "-" || arr[j][k + 1 ] == "-" ) { continue ; } // If the output of states // doesn"t match then not // compatable. if (arr[i][k + 1 ] != arr[j][k + 1 ]) { // Mark the not compatable // edges in the maxtrix with // character "v" mat[i][j] = "v" ; mat[j][i] = "v" ; break ; } } } } int nn = n; // Loop over all node to find other non // compatable edges while (nn-- > 0 ) { // Loop over every pair of nodes in // the given formal language for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { int k; for (k = 0 ; k < m; k += 2 ) { // If the the output is // not specified then // leave edge unprocessed if (arr[i][k + 1 ] == "-" || arr[j][k + 1 ] == "-" ) { continue ; } // If output is not equal // then break as non-compatable if (arr[i][k + 1 ] != arr[j][k + 1 ]) { break ; } } if (k < m) { continue ; } for (k = 0 ; k < m; k += 2 ) { // If next states are unspecified // then continue if (arr[i][k] == "-" || arr[j][k] == "-" ) { continue ; } // If the states are not equal if (arr[i][k] != arr[j][k]) { int x = arr[i][k] - "A" ; int y = arr[j][k] - "A" ; // If the dependent edge // is not compatable then // this edge is also not // compatable if (mat[x][y] == "v" ) { mat[i][j] = "v" ; mat[j][i] = "v" ; break ; } } } РЕКОМЕНДУЕМЫЕ СТАТЬИ |