實驗一:利用真值表法求主析取范式瘪撇、主合取范式
- Using truthTable to find the pdnf and pcnf.cpp
#include <iostream>
#define MAX 100000
using namespace std;
short trueValue[MAX]; // 真值
short trueTable[MAX][10]; // 真值表
int n, i;
// cnt1 是真值為 T 命題公式的數(shù)目
// cnt2 是真值為 F 命題公式的數(shù)目
int cnt1 = 0, cnt2 = 0;
// A)主析取范式
void Output_pdnf() {
cout << "主析取范式為 : " << endl;
string ans = "";
int tmpcnt = 0;
// 遍歷真值表每一行
for (int i = 0; i < (1 << n); i ++) {
// 若此行命題公式真值為 T
if (trueTable[i][n] == 1) {
tmpcnt ++; // 更新 tmpcnt
ans += '('; // 加左括號 "("
// 遍歷此行的各個命題
for (int j = 0; j < n; j ++) {
// 如果命題真值為 F槐脏,加關(guān)聯(lián)詞 "┐"
if (trueTable[i][j] == 0) {
ans += "┐ ";
}
// 加命題變元 j+'P' 對應(yīng)的 ASCII碼
ans += (j + 'P');
// 若命題變元沒遍歷完,加關(guān)聯(lián)詞 "∧"
if (j != n - 1) {
ans += " ∧ ";
}
}
ans += ')'; // 加右括號 ")"
// 若真值為 T 的命題公式?jīng)]遍歷完储玫,加關(guān)聯(lián)詞 "V"
if (tmpcnt < cnt1) {
ans += " V ";
}
}
}
// 輸出主析取范式的字符串
cout << ans << endl;
}
// B)主合取范式
void Output_pcnf() {
cout << "主合取范式為 : " << endl;
string ans = "";
int tmpcnt = 0;
// 遍歷真值表每一行
for (int i = 0; i < (1 << n); i ++) {
// 若對應(yīng)命題真值為 F
if (trueTable[i][n] == 0) {
tmpcnt ++; // 更新命題個數(shù)
ans += '('; // 加左括號 "("
// 遍歷此行的各個命題
for (int j = 0; j < n; j ++) {
// 如果命題真值為 T,加關(guān)聯(lián)詞 "┐"
if (trueTable[i][j] == 1) {
ans += "┐ ";
}
// 加命題變元 "P"
ans += (j + 'P');
// 若命題變元沒遍歷完键俱,加關(guān)聯(lián)詞 " V "
if (j != n - 1) {
ans += " V ";
}
}
ans += ')'; // 加右括號 ")"
// 若真值為 F 的命題公式?jīng)]遍歷完获雕,加關(guān)聯(lián)詞 "∧"
if (tmpcnt < cnt2) {
ans += " ∧ ";
}
}
}
// 輸出主析取范式的字符串
cout << ans << endl;
}
int main() {
cout << "請輸入命題變元的個數(shù) :" << endl;
cin >> n;
cout << "請輸入命題公式的真值 :" << endl;
for (i = 0; i < (1 << n); i ++) {
// 輸入各命題真值
cin >> trueValue[i];
// 若命題真值為 T,更新 cnt1岛马,pcnf
if (trueValue[i]) {
cnt1 ++;
}
// 若命題真值為 F,更新 cnt2屠列,pdnf
else {
cnt2 ++;
}
}
// 給真值表各個命題真值賦值
for (i = 0; i < (1 << n); i ++) {
int tmp = i;
// 保證全為 0 或 1啦逆,即 T 或 F
for (int j = n - 1; j >= 0; j--) {
trueTable[i][j] = tmp % 2;
tmp /= 2;
}
}
// 給真值表每行命題公式賦值
for (i = 0; i < (1 << n); i++) {
trueTable[i][n] = trueValue[i];
}
// 輸出主析取范式
Output_pdnf();
// 輸出主合取范式
Output_pcnf();
return 0;
}
實驗二:集合上二元關(guān)系性質(zhì)的判斷與實現(xiàn)
- Judge properties of binary relation on set.cpp
# include <stdio.h>
# include <string.h>
# include <conio.h> // 控制臺輸入輸出庫
// A)讀取元素集合
char *get_element(char *p) {
printf("輸入集合的(不能有空格):");
// 讀取字符串 p
gets(p);
// 清空輸入緩沖區(qū),以便下次讀取
fflush(stdin);
return p;
}
// B)獲取元素在集合中的位置
int get_position(char ch, char *point) {
for(int i = 0; *(point + i); i++) {
// 返回 ch 在 point 中的下標
if(*(point + i) == ch)
return i;
}
return 0;
}
// C)讀取序偶笛洛,構(gòu)建關(guān)系矩陣
void get_relation(int (*a)[100], char *p) {
int k1, k2;
char ch1, ch2;
printf("輸入關(guān)系的各個序偶(以 <*,*> 結(jié)束):\n");
while(1) {
printf("<");
// 輸入后立即讀取 ch1夏志,不以回車結(jié)束
ch1 = getche();
printf(",");
// 輸入后立即讀取 ch2,不以回車結(jié)束
ch2 = getche();
printf(">\n");
if(ch1 == '*' && ch2 == '*') // 輸入序偶 <*,*> 讀取結(jié)束
break;
k1 = get_position(ch1, p); // 取得 ch1 在 p 中的位置
k2 = get_position(ch2, p); // 取得 ch2 在 p 中的位置
// 將關(guān)系矩陣相應(yīng)元素置 1
a[k1][k2] = 1;
}
}
// D)輸出關(guān)系矩陣
void output_relat_array(int (*a)[100], int arry_w) {
for(int i = 0; i<arry_w; i++) {
for(int j = 0; j<arry_w; j++)
printf("%4d", a[i][j]);
printf("\n");
}
}
// E)輸出序偶集合
void output_relate(int (*a)[100], int arry_w,char *p) {
int count=0;
printf("{ ");
// 遍歷關(guān)系矩陣
for(int i = 0; i < arry_w; i++)
for(int j = 0; j<arry_w; j++)
// 若相應(yīng)元素為 1苛让,則返回對應(yīng)序偶
if(a[i][j] == 1)
printf("<%c, %c>,",*(p+i), *(p+j));
count++;
// \b表示刪除一個字符
printf("\b }");
printf("\n");
}
/*
1)自反性
*/
int ZF(int (*a)[100], int n) {
// 初始化判斷
int flag1 = 1;
for(int i = 0; i < n; i++) {
// 若存在對角元素為 0
if(!a[i][i]) {
// 則不具有自反性
flag1 = 0;
break;
}
}
return flag1;
}
/*
2)反自反性
*/
int FZF(int (*a)[100], int n) {
// 初始化判斷
int flag2 = 1;
for(int i = 0; i < n; i++) {
// 若存在對角元素為 1
if(a[i][i]) {
// 則不具有反自反性
flag2 = 0;
break;
}
}
return flag2;
}
/*
3)對稱性
*/
int DC(int (*a)[100], int n) {
// 初始化判斷
int flag3 = 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) {
// 若存在對稱元素不相等
if(a[i][j] != a[j][i] && i != j)
// 則不具有對稱性
flag3 = 0;
break;
}
return flag3;
}
/*
4)反對稱性
*/
int FDC(int (*a)[100],int n) {
int flag4 = 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
// 若存在對稱元素都為 1
if(a[i][j] && a[j][i] && i != j) {
// 則不具有反對稱性
flag4 = 0;
break;
}
return flag4;
}
/*
5)傳遞性
*/
int CD(int (*a)[100], int n) {
// 初始化判斷
int flag5 = 1;
// 遍歷序偶所有可能的傳遞組合
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
// 若不滿足傳遞定義
if(a[i][j] && a[j][k] && !a[i][k]) {
// 則不具有傳遞性
flag5 = 0;
break;
}
return flag5;
}
int main() {
int a[100][100] = {0}; // 初始化關(guān)系矩陣所有元素為 0
char point[100]; // 元素集合 point
int stlen; // 元素集合個數(shù) stlen
char *p; // 元素集合指針 p
p = get_element(point); // 讀取 point沟蔑,得到 p
stlen = strlen(point);
get_relation(a, p); // 讀取序偶,構(gòu)建關(guān)系矩陣
printf("序偶集合為:");
output_relate(a, stlen, p); // 輸出序偶集合
printf("關(guān)系矩陣為:\n");
output_relat_array(a,stlen); // 輸出關(guān)系矩陣
printf("該關(guān)系具有的性質(zhì):");
if(ZF(a, stlen)) {
printf("自反性 ");
}
if(FZF(a,stlen)) {
printf("反自反性 ");
}
if(DC(a,stlen)) {
printf("對稱性 ");
}
if(FDC(a,stlen)) {
printf("反對稱性 ");
}
if(CD(a,stlen)) {
printf("傳遞性 ");
}
return 0;
}
實驗三:偏序關(guān)系中求蓋住關(guān)系狱杰,格倫中判定有補格
- Covering relation and Judging complementation.cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int count = 0; // 從 0 開始計數(shù)
int n; // 正整數(shù)
int factors[100]; // 存因子的數(shù)組
int matrixs[100][100] = {0}; // 關(guān)系矩陣初始化為 0
void factor(){
cout << "The factors of " << n << " are: ";
for(int i = 1; i <= n/2; i++){
if(n % i == 0){
factors[count++] = i;
cout << i << ", ";
}
}
factors[count] = n;
cout << n << endl << endl;
}
void cover(){
for(int i = 0; i <= count; i++){
for(int j = 0; j <= count; j++){
if(factors[j] % factors[i] == 0){ // 如果滿足整除瘦材,設(shè)為 1
matrixs[i][j] = 1;
}
}
}
// 輸出偏序關(guān)系
cout << "The partial relation is: { ";
for(int i = 0; i <= count; i++){
for(int j = 0; j <= count; j++){
if(matrixs[i][j]){
cout << " <" << factors[i] << "," << factors[j] << ">";
}
}
}
cout << " }" << endl << endl;
for(int i = 0; i <= count; i++){
for(int j = 0; j <= count; j++){
for(int k = 0; k <= count; k++){
matrixs[k][k] = 0; // 去掉自反性,設(shè)為 0
if(matrixs[i][j] && matrixs[j][k]){
matrixs[i][k] = 0; // 去掉傳遞性仿畸,設(shè)為 0
}
}
}
}
// 輸出蓋住關(guān)系
cout << "The covering relation is: { ";
for(int i = 0; i <= count; ++i){
for(int j = 0; j <= count; ++j){
if(matrixs[i][j]){
cout << " <" << factors[i] << "," << factors[j] << ">";
}
}
}
cout << " }" << endl << endl;
}
// 求最大公因子(輾轉(zhuǎn)相除法)
int gcd(int x, int y){
int m;
while(m != 0){
m = x % y;
x = y;
y = m;
}
return x;
}
void complemented_lattice(){
bool flag;
int Gcd, Lcm;
for(int i = 1; i < count; i++){
flag = false; // 初始化 flag = false
for(int j = 1; j < count; j++){
if(i == j)
continue;
Gcd = gcd(factors[i], factors[j]); // 最大公約數(shù)食棕,即最大下界
Lcm = factors[i]*factors[j] / Gcd; // 最小公倍數(shù),即最小上界
if(Gcd == 1 && Lcm == n){ // 若是補元错沽,flag = true
flag = true;
break;
}
if(!flag){ // 若存在元素沒有補元簿晓,則此格不是有補格
cout << "This is not complemented lattice!" << endl;
return;
}
}
}
// 若所有元素均有補元,則此格是有補格
cout << "This is complemented lattice!" << endl;
return;
}
int main(){
cout << "Please input a positive integer: ";
cin >> n;
cout << endl;
factor(); // 求 n的因子千埃,并保存
cover(); // 求蓋住關(guān)系憔儿,并輸出
complemented_lattice(); // 判斷有補格
return 0;
}
實驗四:圖的隨機生成,歐拉(回)路的確定
- Random generation of graphs and Euler loop.cpp
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define Size 1000
using namespace std;
int n, m; // 圖的結(jié)點放可,圖的邊
int G[Size][Size]; // 圖的鄰接矩陣
void Generate(){
printf("\n>>> 正在生成...\n",n,m);
int cnt=0;
srand(time(NULL));
while(cnt<m){ // 隨機取結(jié)點谒臼,連接邊
int x=rand()%n;
int y=rand()%n;
if(x!=y && G[x][y]==0){
G[x][y]=1;
G[y][x]=1;
cnt++;
}
}
printf(">>> 生成完成!!!\n\n");
printf(">>> 隨機生成圖的鄰接矩陣 G=\n");
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%d ",G[i][j]);
}
printf("\n");
}
printf("\n");
}
int Judge() {
int flag=0;
for(int i=0;i<n;i++){
int cnt=0;
for(int j=0;j<n;j++){
if(G[i][j]==1){
cnt++;
}
}
if(cnt%2==1){ // 若第 i行有奇數(shù)個 1
flag++;
}
}
if(flag==0){ // 若沒有行有奇數(shù)個 1
return 0; // 歐拉回路
}
else if(flag==2){ // 若有兩行有奇數(shù)個 1
return 1; // 歐拉路
}
else{
return -1;
}
}
int P[Size][Size]; // 可達性矩陣
int T[Size][Size]; // 存放 G
int TT[Size][Size]; // 存放 G的 K次方
int JudgeLianTong(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
P[i][j]=G[i][j];
T[i][j]=G[i][j];
}
}
for(int k=2;k<=n;k++){ //n的4次方復(fù)雜度,計算可達性矩陣
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int t=0;
for(int a=0;a<n;a++){
t+=T[i][a]*G[a][j];
}
if(t==0){
TT[i][j]=0;
}
else{
TT[i][j]=1;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
T[i][j]=TT[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(T[i][j]>0 || P[i][j]>0 ){
P[i][j]=1;
}
}
}
}
printf(">>> 隨機生成圖的可達性矩陣 P=\n");
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%d ",P[i][j]);
}
printf("\n");
}
printf("\n");
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j && P[i][j] ==0){
return 0;
}
}
}
return 1;
}
int choice,has,cnt; // cnt為歐拉回路個數(shù)
int vis[Size][Size];
int record[Size];
void FindLu(int cur){
if(choice==1 && has==1) return;
if(cnt==m+1){
for(int i=0;i<cnt;i++){
if(i==0) printf("%d",record[i]);
else printf("->%d",record[i]);
}
printf("\n");
has=1;
}
else{
for(int i=0;i<n;i++){
if(G[cur][i]==1 && vis[cur][i]==0 ){
vis[i][cur]=vis[cur][i]=1;
record[cnt++]=i;
FindLu(i);
cnt--;
vis[i][cur]=vis[cur][i]=0;
}
}
}
}
int main(){
do{
printf(">>> 請輸入無向圖的結(jié)點個數(shù):"); scanf("%d",&n);
printf(">>> 請輸入無向圖的邊的個數(shù):"); scanf("%d",&m);
if(m>n*(n-1)/2){
printf("\n>>> %d個結(jié)點的無向圖最多有%d條邊唱逢!\n\n",n,n*(n-1)/2);
}
}while(m>n*(n-1)/2);
Generate(); //隨機生成圖
if(JudgeLianTong()==0){ //判斷連通性
printf(">>> 這個圖不是一個連通圖,所以也不是歐拉圖和半歐拉圖\n");
}
else{
printf("\n>>> 這個圖是連通圖\n");
int tmp=Judge(); //判斷歐拉圖
if(tmp==0){
printf(">>> 這個圖是一個歐拉圖\n");
printf("\n-----------------1.打印一個歐拉回路------------------\n");
printf("-----------------2.打印所有歐拉回路------------------\n\n");
printf(">>> 請輸入你的選擇:"); scanf("%d", &choice);
if(choice==1){
printf(">>> 其中一歐拉回路為:\n");
record[cnt++]=0;
FindLu(0); // 輸出
cnt--;
}
else if(choice==2){
printf(">>> 所有的歐拉回路為:\n");
for(int i=0;i<n;i++){
record[cnt++]=i;
FindLu(i); // 輸出
cnt--;
}
}
}
else if(tmp==1){
printf(">>> 這個圖是一個半歐拉圖\n");
printf("\n-----------------1.打印一個歐拉路------------------\n");
printf("-----------------2.打印所有歐拉路------------------\n\n");
printf(">>> 請輸入你的選擇:"); scanf("%d",&choice);
if(choice==1){
for(int i=0;i<n;i++){
int t=0;
for(int j=0;j<n;j++){
if(G[i][j]==1){
t++;
}
}
if(t%2==1){ // 若此行有奇數(shù)個 1
record[cnt++]=i;
FindLu(i); // 輸出屋休,循環(huán)中斷
cnt--;
break;
}
}
}
else if(choice==2){
printf(">>> 所有的歐拉路為:\n");
for(int i=0;i<n;i++){
int t=0;
for(int j=0;j<n;j++){
if(G[i][j]==1){
t++;
}
}
if(t%2==1){ // 若此行有奇數(shù)個 1
record[cnt++]=i;
FindLu(i); // 輸出坞古,循環(huán)繼續(xù)
cnt--;
}
}
}
}
else{
printf(">>> 這個圖既不是歐拉圖,也不是半歐拉圖\n");
}
}
return 0;
}