请不要照搬源代码,仅提供思路
实验一:利用真值表法求取主析取范式以及主合取范式的实现
实验目的:通过编程实现主析取范式以及主合取范式的真值表求法以巩固相关理论的掌握
编程实现用真值表法求取含三个以内变量的合式公式的主析取范式和主合取范式
要求:
从屏幕输入含三个以内变量的合式公式(其中联结词按照从高到底的顺序出现)
规范列出所输合式公式的真值表
给出相应主析取和主合取范式
语言:Java
开始是想用散列映射存储变量-真假值键值对的,但是迭代过程中Collection类可能需要反复复制,于是改用数组。
遇到的第二个难点是如何将字符串变为可执行代码,搜索资料发现可以使用引入JEXL依赖包解决,但是我不想使用maven项目,于是继续搜索发现jdk6的ScriptEngineManager可以解决。
注意这里其实用Python会更好,eval函数可以直接便表达式,java还要导入包,会提示以后的版本(当前13.0.2)ScriptEngineManager将会舍弃
Part 1
数据结构与存储结构,函数调用关系,数据传递方式:
所使用的数据结构:
读入数据用正则表达式切割,存储到HashSet中(本质是值全部为null的哈希表),避免重复读入变量;
为了方便读取与存储,将变量与值分别用数组存储,并传入函数;
极大项与极小项分别存储到ArrayList(底层是数组)中构成主合取范式和主析取范式;
所使用的存储结构:
- 开始使用散列存储变量值可以避免重复,然后转为顺序存储。
- 基本上采用顺序存储
函数调用关系与数据传递方式:
Part 2
- 核心代码部分
1 | public class Main1 { |
Part 3
- 实验截图
实验二:集合上二元关系性质判定的实现
实验目的:通过编程实现集合上二元关系性质的判定以巩固相关理论的掌握;
要求:
输入:集合X的元素个数(不超过5个元素,必做);X上关系的序偶个数(选做)
输出关系矩阵(由程序随机生成)
输出性质描述,不具备的性质需给出反例描述
语言:Java
采用数组来生成关系矩阵,随机生成本来想用生成一个就将那个位置排除待分配队列的,但是实现较为麻烦,就牺牲时间复杂度来换取简单的实现。
最好的情况是$O(n)$,但是有可能无限循环
求传递闭包使用的是时间复杂度为$O(n^3)$的$Warshall$算法
Part 1
实验中所使用的数据结构和存储结构,给出函数之间的调用关系和数据传递方式
数据结构与存储结构:
二维数组,顺序存储。
函数调用关系:
Part 2
给出核心算法的C++或Java等语言的源代码,并加上详细注释,分析算法的时间复杂度;
源代码:
Main2.java 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116public 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>以及是有补格3,>2,>1,>1,>
语言:C++
采用全局静态变量减少传值影响效率。
Part 1
数据结构与存储结构,函数调用关系,数据传递方式:
数据结构与存储结构:
vector存储因数
二维数组存储关系矩阵
均为顺序存储
- 函数调用关系和数据传递方式
函数调用关系都是顺序调用,Check函数检查是否为有补格,调用getGcd函数计算最大公因数。采用全局静态变量所以无参数传递。
- 函数调用关系和数据传递方式
Part 2
- 关键部分源代码与时间复杂度
1 |
|
时间复杂度:
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)))$
由加法法则,总时间复杂度为
Part 3
实验截图
实验四:图的随机生成及欧拉(回)路的确定
目的:通过编程实现图的随机生成及欧拉(回)路判定和查找以巩固相关理论的掌握
要求:对给定m个结点和n条边,随机生成相关邻接矩阵以确定某无向简单图
基于度的计算进行欧拉图和半欧拉图的判定
若符合则给出至少一条欧拉回路或欧拉路
本来想用list嵌套构建二维数组的,但是要自己写迭代和初始化,比较麻烦,于是使用了numpy这个模块,简化了代码
寻找欧拉路和欧拉回路我用的是DFS深度优先搜索,如果是半欧拉图,欧拉通路肯定从奇数度节点开始,但是循环总能循环到的,如果不是太大的图影响不大。
完成实验后发现还有用邻接表法的,时间复杂度为$O(n+e)$
Part 1
数据结构与存储结构与函数调用关系传值方式
数据结构使用的是数组(numpy数组)
存储结构为顺序结构
函数调用关系传值方式如下
Part 2
- 关键部分代码与时间复杂度
1 | import random |
时间复杂度分析:
n为节点个数
构建邻接矩阵 $O(n^2)$
检测是否为(半)欧拉图 $O(n^2)$
假设单个节点查找欧拉路径时间复杂度为$v$
深度搜索寻找欧拉路:$O(v^2)$
所以总时间复杂的为$O(v^2)$
Part 3
实验截图