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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Deligor
1 / 1 / 0
Регистрация: 12.04.2014
Сообщений: 30
#1

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

25.08.2014, 16:47. Просмотров 381. Ответов 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
??????

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

дана целочисленная матрица A , размером а х м, найти в матрице первую строку, все элементы которой равны нолю, Умножить элементы столбца с таким же н - C++
#include &lt;iostream&gt; using namespace std; int main() { const int a = 5; const int m = 4;

Дана квадратная матрица, все элементы которой различны - C++
1. Дана квадратная матрица, все элементы которой различны. Поменять местами строки, в которых находятся максимальный и минимальный...

Циклы. Дана таблица целых чисел a1, a2, ., an. Упорядочить эту таблицу - Turbo Pascal
Дана таблица целых чисел a1, a2, ..., an. Упорядочить эту таблицу.

Как заполнить матрицу, в которой некоторые элементы - случайные числа - Matlab
Есть матрица размерности 3N х 3N нужно заполнить ее таким образом: Для N = 3 матрица будет такая. Если можно, то без циклов, или же...

Дана таблица из 8 элементов заменить отрицательные элементы таблице их модулями - Delphi
Помогите решить задачу Дана таблица из 8 элементов заменить отрицательные элементы таблице их модулями

дана целочисленная таблица, есть ли в ней элементы, равные нулю - Pascal ABC
дана целочисленная таблица А. проверьте, есть ли в ней элементы, равные нулю. Если есть, найдите номер первого из них, т.е. наименьший i,...

1
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;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2014, 18:07
Привет! Вот еще темы с ответами:

Дана матрица порядка n*m, все элементы которой различны - Delphi
Дана матрица порядка n*m,все элементы которой различны.В каждой строке выбирается элемент с наименьшим значением , затем среди этих чисел...

Дана таблица. Вывести элементы, которые находятся между max и min - Delphi
Не понимаю, что я сделала не так. Проект компилируется, но программа не выполняется. unit Unit1; interface uses ...

Дана действительная матрица размером m n, все элементы которой различны - Pascal
В каждой строке выбирается элемент с наименьшим значением, затем среди этих чисел выбирается наибольшее. Указать индексы элемента с...

Дана действительная матрица размером , все элементы которой различны - Visual Basic
Дана действительная матрица размером , все элементы которой различны. В каждой строке выбирается элемент с наименьшим значением, а затем...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru