Форум программистов, компьютерный форум CyberForum.ru

Дана таблица с булевыми выражениями, некоторые элементы которой утеряны. Требуется восстановить таблицу - C++

Восстановить пароль Регистрация
 
Deligor
1 / 1 / 0
Регистрация: 12.04.2014
Сообщений: 30
25.08.2014, 16:47     Дана таблица с булевыми выражениями, некоторые элементы которой утеряны. Требуется восстановить таблицу #1
Пожалуйста, помогите решить задачу:

Буль
Имя входного файла: bool.in
Имя выходного файла: bool.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта

Булевыми числами называются такие числа, которые могут принимать два значения:
True (Правда) и False (Ложь). Булевыми операциями называются операции
над булевыми числами. Рассмотрим некоторые из таких операций:
1. c = a AND b (Логическое И)
c = True, если a = True и b = True.
c = False, если хотя бы одна из двух переменных равна False.
2. c = a OR b (Логическое ИЛИ)
c = True, если хотя бы одна из двух переменных равна True.
c = False, если обе переменных равны False.
3. c = a XOR b (Исключающее ИЛИ)
c = True, если a принимает другое значение, нежели b, то есть a не равно b.
c = False, если a и b принимают одно значение, то есть a = b.
4. c = a IMP b (Импликация)
c = False, если b не следует из a, то есть если a = True, а b = False.
c = True, если b следует из a, то есть в любом другом случае.

Формат входных данных
Во входном файле на первой строке записано число 0 <= N <= 10000, затем
следуют N строк, по 6 символов в каждой строке (каждый из которых - латинская
буква T или F, или знак вопроса ?). Первые два символа содержат значения
булевых переменных a и b. Затем идут результаты выполнения четырех булевых
операций, описанных выше, для этой пары переменных (a AND b, a OR b, a XOR
b, a IMP b). Таким образом, получается 6 символов. Однако вместо некоторых
значений в таблице стоят знаки вопроса. Ваша задача - восстановить те столбцы
таблицы, которые возможно восстановить.

Формат выходных данных
Вывести восстановленную таблицу. На месте столбцов, значения которых восстановить
невозможно, в выходном файле должен стоять знак вопроса. В таблице
может присутствовать ошибка. В таком случае в выходной файл на соответствующей
строке необходимо вывести слово ERROR.

Пример
Ввод:
5
F?????
?????F
???F??
TTF???
??????

Вывод:
F?F??T
TFFTTF
FFFFFT
ERROR
??????

Заранее премного благодарен!
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2014, 16:47     Дана таблица с булевыми выражениями, некоторые элементы которой утеряны. Требуется восстановить таблицу
Посмотрите здесь:

Дана квадратная матрица, все элементы которой различны C++
Даны таблицы А[1..n] ,В[1..m]. Построить таблицу С в которой сначала размещаются все элементы А, затем все элементы таблицы В C++
C++ дана целочисленная матрица A , размером а х м, найти в матрице первую строку, все элементы которой равны нолю, Умножить элементы столбца с таким же н
C++ Дана действительная квадратная матрица порядка n, все элементы которой различны. Найти наибольший элемент среди стоящих на главной и побочной диаг
дана целочисленная таблица a[1..m]. C++
C++ Дана действительная матрица размером пхт, все элементы которой различны. В каждой строке выбирается элемент с наименьшим значением, затем среди этих ч
C++ Дана последовательность, элементы которой есть целые двузначные числа. Упорядочить последовательность по убыванию произведений цифр
C++ Перемножить попарно элементы строки, в которой расположен максимум матрицы, на элементы столбца

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
olegoner
 Аватар для olegoner
160 / 74 / 4
Регистрация: 22.04.2012
Сообщений: 221
26.08.2014, 18:07     Дана таблица с булевыми выражениями, некоторые элементы которой утеряны. Требуется восстановить таблицу #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/*
* Пояснение к решению:
* Что-бы не возится с символами, переведём строку в бинарный вид, заменяя T на 1,
* а F соответственно на 0 в соответсвующем бите. Таким образом, вся строка представляется
* одним байтом.
* Пример: TFFTTF = bin 100110 = dec 38 = hex 0x26
* Теперь над строками можно выполнять побитные операции.
* Т.к. независимых переменных в таблице истиности будет только две, то строки могут принимать только 4 значения
* 00 000 001 = 0x01
* 00 010 111 = 0x17
* 00 100 110 = 0x26
* 00 111 101 = 0x3D
* их мы и заносим в константный массив line
* для каждой считанной строки мы формируем три переменные:
* mask - маска заполненных символов (для F????? => mask = 00 100 000; для ??T??? mask = 00 001 000)
* positive - все знаки вопроса заменяются 1 (F????? positive = 00 011 111)
* negative - все знаки вопроса заменяются 0 (F????? negative = 00 000 000)
* далее устанавливается побитовая эквивалетность между (positive ~ line[i]) и (negative ~ line[i])
* после чего выполняется побитовая конъюнкция к полученным числам. В результате, получаем маску совпадения строки
* таблицы истиности и востанавливаемой. Если эта маска при побитной дисъюнкции с отрицанием mask даст 00 111 111 = 0x3F,
* то это означает, что строка таблицы на 100% совпадает с шаблоном исследуемой строки.
* После приобразований алгебры логики получаем выражение, описывающее данные операции:
* p_line[i] = (~(((line[i] ^ positive) | (line[i] ^ negative)) & mask)) & 0x3F;
* здесь, что бы "погасить" два старших бита дополнительно наложена маска 00 111 111 = 0x3F.
* Каждой строке таблицы истиности мы присвоили уникальный код: 1,2,4,8 соответсвенно.
* После вычисления p_line[i], если найдено 100% совпадение line[i] с шаблоном, мы прибавляем код строки к
* ключу key, который является уникальным для любой комбинации строк, удволетворяющих шаблону (из-за свойств степени двойки).
* Запоминаем последнюю шаблонную (100%) строку в pos. Из неё будем востанвливать символы.
* Теперь мы можем получить "маску вывода" по ключу, т.е. символы, которые мы будем выводить из сохранённой строки таблицы истиности.
* Предварительно эти маски были подсчитаны (из комбинаторики их 15).
* Теперь просто переводим число обратно в строку, используя массив masks_f, элементы которого - маски на отдельне биты (например 00 001 000 или 00 000 010)
* Исходя из ограничений на N, выполнение программы не должно привысить 1 сек (хотя не испытовал)
* Для увелечения скорости выполнения, можно сделать ввод - вывод в стиле С.
*/
 
 
 
#include <fstream>
int main()
{
    const char code[4] = {1,2,4,8};//коды строк таблицы истиности
    const char line[4] = {0x01,0x17,0x26,0x3D};//таблица истиности
    
    char masks[16];//массив масок вывода
    char masks_f[6] = {0x20,0x10,0x08,0x04,0x02,0x01};// маски на отдельные биты для конвертирования строки в число и обратно
    
    
    masks[1] = 0x3F;
    masks[2] = 0x3F;
    masks[4] = 0x3F;
    masks[8] = 0x3F;
 
    for (int i = 0; i < 3; i++)
        for (int j = i+1; j < 4; j++)
            masks[code[i]+code[j]] = ~(line[i] ^ line [j]);
 
    for (int i = 0; i < 2; i++)
        for (int j = i+1; j < 3; j++)
            for (int k = j+1; k < 4; k++)
                masks[code[i]+code[j]+code[k]] = ~((line[i] ^ line [j]) | (line[i] ^ line [k]) | (line[k] ^ line [j]));
    masks[15] = 0x00; 
 
 
    char p_line[4];
    char mask;
    
    char positive, negative;
    char key;
    char pos;
    int N;
    
    std::ifstream inFile("input.txt");
    std::ofstream outFile("out.txt");
 
    if (! inFile.good()) 
    {
        outFile << "Can't open file 'input.txt'";
        return -1;
    }
 
 
    inFile >> N;
    inFile.get();
    char str[7];
 
    for (int count = 0; count < N; count++)
    {
 
        inFile.getline(str,7);
 
        mask = 0x00;
        positive = 0x00;
        negative = 0x00;
    
        //переводим строку в число
        for (int i = 0; i < 6; i++) 
            switch(str[i])
            {
                case 'F': mask |= masks_f[i]; break;
                case 'T': mask |= masks_f[i]; positive |= masks_f[i]; negative |= masks_f[i];break;
                default: positive |= masks_f[i];
            }
        if (mask == 0x00) 
        {
            outFile<<str<<std::endl;
            break;      
        }
    
 
        pos = 0;
        key = 0;
        //вычисляем ключ маски вывода
        for (int i = 0; i < 4; i++)
        {
            p_line[i] = (~(((line[i] ^ positive) | (line[i] ^ negative)) & mask)) & 0x3F;
            if (p_line[i] == 0x3F) 
            {
                key += code[i];
                pos = i;
            }
        }
        mask = masks[key];
 
        //востанавливаем строку по маске
        if (key != 0)
        {
            for (int i = 0; i < 6; i++)         
                if (str[i] == '?')
                    if ((mask & masks_f[i]) != 0x00)        
                        if ((masks_f[i] & line[pos]) != 0x00) str[i] = 'T';
                        else str[i] = 'F';
            str[6] = '\0';
        }
        else
            strcpy(str,"ERROR");
 
        outFile << str<<std::endl;
    }
    
    inFile.close();
    outFile.close();
    return 0;
}
Yandex
Объявления
26.08.2014, 18:07     Дана таблица с булевыми выражениями, некоторые элементы которой утеряны. Требуется восстановить таблицу
Ответ Создать тему
Опции темы

Текущее время: 20:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru