实验一：利用真值表法求主析取范式、主合取范式

• 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 命题公式的数目
// cnt2 是真值为 F 命题公式的数目
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，加关联词 "┐"  
                if (trueTable[i][j] == 0) {
                   ans += "┐ ";
                }
                // 加命题变元 j+'P' 对应的 ASCII码 
                ans += (j + 'P');
                // 若命题变元没遍历完，加关联词 "∧"
                if (j != n - 1) {
                    ans += " ∧ ";
                }
            }
            ans += ')'; // 加右括号 ")" 
            // 若真值为 T 的命题公式没遍历完，加关联词 "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 ++) {  
        // 若对应命题真值为 F 
        if (trueTable[i][n] == 0) { 
            tmpcnt ++; // 更新命题个数
            ans += '('; // 加左括号 "(" 
            // 遍历此行的各个命题
            for (int j = 0; j < n; j ++) {  
                // 如果命题真值为 T，加关联词 "┐" 
                if (trueTable[i][j] == 1) {
                    ans += "┐ ";
                }
                // 加命题变元 "P"    
                ans += (j + 'P');
                // 若命题变元没遍历完，加关联词 " V "
                if (j != n - 1) {
                    ans += " V ";
                }
            }
            ans += ')'; // 加右括号 ")" 
            // 若真值为 F 的命题公式没遍历完，加关联词 "∧"   
            if (tmpcnt < cnt2) {
                ans += " ∧ ";
            }
        }
    }
    // 输出主析取范式的字符串
    cout << ans << endl;
}
 
int main() {
    cout << "请输入命题变元的个数 :" << 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;
}

实验二：集合上二元关系性质的判断与实现

• 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);
    // 清空输入缓冲区，以便下次读取 
    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）读取序偶，构建关系矩阵 
void get_relation(int (*a)[100], char *p) {
    int k1, k2;
    char ch1, ch2;
    printf("输入关系的各个序偶（以 <*,*> 结束）：\n");
    while(1) {
        printf("<");
        // 输入后立即读取 ch1，不以回车结束
        ch1 = getche();
        printf(",");
        // 输入后立即读取 ch2，不以回车结束
        ch2 = getche();
        printf(">\n"); 
        if(ch1 == '*' && ch2 == '*') // 输入序偶 <*,*> 读取结束
            break;
        k1 = get_position(ch1, p); // 取得 ch1 在 p 中的位置
        k2 = get_position(ch2, p); // 取得 ch2 在 p 中的位置
        // 将关系矩阵相应元素置 1 
        a[k1][k2] = 1;
    }
}

// D）输出关系矩阵 
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("{ ");
    // 遍历关系矩阵 
    for(int i = 0; i < arry_w; i++)
        for(int j = 0; j<arry_w; j++)
            // 若相应元素为 1，则返回对应序偶 
            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}; // 初始化关系矩阵所有元素为 0 
    char point[100]; // 元素集合 point 
    int stlen; // 元素集合个数 stlen 
    char *p; // 元素集合指针 p 
    p = get_element(point); // 读取 point，得到 p 
    stlen = strlen(point); 
    get_relation(a, p); // 读取序偶，构建关系矩阵
    
    printf("序偶集合为：");
    output_relate(a, stlen, p); // 输出序偶集合 
    printf("关系矩阵为：\n");
    output_relat_array(a,stlen); // 输出关系矩阵 
    printf("该关系具有的性质：");
    
    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; 
}

实验三：偏序关系中求盖住关系，格伦中判定有补格

• Covering relation and Judging complementation.cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;
int count = 0;  // 从 0 开始计数
int n;  // 正整数
int factors[100];  // 存因子的数组 
int matrixs[100][100] = {0};  // 关系矩阵初始化为 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){ // 如果满足整除，设为 1
                matrixs[i][j] = 1;
            }
        }
    }
    // 输出偏序关系 
    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;  // 去掉自反性，设为 0 
                if(matrixs[i][j] && matrixs[j][k]){
                    matrixs[i][k] = 0;  // 去掉传递性，设为 0 
                }
            }
        }
    }
    // 输出盖住关系
    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;
}

// 求最大公因子（辗转相除法） 
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]); // 最大公约数，即最大下界
            Lcm = factors[i]*factors[j] / Gcd; // 最小公倍数，即最小上界
            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(); // 求盖住关系，并输出 
    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; // 图的结点，图的边 
int G[Size][Size]; // 图的邻接矩阵 
 
void Generate(){ 
    printf("\n>>> 正在生成...\n",n,m);
    int cnt=0;
    srand(time(NULL));
    while(cnt<m){ // 随机取结点，连接边 
        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行有奇数个 1 
            flag++;
        }
    }
    if(flag==0){ // 若没有行有奇数个 1  
        return 0; // 欧拉回路
    }
    else if(flag==2){ // 若有两行有奇数个 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次方复杂度,计算可达性矩阵
        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为欧拉回路个数 
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(">>> 请输入无向图的结点个数:"); scanf("%d",&n);
        printf(">>> 请输入无向图的边的个数:"); scanf("%d",&m);
        if(m>n*(n-1)/2){
            printf("\n>>> %d个结点的无向图最多有%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){ // 若此行有奇数个 1 
                        record[cnt++]=i;
                        FindLu(i); // 输出，循环中断 
                        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){ // 若此行有奇数个 1 
                        record[cnt++]=i;
                        FindLu(i); // 输出，循环继续 
                        cnt--;
                    }
                }
            }
        }
        else{ 
            printf(">>> 这个图既不是欧拉图，也不是半欧拉图\n"); 
        }
    }
    return 0;
}