Добро пожаловать! Войти Зарегистрироваться

Расширенный

КНФ из дерева выражений

Написал w-495 
КНФ из дерева выражений
03 Июнь 2014 19:07
Интересная практическая задача, и удачная задача для собеседования.

Есть дерево выражений в JSON.
{
   "and-500" : {
      "or-1933" : {
         "or-21314" : [
            "x16"
         ]
      },
      "and-11" : {
         "or-2971" : {
            "or-31" : [
               "x3",
               "x4"
            ]
         },
         "or-2878" : [
            "x2"
         ],
         "or-2981" : [
            "x5"
         ],
         "or-21021" : [
            "x13",
            "x14",
            "x15"
         ],
         "and-2982" : [
            "x9",
            "x10",
            "x6",
            "x11",
            "x8",
            "x12",
            "x7"
         ],
         "or-2166" : [
            "x1"
         ]
      }
   }
}

Представьте это дерево в виде КНФ, заменяя каждую and-* на конъюнкцию, а or-* на дизъюнкцию.
Нужно составить алгоритм для этого.



Исправлений: 1. Последний раз редактировал w-495 в 03.06.2014, 19:07.
К сожалению, только зарегистрированные пользователи могут писать в этом форуме.

Авторизоваться на форуме