请不要照搬源代码，仅提供思路

实验一：利用真值表法求取主析取范式以及主合取范式的实现

实验目的：通过编程实现主析取范式以及主合取范式的真值表求法以巩固相关理论的掌握

编程实现用真值表法求取含三个以内变量的合式公式的主析取范式和主合取范式

要求：

从屏幕输入含三个以内变量的合式公式（其中联结词按照从高到底的顺序出现）

规范列出所输合式公式的真值表

给出相应主析取和主合取范式

语言：Java

开始是想用散列映射存储变量-真假值键值对的，但是迭代过程中Collection类可能需要反复复制，于是改用数组。

遇到的第二个难点是如何将字符串变为可执行代码，搜索资料发现可以使用引入JEXL依赖包解决，但是我不想使用maven项目，于是继续搜索发现jdk6的ScriptEngineManager可以解决。

注意这里其实用Python会更好，eval函数可以直接便表达式，java还要导入包，会提示以后的版本（当前13.0.2）ScriptEngineManager将会舍弃

Part 1

数据结构与存储结构，函数调用关系，数据传递方式：
- 所使用的数据结构：
  - 读入数据用正则表达式切割，存储到HashSet中（本质是值全部为null的哈希表），避免重复读入变量；
  - 为了方便读取与存储，将变量与值分别用数组存储，并传入函数；
  - 极大项与极小项分别存储到ArrayList（底层是数组）中构成主合取范式和主析取范式；
- 所使用的存储结构：
  - 开始使用散列存储变量值可以避免重复，然后转为顺序存储。
  - 基本上采用顺序存储
- 函数调用关系与数据传递方式：

Part 2

核心代码部分

Main1.java

public class Main1 {
    static ScriptEngineManager manager = new ScriptEngineManager();
    static ScriptEngine engine = manager.getEngineByName("js");
    static String inp;//可计算表达式
    static String input;//用户输入
    static ArrayList<String> MCP = new ArrayList<>();//主合取范式
    static ArrayList<String> MDP = new ArrayList<>();//主析取范式

    public static void main(String[] args) throws ScriptException {
        /**
        *输出信息省略
        */
        
        //正则表达式切割读取变量存入数组
        Pattern p = Pattern.compile("[&|!()->]+");
        input = in.nextLine();
        String[] arr = p.split(input);

        //排除T、F和空串（如果第一个是括号会产生空串），存入HashSet
        HashSet<String> variables = new HashSet<>();
        for (String variable : arr) {
            if (!variable.equals("") && !variable.equals("F") && !variable.equals("T")) {
                variables.add(variable);
            }
        }

        //替换成可计算表达式
        inp = input
                .replace("T", "true")
                .replace("F", "false")
                .replace("|", "||")
                .replace("&", "&&");//初步处理
        if (inp.contains(">") || inp.contains("-")) {//根据连接词顺序切分并处理
            String[] parts = inp.split("[>-]");
            String[] sign = inp.split("[^>-]");
            int n = 0;
            for(String s : sign){
                if(s.equals("-")){
                    parts[n+1] = "(("+parts[n]+")"+"&&"+"("+parts[n+1]+"))"+
                            "||"+"(!("+parts[n]+")"+"&&"+"!("+parts[n+1]+"))";
                    n++;
                }
                else if(s.equals(">")){
                    parts[n+1] = "!("+parts[n]+")"+"||"+"("+parts[n+1]+")";
                    n++;
                }
            }
            inp=parts[parts.length-1];处理结果返回
        }
        /**
        * 输出信息部分省略
        */

        boolean[] tf = new boolean[variables.size()];
        Arrays.fill(tf, true);//临时存储真值表并且初始化为true
        String[] keys = new String[variables.size()];
        keys = variables.toArray(keys);
        Table(keys, tf, 0);//集合转数组并调用Table函数

        System.out.println("主合取范式为：");
        System.out.println(MCP.toString().replace(", ", "∧"));
        System.out.println("主析取范式为：");
        System.out.println(MDP.toString().replace(", ", "∨"));
    }

    /**
     * @param keys   变量名
     * @param values 变量值
     * @param n      变量序号
     */
    private static void Table(String[] keys, boolean[] values, int n) throws ScriptException {
        if (n == keys.length - 1) {//到达最后一个变量
            execute(keys, values);
            values[n] = !values[n];//切换真假值

            execute(keys, values);//调用函数进行计算
        } else {//未到达最后一个变量，进行递归
            Table(keys, values, n + 1);//此时为T
            values[n] = !values[n];
            Table(keys, values, n + 1);//此时为F
        }
        values[n] = !values[n];//切换真假值，为下一次递归做准备
    }

    private static void execute(String[] keys, boolean[] values) throws ScriptException {

        String in = inp;
        //变量替换
        for (int i = 0; i < keys.length; i++) {
            in = in.replace(keys[i], values[i] + "");
        }
        String ans = "" + engine.eval(in);

        //存储极大项与极小项
        if (ans.equals("true")) {//主析取范式
            StringBuilder insert = new StringBuilder("(" + (values[0] ? "" : "┐") + keys[0]);
            for (int i = 1; i < keys.length; i++) {
                insert.append("∧").append(values[i] ? "" : "┐").append(keys[i]);
            }
            insert.append(")");
            MDP.add(insert.toString());
        } else if (ans.equals("false")) {//主合取范式
            /**
            *内容与主析取范式的收集类似，三目运算符条件式加个!,改∧为∨，添加进MCP中即可。省略
            */
        }
        
        //输出信息
        System.out.println((Arrays.toString(values) + "\t" + ans)
                .replace("true", "T")
                .replace("false", "F"));
    }

}

Part 3

实验截图

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

实验目的：通过编程实现集合上二元关系性质的判定以巩固相关理论的掌握；

要求：

输入：集合X的元素个数（不超过5个元素，必做）；X上关系的序偶个数（选做）

输出关系矩阵（由程序随机生成）

输出性质描述，不具备的性质需给出反例描述

语言：Java

采用数组来生成关系矩阵，随机生成本来想用生成一个就将那个位置排除待分配队列的，但是实现较为麻烦，就牺牲时间复杂度来换取简单的实现。
最好的情况是$O(n)$，但是有可能无限循环
求传递闭包使用的是时间复杂度为$O(n^3)$的$Warshall$算法

Part 1

实验中所使用的数据结构和存储结构，给出函数之间的调用关系和数据传递方式
- 数据结构与存储结构：
  
  二维数组，顺序存储。
- 函数调用关系：

Part 2

给出核心算法的C++或Java等语言的源代码，并加上详细注释，分析算法的时间复杂度；

源代码：

Main2.java

public class Main2 {
    static int n;//集合元素个数
    static int m;//序偶个数

    public static void main(String[] args) {
        /**
         * 读取m和n部分省略
         */

        //随机产生序偶，若重复则i不增加
        for (int i = 0; i < m; ) {
            int x = (int) (Math.random() * 100 % n);
            int y = (int) (Math.random() * 100 % n);
            if (arr[x][y] == 0) {
                arr[x][y] = 1;
                i++;
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(arr[i]));
        }

        //一次调用函数判断
        isReflexive(arr);
        isAntiReflexive(arr);
        isSymmetry(arr);
        isAntiSymmetry(arr);
        isTransitive(arr);

    }


    //自反性判断，对角线有0则直接返回，空集不执行，满足自反
    static void isReflexive(int[][] arr) {
        for (int i = 0; i < n; i++) {
            if (arr[i][i] == 0) {
                System.out.println("不满足自反关系，因为(" +
                        (i + 1) + ", " + (i + 1) +
                        ")应该为1");
                return;
            }
        }
        System.out.println("满足自反关系");
    }

    //反自反性判断，只要有1就不行
    static void isAntiReflexive(int[][] arr) {

        for (int i = 0; i < n; i++) {
            if (arr[i][i] == 1) {
                System.out.println("不满足反自反关系，因为(" +
                        (i + 1) + ", " + (i + 1) +
                        ")应该为0");
                return;
            }
        }
        System.out.println("满足反自反关系");
    }

    //对称性判断，对称位置不相等直接返回
    static void isSymmetry(int[][] arr) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i][j] != arr[j][i]) {
                    System.out.println("不满足对称关系，因为(" +
                            (i + 1) + ", " + (j + 1) + ")与(" +
                            (j + 1) + ", " + (i + 1) + ")不相等");
                    return;
                }
            }
        }
        System.out.println("满足对称关系");
    }

    //反对称性判断，除对角线元素外，1关于对角线对称位置为1直接返回
    static void isAntiSymmetry(int[][] arr) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i][j] == 1 && arr[j][i] != 0) {
                    System.out.println("不满足反对称关系，因为(" +
                            (i + 1) + ", " + (j + 1) + ")为1时(" +
                            (j + 1) + ", " + (i + 1) + ")不为0");
                    return;
                }
                if (arr[j][i] == 1 && arr[i][j] != 0) {
                    System.out.println("不满足反对称关系，因为(" +
                            (j + 1) + ", " + (i + 1) + ")为1时(" +
                            (i + 1) + ", " + (j + 1) + ")不为0");
                    return;
                }
            }
        }
        System.out.println("满足反对称关系");
    }

    //Warshall算法
    static void isTransitive(int[][] arr) {
        for (int i = 0; i < n; i++) {//加行
            for (int j = 0; j < n; j++) {//被加行
                if (i == j) {
                    continue;
                }
                if (arr[j][i] == 1) {
                    for (int k = 0; k < n; k++) {
                        if (arr[j][k] == 0 && arr[i][k] == 1) {//被加数是1不会影响自身改变
                            System.out.println("不满足传递性，缺少序偶<" +
                                    (j + 1) + ", " + (k + 1) + ">");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("满足传递性");
    }
}

时间复杂度分析（均按照最坏情况）：
- isReflexive和isAntiReflexive的时间复杂度为$O(n)$
- isSymmetry和isAntiSymmetry的时间复杂度最坏情况为(梯形)$O(\displaystyle \frac{n(n-1)}{2})=O(n^2)$
- isTransitive的时间复杂度为$O(n^3)$
总时间复杂度由加法法则为

Part 3

给出测试数据及运行结果、实验相关结论等。

实验三：偏序关系中盖住关系的求取及格论中有补格的判定

目的：通过编程实现偏序关系中盖住关系的求取及格论中有补格的判定以巩固相关理论的掌握

要求：

从屏幕输入一个正整数

列出由该整数所有因子构成的盖住关系

给出由其因子构成的格是否为有补格的判定

如：输入6，则输出<1, 2>, <1, 3>, <2, 6>, <3, 6>以及是有补格

语言：C++

采用全局静态变量减少传值影响效率。

Part 1

数据结构与存储结构，函数调用关系，数据传递方式：
- 数据结构与存储结构：
  
  vector存储因数
  
  二维数组存储关系矩阵
  
  均为顺序存储
  - 函数调用关系和数据传递方式
    函数调用关系都是顺序调用，Check函数检查是否为有补格，调用getGcd函数计算最大公因数。采用全局静态变量所以无参数传递。

Part 2

关键部分源代码与时间复杂度

Main3.cpp

#include <bits/stdc++.h>
using namespace std;

//下面定义全局变量，减少传参
static int n;               //最大数字
static vector<int> factors; //因数数组
static int number;          //因数个数
static int **matrix;        //关系矩阵

//求因数并存储
void calFactor()
{
    for (int i = 1; i <= n / 2; ++i) //因为对称，只需运行一半
    {
        if (n % i == 0)
        {
            factors.push_back(i);
        }
    }
    factors.push_back(n);
    number = factors.size();
}
void calCover()
{
    int i, j, k;
    //初始化
    matrix = new int *[number];
    for (i = 0; i < number; i++)
    {
        matrix[i] = new int[number];
        memset(matrix[i], 0, number * sizeof(int));
    }
    //构建关系矩阵
    for (i = 0; i < number; i++)
    {
        for (j = i + 1; j < number; j++) //去掉自反性和传递性
        {
            if (factors[j] % factors[i] == 0) //满足整除
            {
                matrix[i][j] = 1;
            }
        }
    }
    //去传递性
    for (i = 0; i < number; i++)
    {
        for (j = 0; j < number; j++)
        {
            for (k = 0; k < number; k++)
            {

                if (matrix[i][j] && matrix[j][k])
                {
                    matrix[i][k] = 0;
                }
            }
        }
    }
    //输出信息
    cout << "The Cover Set: { ";
    for (int i = 0; i < number; i++)
    {
        for (int j = i + 1; j < number; j++)
        {
            if (matrix[i][j])
                cout << "<" << factors[i] << ", " << factors[j] << "> ";
        }
    }

    cout << "}" << endl;
}

//求最大公约数
int getGcd(int a, int b)
{
    return b ? getGcd(b, a % b) : a;
}

void Check()
{
    bool flag;
    int gcd, lcm;
    for (int i = 1; i < number - 1; i++)
    {
        flag = false;
        for (int j = 1; j < number - 1; j++)
        {
            if (i == j)
                continue;
            gcd = getGcd(factors[i], factors[j]); //最大公约数
            lcm = factors[i] / gcd * factors[j];  //最小公倍数
            if (gcd == 1 && lcm == n)             //最大下界为 1，最小上界为 n
            {
                flag = true;
                break;
            }
        }
        if (!flag) //只要有一个找不到补元，那么直接返回
        {
            cout << "This is not a complemented lattice!" << endl;
            return;
        }
    }
    cout << "This is a complemented lattice!" << endl;
}

int main()
{
    cout << "Iunput a number: ";
    cin >> n;
    calFactor();
    calCover();
    Check();
    return 0;
}

时间复杂度：
- calFactor()时间复杂度为$O(n)$
- calCover()有三部分
  
  第一个是构建关系矩阵并去掉自反性
  
  时间复杂度为$O(n)+O(\displaystyle \frac{n(n+1)}{2})=O(n^2)$
  
  第二部分是去掉自反性
  
  时间复杂度为$(n^3)$
  
  第三部分是输出盖住关系
  
  时间复杂度为$O(n^2)$
  
  所以此函数时间为$(n^3)$_image006.png)
- getGcd()时间复杂度
  
  辗转相除法运用递归实现，时间复杂度为$O(log(max(a,b)))$
- Check()时间复杂度为$O(n^2log(max(a,b)))$
- 由加法法则，总时间复杂度为
  
  $O(n^3)$

Part 3

实验截图

实验四：图的随机生成及欧拉（回）路的确定

目的：通过编程实现图的随机生成及欧拉（回）路判定和查找以巩固相关理论的掌握

要求：对给定m个结点和n条边，随机生成相关邻接矩阵以确定某无向简单图

基于度的计算进行欧拉图和半欧拉图的判定

若符合则给出至少一条欧拉回路或欧拉路

本来想用list嵌套构建二维数组的，但是要自己写迭代和初始化，比较麻烦，于是使用了numpy这个模块，简化了代码

寻找欧拉路和欧拉回路我用的是DFS深度优先搜索，如果是半欧拉图，欧拉通路肯定从奇数度节点开始，但是循环总能循环到的，如果不是太大的图影响不大。

完成实验后发现还有用邻接表法的，时间复杂度为$O(n+e)$

Part 1

数据结构与存储结构与函数调用关系传值方式

数据结构使用的是数组（numpy数组）

存储结构为顺序结构

函数调用关系传值方式如下

Part 2

关键部分代码与时间复杂度

import random
import numpy as np

global n  # 节点数量
global m  # 边数量
global arr  # 邻接矩阵
global check  # 检查矩阵
global queue  # 连线节点次序


# 创造并初始化数组
def create():
    global arr, n, m
    arr = np.zeros((n, n), dtype=int)
    i = 0
    while i != m:
        x = random.randint(0, n - 1)
        y = random.randint(0, n - 1)
        if arr[x][y] == 0 and x != y:  # 无向图保证对称且反自反
            arr[y][x] = arr[x][y] = 1
            i += 1


# 检查是否为（半）欧拉图
def checkEuler():
    global arr
    degree = arr.sum(axis=1)  # 节点度数
    odd = np.where(degree % 2 != 0)[0].shape[0]  # 奇数度结点个数
    if 0 in degree:
        print('非连通图，这不是（半）欧拉图')
        return False
    if odd == 0:
        print('这是欧拉图')
        return True
    elif odd == 2:
        print('这是半欧拉图')
        return True
    else:
        print('这不是（半）欧拉图')
        return False


def dfs(i):
    global arr, n, m, check, queue
    for x in range(n):  # 遍历邻接点
        if arr[i][x] == 1:  # 如果邻接
            if check[i][x] == 1:  # 如果i-x已经走过
                continue  # 下一个邻接点
            else:  # 如果没走过
                check[i][x] = check[x][i] = 1  # 记录i-x已经走过
                if dfs(x):  # i-x的路线走下去如果找到欧拉（回）路
                    break  # 跳出循环
                else:  # 找不到欧拉（回）路
                    check[i][x] = check[x][i] = 0  # 清楚i-x的记录
                    continue  # 下一个邻接点
    if (check == arr).all():  # 如果边已经全部遍历，检查矩阵应该和邻接矩阵相同
        queue.append(i)
        return True
    else:
        return False


def main():
    global n, m, arr, check, queue
    queue = []
    n = int(input('请输入元素的个数: '))
    m = int(input('请输入边数，应小于等于' + str(n * (n - 1) // 2) + ': '))
    create()
    print(arr)
    if checkEuler():
        check = np.zeros((n, n), dtype=int)
        for i in range(n):
            if dfs(i):
                break
        print(queue)  # 正走倒走都一样


main()

时间复杂度分析：

n为节点个数

构建邻接矩阵 $O(n^2)$

检测是否为（半）欧拉图 $O(n^2)$

假设单个节点查找欧拉路径时间复杂度为$v$

深度搜索寻找欧拉路：$O(v^2)$

所以总时间复杂的为$O(v^2)$

Part 3

实验截图

open=>start: 主函数 userInput=>inputoutput: 输入合式公式 processes=>operation: 处理输入 results=>operation: 传递变量与值数组的引用给Table函数 end=>end: 结束 open->userInput->processes->results results->end{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}o=>start: Table函数 cond=>condition: 判断是否为最后一个变量 proc=>operation: 第n个变量值为T pro=>operation: 第n个变量值为F chh=>operation: 第n个变量值为T dhh=>operation: 第n个变量值为F resultss=>operation: 调用递归，n+1，传值进Table results=>operation: 调用递归，n+1，传值进Table ree=>operation: 输出并将极大项或极小项添加进数组 re=>operation: 输出并将极大项或极小项添加进数组 end=>end: 结束 o->cond cond(no)->proc->results->pro->resultss->end cond(yes)->chh->re->dhh->ree->end{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}st=>start: 开始 end=>end: 结束 io=>inputoutput: 输入元素个数n和序偶个数m op1=>operation: isReflexive op2=>operation: isAntiReflexive op3=>operation: isSymmetry op4=>operation: isAntiSymmetry op5=>operation: isTransitive st->io->op1->op2->op3->op4->op5->end{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}st=>start: 开始 io=>inputoutput: 输入节点数量n与边数量m create=>operation: 调用create初始化并输出 check=>condition: 是否为（半）欧拉图 op=>operation: 第i个节点调用dfs查找欧拉（回）路 ot=>inputoutput: 输出欧拉（回）路 i++=>operation: i++ c=>condition: 是否找到 end=>end: end st->io->create->check check(yes)->op->c c(no)->i++->op c(yes)->ot->end check(no)->end{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}st=>start: 入参i，第i个节点 op1=>operation: for x in range(节点个数) ch1=>condition: 如果i-x邻接 ch=>condition: i-x边是否走过 op2=>operation: 记录i-x边已经走过 ch2=>condition: dfs(x)==True？ op3=>operation: 取消i-x边走过的记录 ch3=>condition: 邻接矩阵与记录矩阵相等 op4=>operation: 添加i进队列 end=>end: 返回(邻接矩阵==记录矩阵) st->op1->ch1 ch1(yes)->ch(yes)->op1 ch1(no)->op1 ch(no)->op2->ch2 ch2(no)->op3->op1 ch2(yes)->ch3 ch3(yes)->op4->end ch3(no)->end{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}

头发收集屋

南邮离散数学实验

实验一：利用真值表法求取主析取范式以及主合取范式的实现

Part 1

Part 2

Part 3

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

Part 1

Part 2

Part 3

实验三：偏序关系中盖住关系的求取及格论中有补格的判定

Part 1

Part 2

Part 3

实验四：图的随机生成及欧拉（回）路的确定

Part 1

Part 2

Part 3

实验一：利用真值表法求取主析取范式以及主合取范式的实现

Part 1

Part 2

Part 3

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

Part 1

Part 2

Part 3

实验三： 偏序关系中盖住关系的求取及格论中有补格的判定

Part 1

Part 2

Part 3

实验四：图的随机生成及欧拉（回）路的确定

Part 1

Part 2

Part 3

实验三：偏序关系中盖住关系的求取及格论中有补格的判定