为了人类的未来,让我们做离散数学上机题吧
题目背景
李昕峰同学致力于研究可控核聚变技术,每天废寝忘食,呕心沥血,抽不出空写离散作业。你身为李昕峰的同学,为了国家的未来,为了人类科技的发展,为了以后人类能够安全有效地使用核能,你需要帮助李昕峰同学完成他的离散作业。你不需要写很多,因为李昕峰已经写了一部分了,只剩下析取范式转化为主析取范式这部分没写,你的任务是编写一个程序,把析取范式转化为主析取范式。
题目描述
给你一个析取范式,请你编写程序将其转化为主析取范式输出出来。
输入格式
第一行输入一个数字 \(n(1\leqslant n \leqslant16)\),表示共有的命题个数
第二行输入\(n\)个命题的名字某大写字母
第三行输入一个析取范式(每个命题之间用空格隔开,同时将合取的式子用括号括在一起,取非用~
,析取符号用小写字母v
表示。(参考样例)(我们保证~
和命题某大写字母
是连在一起的)
输出格式
输出一行主析取范式(请你保证~
和命题某大写字母
是连在一起的,单元与单元之间用英文括号和小写字母v
隔开)
样例 #1
样例输入 #1
3
P Q R
(P ^ Q ^ R) v (P ^ ~Q)
样例输出 #1
(P ^ Q ^ R) v (P ^ ~Q ^ R) v (P ^ ~Q ^ ~R)
真值表秒了!!!
我的思路就是把合取式转化为真值表,最后输出结果。
关键代码
构造真值表函数
void gouzhao(int n, string ne)
{
bool upLcx = isHere.count(arr[n]) ? true : false;
bool downLcx = isHere.count(brr[n]) ? true : false;
if (upLcx && downLcx)
return;
if (n == all)
{
q.insert(ne);
return;
}
if (upLcx)
gouzhao(n + 1, ne + "1"); //如果是真的,构造1
else if (downLcx)
gouzhao(n + 1, ne + "0"); //假的,构造0
else //没写真假,构造0和1
{
gouzhao(n + 1, ne + "0");
gouzhao(n + 1, ne + "1");
}
}
数据预处理,即把(P ^ ~Q ^ R)转化为PqR
rep(i, 0, all) cin >> arr[i];
rep(i, 0, all) brr[i] = arr[i] - 'A' + 'a';
string father;
string son = "";
getline(cin, father);
rep(i, 0, (int)father.size())
{
if (father[i] >= 'A' && father[i] <= 'Z')
son += father[i];
else if (father[i] == '~')
son += father[++i] - 'A' + 'a';
else if (father[i] == 'v')
son += ' ';
}
第一步构造
stringstream ss;
ss << son;
while (ss >> s)
{
isHere.clear();
rep(i, 0, (int)s.size()) isHere.insert(s[i]);
if (isHere.count(arr[0]) && isHere.count(brr[0]))
continue;
if (isHere.count(arr[0]))
gouzhao(1, "1");
else if (isHere.count(brr[0]))
gouzhao(1, "0");
else
{
gouzhao(1, "0");
gouzhao(1, "1");
}
}
输出部分
for (auto it = q.begin(); it != q.end(); it++)
{
if (it != q.begin())
cout << "v";
cout << "(";
rep(i, 0, all)
{
if (i)
cout << "^ ";
if ((*it)[i] == '0')
cout << "~" << arr[i] << " ";
else if ((*it)[i] == '1')
cout << arr[i] << " ";
}
cout << ")";
}
写在最后
特别鸣谢李老师,感谢他对于题目格式以及测试点信息的帮助。
标签:count,isHere,上机,gouzhao,father,ne,离散数学,U433730,析取范式 From: https://www.cnblogs.com/acidbarium/p/18206978