Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
>>
глава 6. Задачи на разные темы
>>
задача 5
Фильтр
Выбрана 1 задача Убрать все задачи
Булевой функцией называется функция, принимающая одно из логических значений TRUE или FALSE и зависящая от некоторого (быть может, нулевого) количества аргументов, каждый из которых также может принимать любое из значений TRUE или FALSE.
Любая булева функция однозначно задается своей таблицей истинности, в которой для каждого возможного набора значений аргументов указано значение функции. Например, x AND y – булева функция от двух аргументов. Ее таблица истинности выглядит так:
Если договориться, что наборы значений аргументов в таблице располагаются в лексикографическом порядке, то функция AND однозначно задается третьим столбцом таблицы – строкой 0001. Аналогично, каждой булевой функции от k аргументов можно поставить в соответствие строку из нулей и единиц длины 2k.
Задан набор из N+1 булевой функции (f, f1, f2, ..., fN). Напишите программу,
которая определяет, можно ли функцию f выразить через функции f1, f2, ..., fN, и
если такие представления возможны, то находит кратчайшее по числу символов
среди них.
Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 9).
Последующие N+1 строк содержат описания функций
f, f1, f2, ..., fN соответственно. Каждая из функций описывается строкой символов так, как
указано выше. Число аргументов у функции f будет не более двух, а у остальных
функций – не более трех.
Выходные данные
Первая строка выходного файла должна содержать искомое символьное
представление, либо строку «Impossible», если такого представления не
существует. После функции с нулевым числом аргументов скобки не ставятся.
Если у функции f один аргумент, то он обозначается x, а если два, то они
обозначаются x и y.
Пример входного файла
2
1
1010
0
Пример выходного файла
f1(f2,f2)
Решение
Задачи
Задача 102950[Булевы функции ] |
|
|
Любая булева функция однозначно задается своей таблицей истинности, в которой для каждого возможного набора значений аргументов указано значение функции. Например, x AND y – булева функция от двух аргументов. Ее таблица истинности выглядит так:
Если договориться, что наборы значений аргументов в таблице располагаются в лексикографическом порядке, то функция AND однозначно задается третьим столбцом таблицы – строкой 0001. Аналогично, каждой булевой функции от k аргументов можно поставить в соответствие строку из нулей и единиц длины 2k.
Задан набор из N+1 булевой функции (f, f1, f2, ..., fN). Напишите программу,
которая определяет, можно ли функцию f выразить через функции f1, f2, ..., fN, и
если такие представления возможны, то находит кратчайшее по числу символов
среди них.
Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 9).
Последующие N+1 строк содержат описания функций
f, f1, f2, ..., fN соответственно. Каждая из функций описывается строкой символов так, как
указано выше. Число аргументов у функции f будет не более двух, а у остальных
функций – не более трех.
Выходные данные
Первая строка выходного файла должна содержать искомое символьное
представление, либо строку «Impossible», если такого представления не
существует. После функции с нулевым числом аргументов скобки не ставятся.
Если у функции f один аргумент, то он обозначается x, а если два, то они
обозначаются x и y.
Пример входного файла
2
1
1010
0
Пример выходного файла
f1(f2,f2)
|
|
|
Решение |
Страница: 1 [Всего задач: 1]
