Найдите все совместимые и несовместимые края машины

Опубликовано: 17 Февраля, 2022

Дана машина на формальном языке из 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)

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Для всех возможных комбинаций (скажем, (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;
                        }
                    }
                }

                    
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИ
                                    