页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]_页面置换算法c++实现

⌛️

---

---

Page Replacement Algorithm ⌨️

---

零、运行结果图

◆ 对上图说明：后面分别用四种算法，对该样例都进行了检验，结果一致。

● 后文代码的常见变量：
  [1] n：物理页框数。
  [2] len：地址走向的长度。
  [3] save_Frame：含有n个格子的物理页框（即一个长度为n的动态数组，指针申请的）。
  [4] interview_Array：长度为len的地址数组（即一个长度为len的动态数组，指针申请的）。

---

一、最佳置换算法（OPT）

● 替换规则：将以后永不使用的或在最长时间内不再被访问的页面进行替换。

● 这是一种理想化的算法，有点 “先知” 算法的味道，故在实际上是难以实现的。但它可作为衡量各种实用的页面置换算法的标准。

● 样例：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为后面需访问地址里面没有 “1”，所以用 “5” 置换 “1”。
  ② 第二个红箭头：因为后面需访问的地址里面，“2” 是最长时间内不被访问的，所以置换它。
  ③ 当进程运行完毕时，系统进行了 3 次置换，缺页中断次数为 6 次，即蓝色箭头加上红色箭头的个数。缺页率为 6/12 = 50% 。

● 算法设计：

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则执行[4](即未命中的情况)。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则执行[5](即未命中的情况)。

[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。

[5] 执行Find_LeastInteviewTime()函数，找出需要替换的页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()等函数在后文的完整代码中】

int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len)
{
	for (int i = sta; i < len; i++)
	{
		if (interview_Array[i] == addr)
			return i - sta;
	}
	return 99999;
}

void OPT_Agorithm()
{
	printf("欢迎使用 OPT \n");
	int n = 0, len = 0, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
		
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int addr;		// 地址
	int cnt = 0;			// 物理页框已装满的份数(大于 n 时无效) 
	int score = 0;			// 成功的访问次数
	int fail_time = 0;		// 不成功的访问次数
	int iter = 0;	// 迭代次数
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];		// 读取地址
		iter++;
		...
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但有空间 
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* least_Time = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					least_Time[i] = Find_LeastInteviewTime(iter, save_Frame[i], interview_Array, len);
					if (least_Time[i] > max_Time)
					{
						max_Time = least_Time[i];
						index = i;
					}
				}
				...
				save_Frame[index] = addr;
				...
			}
		}
	}
	...
}
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

● 运行结果：

---

二、先进先出算法（FIFO）

● 替换规则：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以替换。

● 依旧沿用上面的样例来图形化说明：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为 “2” 最先进来，所以用 “5” 置换 “2”。
  ② 当进程运行完毕时，系统进行了 6 次置换，缺页中断次数为 9 次，即蓝色箭头加上红色箭头的个数。缺页率为 9 /12 = 75% 。

● 算法设计：【in_HereTime[]：记录每个页面驻留的时间】

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后执行Update_InHereTime()函数来更新in_HereTime[]数组，然后返回执行步骤[1]，否则执行[4](即未命中的情况)。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后执行Update_InHereTime()函数来更新in_HereTime[]数组，然后返回执行步骤[1]，否则执行[5](即未命中的情况)。

[4] 把当前地址addr装入空闲的物理页框，然后执行Update_InHereTime()函数来更新in_HereTime数组，然后返回执行步骤[1]。

[5] 从in_HereTime[]找出最大值对应的那个页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】

void Update_InHereTime(int* in_HereTime, int n, int ind)
{
	for (int i = 0; i < n; i++)
		in_HereTime[i]++;
	if (ind != -1)
		in_HereTime[ind] = 0;
}

void FIFO_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
		
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int* in_HereTime = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		in_HereTime[i] = 0;		// 初始化都为零

	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
				Update_InHereTime(in_HereTime, cnt, -1);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				Update_InHereTime(in_HereTime, cnt, cnt);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
				Update_InHereTime(in_HereTime, n, -1);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					if (in_HereTime[i] > max_Time)
					{
						max_Time = in_HereTime[i];
						index = i;
					}
				}
				...
				save_Frame[index] = addr;
				...
				int ind = Find_Exist(save_Frame, n, addr);
				Update_InHereTime(in_HereTime, n, ind);
			}
		}
	}
	...
}
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

● 测试结果：

---

三、最近最久未使用算法（LRU）

● 替换规则：替换最近一段时间内最久未被使用的页面。

● 依旧沿用上面的样例来图形化说明：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为 “2” 最近被访问过，“1”刚刚才被调入，只有 “3” 最近最久未被访问，所以置换它。
  ② 当进程运行完毕时，系统进行了 4 次置换，缺页中断次数为 7 次，即蓝色箭头加上红色箭头的个数。缺页率为 7 /12 = 58.33% 。

● 算法设计：

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则(即未命中)执行[4]。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则(即未命中)执行[5]。

[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。

[5] 执行Find_LeastNotUseTime()函数，找出需要替换的页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】

int Find_LeastNotUseTime(int end, int addr, int* interview_Array)
{
	for (int i = end - 1; i >= 0; i--)
	{
		if (interview_Array[i] == addr)
			return end - i;
	}
	return 99999;
}

void LRU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
		
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		...
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但有空间
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* Not_UseTime = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					Not_UseTime[i] = Find_LeastNotUseTime(iter, save_Frame[i], interview_Array);
					if (Not_UseTime[i] > max_Time)
					{
						max_Time = Not_UseTime[i];
						index = i;
					}
				}
				...
				save_Frame[index] = addr;
				...
			}
		}
	}
	...
}
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

● 测试结果：

---

四、最不经常使用算法（LFU）

● 替换规则：把当前为止，访问次数最少的页面予以替换。

● 和上面的样例有一点不同(地址走向不同)：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，2，1，5，4，2，4，4 和 6。则 LFU 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为 “3” 被访问（即被命中）的次数为 0，而其他两个页面( “2” 和 “1” 都分别有 2、1 次命中)，所以“3” 的访问次数最少，所以置换它。
  ② 当进程运行完毕时，系统进行了 3 次置换，缺页中断次数为 6 次（即蓝色箭头加上红色箭头的个数）。缺页率为 6 /12 = 50% 。

● 算法设计：【interview_Time[]：记录每个页面被访问的次数】

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，并且使对应的interview_Time加1，然后返回执行步骤[1]，否则(即未命中)执行[4]。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，并且使对应的interview_Time加1，然后返回执行步骤[1]，否则(即未命中)执行[5]。

[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。

[5] 执行Find_LeastNotInterviewTime()函数，找出需要替换的页面地址(在物理页框中的)进行替换，并使对应的的interview_Time重新赋值为0，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】

int Find_LeastNotInterviewTime(int n, int* interview_Time)
{
	int min_Time = 99999;
	int ind;
	for (int i = 0; i < n; i++)
	{
		if (interview_Time[i] < min_Time)
		{
			min_Time = interview_Time[i];
			ind = i;
		}
	}
	return ind;
}

void LFU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int* interview_Time = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		interview_Time[i] = 0;

	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
				int ind = Find_Exist(save_Frame, cnt, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但有空间
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
				int ind = Find_Exist(save_Frame, n, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int index = Find_LeastNotInterviewTime(n, interview_Time);
				...
				save_Frame[index] = addr;
				...
			}
		}
	}
	...
}
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

● 测试结果：

---

五、完整代码 —— C语言版本

● 补充说明：完整代码中，还包含 “输出内存驻留的页面集合”【Print_Frame()函数】 、“缺页次数” 和 “缺页率” 等功能【Page_Loss_Rate()函数】。

#include <stdio.h>
#include <stdlib.h>
void OPT_Agorithm();
void FIFO_Agorithm();
void LRU_Agorithm();
void LFU_Agorithm();
double Page_Loss_Rate(int, int);
int Find_Exist(int*, int, int);
int Find_LeastInteviewTime(int, int, int*, int);
void Update_InHereTime(int*, int, int);
int Find_LeastNotUseTime(int, int, int*);
int Find_LeastNotInterviewTime(int, int*);
void Print_Frame(int*, int);
void Print_Menu();
void Init(int*, int*);

int main()
{
	int choice;
	do
	{
		Print_Menu();
		printf("请选择要实现的算法：");
		scanf_s("%d", &choice);
		switch (choice)
		{
		case 1:
			OPT_Agorithm();
			break;
		case 2:
			FIFO_Agorithm();
			break;
		case 3:
			LRU_Agorithm();
			break;
		case 4:
			LFU_Agorithm();
			break;
		case 0:
			break;
		}
		system("pause");
		system("cls");
	} while (choice);
	return 0;
}

/*
* 用于遍历 save_Frame[] 的 n 个存储页框, 是否有 “待定地址 -> addr”
* 如果有就返回 ture, 否则返回 false
*/
int Find_Exist(int* save_Frame, int n, int addr)
{
	for (int i = 0; i < n; i++)
	{
		if (save_Frame[i] == addr)
		{
			return i;
		}
	}
	return -1;
}

void Print_Menu()
{
	/* 输入模块 */
	printf("+---------------------------------------+\n");
	printf("|\t***算法清单***\t\t\t|\n");
	printf("|\t1.最佳置换算法(OPT)\t\t|\n|\t2.先进先出算法(FIFO)\t\t|\n");
	printf("|\t3.最近最久未使用算法(LRU)\t|\n|\t4.最不经常使用算法(LFU)\t\t|\n");
	printf("|\t0.退出\t\t\t\t|\n");
	printf("+---------------------------------------+\n");
}

void Print_Frame(int* save_Frame, int n)
{
	printf("\t");
	for (int i = 0; i < n; i++)
	{
		if (i == 0)
		{
			if (save_Frame[i] == -999)
				printf("/ /");
			else
				printf("/%d/", save_Frame[i]);
		}
		else
		{
			if (save_Frame[i] == -999)
				printf(" /");
			else
				printf("%d/", save_Frame[i]);
		}
	}
	printf("\n");
}

void Init(int* n, int* len)
{
	printf("请输入 n :");
	scanf_s("%d", n);

	printf("请输入地址走向的长度：");
	scanf_s("%d", len);
}

/*
 * 缺页中断率：
 * 假设进程 P 在运行中成功的内存访问次数为 s 
 * 不成功的访问次数为 F，则缺页中断率为 R = F/(S+F)
*/
double Page_Loss_Rate(int S, int F)
{
	double ans = 1.0 * F / (1.0 * S + 1.0 * F) * 100;
	return ans;
}

/*
* 最佳置换算法(OPT)：
* 将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
* 数据结构：数组
*/

int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len)
{
	for (int i = sta; i < len; i++)
	{
		if (interview_Array[i] == addr)
		{
			return i - sta;
		}
	}
	return 99999;
}
void OPT_Agorithm()
{
	printf("欢迎使用 OPT \n");
	int n = 0, len = 0, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");

	//测试样例： 1 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		printf("\n第%d轮：", iter);
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d\" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* least_Time = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					least_Time[i] = Find_LeastInteviewTime(iter, save_Frame[i], interview_Array, len);
					if (least_Time[i] > max_Time)
					{
						max_Time = least_Time[i];
						index = i;
					}
				}
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				free(least_Time);
			}
		}
		// printf("\n");
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
}

void Update_InHereTime(int* in_HereTime, int n, int ind)
{
	for (int i = 0; i < n; i++)
		in_HereTime[i]++;

	if (ind != -1)
		in_HereTime[ind] = 0;
}
/*
* 先进先出算法(FIFO)：
* 淘汰最先使用内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void FIFO_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");

	int* in_HereTime = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		in_HereTime[i] = 0;		// 初始化都为零

	//测试样例： 2 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, -1);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d\" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, cnt);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, n, -1);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					if (in_HereTime[i] > max_Time)
					{
						max_Time = in_HereTime[i];
						index = i;
					}
				}
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				Update_InHereTime(in_HereTime, n, ind);
			}
		}
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f\%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
	free(in_HereTime);
	return;
}

int Find_LeastNotUseTime(int end, int addr, int* interview_Array)
{
	for (int i = end - 1; i >= 0; i--)
	{
		if (interview_Array[i] == addr)
		{
			return end - i;
		}
	}
	return 99999;
}
/*
* 最近最久未使用算法(LRU)：
* 淘汰最近最久未被使用的页面。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LRU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");
	//测试样例： 3 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		printf("\n第%d轮：", iter);
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);

			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d \" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* Not_UseTime = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					Not_UseTime[i] = Find_LeastNotUseTime(iter, save_Frame[i], interview_Array);
					if (Not_UseTime[i] > max_Time)
					{
						max_Time = Not_UseTime[i];
						index = i;
					}
				}
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				free(Not_UseTime);
			}
		}
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
}

int Find_LeastNotInterviewTime(int n, int* interview_Time)
{
	int min_Time = 99999;
	int ind;
	for (int i = 0; i < n; i++)
	{
		if (interview_Time[i] < min_Time)
		{
			min_Time = interview_Time[i];
			ind = i;
		}
	}
	return ind;
}
/*
* 最不经常使用算法(LFU):
* 即选择最近一段时间内最长时间没有被访问过的页面进行置换
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LFU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");

	int* interview_Time = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		interview_Time[i] = 0;

	// 测试样例一：4 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	// 测试样例二：4 3 12 2 3 2 1 2 1 5 4 2 4 4 6
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, cnt, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d\" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int index = Find_LeastNotInterviewTime(n, interview_Time);
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				interview_Time[index] = 0;
				Print_Frame(save_Frame, n);
			}
		}
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f\%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
	free(interview_Time);
}
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514

---

六、完整代码 —— C++版本

● 补充说明：完整代码中，还包含 “输出内存驻留的页面集合”【Print_Frame()函数】 、“缺页次数” 和 “缺页率” 等功能【Page_Loss_Rate()函数】。

#include <iostream>
#include <stdlib.h>
using namespace std;
void OPT_Agorithm();
void FIFO_Agorithm();
void LRU_Agorithm();
void LFU_Agorithm();
double Page_Loss_Rate(int, int);
int Find_Exist(int*, int, int);
int Find_LeastInteviewTime(int, int, int*, int);
void Update_InHereTime(int*, int, int);
int Find_LeastNotUseTime(int, int, int*);
int Find_LeastNotInterviewTime(int, int*);
void Print_Frame(int*, int);
void Print_Menu();

int main()
{
	int choice;
	do
	{
		Print_Menu();
		cout << "请选择要实现的算法：";
		cin >> choice;
		switch (choice)
		{
		case 1:
			OPT_Agorithm();
			break;
		case 2:
			FIFO_Agorithm();
			break;
		case 3:
			LRU_Agorithm();
			break;
		case 4:
			LFU_Agorithm();
			break;
		case 0:
			break;
		}
		system("pause");
		system("cls");
	} while (choice);
	return 0;
}

/*
* 用于遍历 save_Frame[] 的 n 个存储页框, 是否有 “待定地址 -> addr”
* 如果有就返回 ture, 否则返回 false
*/
int Find_Exist(int* save_Frame, int n, int addr)
{
	for (int i = 0; i < n; i++)
	{
		if (save_Frame[i] == addr)
		{
			return i;
		}
	}
	return -1;
}

void Print_Menu()
{
	/* 输入模块 */
	cout << "+---------------------------------------+" << endl;
	cout << "|\t***算法清单***\t\t\t|" << endl;
	cout << "|\t1.最佳置换算法(OPT)\t\t|" << endl << "|\t2.先进先出算法(FIFO)\t\t|" << endl;
	cout << "|\t3.最近最久未使用算法(LRU)\t|" << endl << "|\t4.最不经常使用算法(LFU)\t\t|" << endl;
	cout << "|\t0.退出\t\t\t\t|" << endl;
	cout << "+---------------------------------------+" << endl;
}

void Print_Frame(int* save_Frame, int n)
{
	cout << "\t";
	for (int i = 0; i < n; i++)
	{
		if (i == 0)
		{
			if (save_Frame[i] == -999)
				cout << "/ /";
			else
				cout << "/" << save_Frame[i] << "/";
		}
		else
		{
			if (save_Frame[i] == -999)
				cout << " /";
			else
				cout << save_Frame[i] << "/";
		}
	}
	cout << endl;
}
void Init(int* n, int* len, int*& save_Frame, int*& interview_Array)
{
	cout << "请输入 n :";
	cin >> *n;
	save_Frame = new int[*n];
	for (int i = 0; i < *n; i++)
		save_Frame[i] = -999;

	cout << "请输入地址走向的长度：";
	cin >> *len;
	cout << "请输入地址走向:";
	interview_Array = new int[*len];
	for (int i = 0; i < *len; i++)
		cin >> interview_Array[i];
}

/*
* 缺页中断率：
* 假设进程 P 在运行中成功的内存访问次数为 s
* 不成功的访问次数为 F，则缺页中断率为 R = F/(S+F)
*/
double Page_Loss_Rate(int S, int F)
{
	double ans = 1.0 * F / (1.0 * S + 1.0 * F) * 100;
	return ans;
}

int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len)
{
	for (int i = sta; i < len; i++)
	{
		if (interview_Array[i] == addr)
		{
			return i - sta;
		}
	}
	return 99999;
}
/*
* 最佳置换算法(OPT)：
* 将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
* 数据结构：数组
*/
void OPT_Agorithm()
{
	cout << "欢迎使用 OPT " << endl;
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);
	//测试样例： 1 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		cout << endl << "第" << iter << "轮：";
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但有空间，" << "\" << addr << "\" 被装入 
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* least_Time = new int[n];
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					least_Time[i] = Find_LeastInteviewTime(iter, save_Frame[i], interview_Array, len);
					if (least_Time[i] > max_Time)
					{
						max_Time = least_Time[i];
						index = i;
					}
				}
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				delete[] least_Time;
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
}

void Update_InHereTime(int* in_HereTime, int n, int ind)
{
	for (int i = 0; i < n; i++)
	{
		in_HereTime[i]++;
	}
	if (ind != -1)
		in_HereTime[ind] = 0;
}
/*
* 先进先出算法(FIFO)：
* 淘汰最先使用内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void FIFO_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);

	int* in_HereTime = new int[n];
	for (int i = 0; i < n; i++)
		in_HereTime[i] = 0;		// 初始化都为零

	//测试样例： 2 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		cout << endl << "第" << iter << "轮：";
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, -1);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, cnt);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, n, -1);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					if (in_HereTime[i] > max_Time)
					{
						max_Time = in_HereTime[i];
						index = i;
					}
				}
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				Update_InHereTime(in_HereTime, n, ind);
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
	delete[]  in_HereTime;
	return;
}

int Find_LeastNotUseTime(int end, int addr, int* interview_Array)
{
	for (int i = end - 1; i >= 0; i--)
	{
		if (interview_Array[i] == addr)
		{
			// cout << " i = " << i << endl;
			return end - i;
		}
	}
	return 99999;
}
/*
* 最近最久未使用算法(LRU)：
* 淘汰最近最久未被使用的页面。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LRU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);

	//测试样例： 3 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		cout << endl << "第" << iter << "轮：";
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);

			}
			else // 未命中，但有空间
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* Not_UseTime = new int[n];
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					Not_UseTime[i] = Find_LeastNotUseTime(iter, save_Frame[i], interview_Array);
					if (Not_UseTime[i] > max_Time)
					{
						max_Time = Not_UseTime[i];
						index = i;
					}
				}
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				delete[] Not_UseTime;
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
}

int Find_LeastNotInterviewTime(int n, int* interview_Time)
{
	int min_Time = 99999;
	int ind;
	for (int i = 0; i < n; i++)
	{
		if (interview_Time[i] < min_Time)
		{
			min_Time = interview_Time[i];
			ind = i;
		}
	}
	return ind;
}
/*
* 最不经常使用算法(LFU):
* 即选择最近一段时间内最长时间没有被访问过的页面进行置换
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LFU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);

	int* interview_Time = new int[n];
	for (int i = 0; i < n; i++)
		interview_Time[i] = 0;

	// 测试样例一：4 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	// 测试样例二：4 3 12 2 3 2 1 2 1 5 4 2 4 4 6
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		cout << endl << "第" << iter << "轮：";
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, cnt, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但有空间
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int index = Find_LeastNotInterviewTime(n, interview_Time);
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				interview_Time[index] = 0;
				Print_Frame(save_Frame, n);
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
	delete[] interview_Time;
}
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488

---

七、参考附录

无。
(纯手敲，原创，可能存在未知 Bug，烦请指正…)

---

⭐️ ⭐️