1、实验目的

通过动态优先权算法的模拟加深对进程概念进程调度过程的理解。

2、实验内容

1. 用C语言来实现对N个进程采用动态优先权优先算法的进程调度。
2. 每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：

• 进程标识数 ID。
• 进程优先数 PRIORITY，并规定优先数越大的进程，其优先权越高。
• 进程已占用的CPU时间CPUTIME。
• 进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0。•••• 进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，将进入阻塞状态。
• 进程被阻塞的时间BLOCKTIME，表示已足赛的进程再等待BLOCKTIME个时间片后，将转换成就绪状态。
• 进程状态START。
• 队列指针NEXT，用来将PCB排成队列。

3. 优先数改变的原则：

1、实验目的

了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

2、实验内容

1. 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
2. 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
   作业1申请130KB。
作业2申请60KB。
作业3申请100KB。
作业2释放60KB。
作业4申请200KB。
作业3释放100KB。
作业1释放130KB。
作业5申请140KB。
作业6申请60KB。
作业7申请50KB。
作业6释放60KB。

请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。

实验代码

1、实验目的

通过具体的文件存储空间的管理、文件的物理结构、目录结构和文件操作的实现，加深对文件系统内部功能和实现过程的理解。

2、实验内容

1. 在内存中开辟一个虚拟磁盘空间作为文件存储器，在上面实现一个简单单用户文件系统。退出时应该将该虚拟文件系统保存到磁盘上，以便下次可以再将它恢复到内存对虚拟磁盘空间中。
2. 文件存储空间对分配可以采用显式链接分配或者其他的办法。
3. 空闲空间的管理可以选择位示图或者其他的办法。如果采用位示图来管理文件存储空间，并采用显式链接分配方式，那么可以将位示图合并到FAT中。
4. 文件目录结构采用多级目录结构。为了简单起见，可以不使用索引结点，其中的每个目录项应包含文件名、物理地址、长度等信息，还可以通过目录项实现对文件对读和写的保护。
5. 要求提供以下有关的操作：

1
2
3
4
5
6
7
8
9
10
11

√format：对文件存储器进行格式化，即按照文件系统对结构对虚拟磁盘空间进行布局，并在其上创建根目录以及用于管理文件存储空间等的数据结构。
√mkdir：用于创建子目录；
√rmdir：用于删除目录；
√ls：用于显示目录；
√cd：用于更改当前目录；
√create：用于创建文件；
√open：用于打开文件；
√close：用于关闭文件；
√write：用于写文件；
√read：用于读文件
√rm：用于删除文件。

代码

1、实验目的

通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。

2、实验内容

• 假设每个页面中可存放10条指令，分配给一作业的内存块数为4。
• 用C语言模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已经在内存中，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面置换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
• 置换算法：请分别考虑OPT、FIFO和LRU算法。
• 作业中指令的访问次序按下述原则生成：

• 50%的指令是顺序执行的。
• 25%的指令是均匀分布在前地址部分。
• 25%的指令时均匀分布在后地址部分。

具体的实施办法是：

2020-07-27

55. 跳跃游戏

思路

1. 对nums数组，令nums[i] += i,这样表示i位置最远可以走到的距离
2. 算法

从i = 0开始
对于当前i，可以从0走到nums[i]，选取0-nums[i]的最大值，如果最大值大于等于n-1，则可以到达最后，若小于，重复这个步骤，除非i=最大值，则不能到达最后

1. 为了降低时间复杂度，创建一个数组v，v[i] = max(nums[k]), k = 0,1,…,i

2020-07-25

Z 字形变换

AC代码

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

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        int n = s.size();
        string temp[numRows];
        int t_numRows = 0;
        int p = 0;
        while(p < n) {
            while(p < n && t_numRows < numRows) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows++;
            }
            t_numRows = numRows -2;
            while (p < n && t_numRows > 0) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows--;
            }
        }
        string res;
        for(int i = 0 ; i < numRows; i++) {
            res = res + temp[i];
        }
        return res;
    }
};

优化思路

1. 两层while循环多次判断p<n,效率底下，实际上只需要当t_numRows0或t_numRowsnumRows-1时改变方向即可

2. 实际上需要的string数组长度是min(n, numRows)

   优化代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   class Solution { public: string convert(string s, int numRows) { if (numRows <= 1) { return s; } int n = int(s.size()); int len = min(numRows, n); vector<string> temp(len); int t_numRows = 0; bool goingDown = false; for(int i = 0; i < n; i++) { temp[t_numRows] += s[i]; if (t_numRows == 0 || t_numRows == numRows-1) { goingDown = !goingDown; } t_numRows += goingDown ? 1 :-1; } string res; for (int i = 0; i < len; i++) res += temp[i]; return res; } };

   再次优化

   可以直接找新旧数列的数字关系，直接计算

   优化代码

   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

   class Solution { public: string convert(string s, int numRows) { if (numRows <= 1) { return s; } int len_s = int(s.size()); int unit =(2*numRows-2); int n = len_s/unit; int remain = len_s%unit; string res(len_s, 0); for (int i = 0; i < len_s; i++) { int p = 0; if (i%unit == 0) { p = i/unit+1; } else { int r = i%unit + 1,c = i/unit+1; if (r > numRows) { r = unit-r+2; p = 1; } else if (r == numRows) { p = 1-c; } p += n + (n*2)*(r-2) + 2*(c-1) + min(r-1, remain)+1; if (remain > numRows) { p += max(r-(unit-remain+2),0); } } res[p-1] = s[i]; } return res; } };

   最终成绩

   执行用时：8 ms, 在所有 C++ 提交中击败了98.89%的用户

   内存消耗：7.7 MB, 在所有 C++ 提交中击败了100.00%的用户

PROBLEM

This time, you are supposed to find A+B where A and B are two polynomials.

#### Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:

K N1 aN1 N2 aN2 … NK aNK

where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<⋯<N2<N1≤1000.

PROBLEM

Calculate a+b and output the sum in standard format – that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

Input Specification:

Each input file contains one test case. Each case contains a pair of integers a and b where $−10^6≤a,b≤10^6$. The numbers are separated by a space.

Output Specification:

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

题目

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n 不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：

每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n (1<n≤100)的值，数字间用空格隔开。

题目

大侦探福尔摩斯接到一张奇怪的字条：我们约会吧！ 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm。大侦探很快就明白了，字条上奇怪的乱码实际上就是约会的时间星期四 14:04，因为前面两字符串中第 1 对相同的大写英文字母（大小写有区分）是第 4 个字母 D，代表星期四；第 2 对相同的字符是 E ，那是第 5 个英文字母，代表一天里的第 14 个钟头（于是一天的 0 点到 23 点由数字 0 到 9、以及大写字母 A 到 N 表示）；后面两字符串第 1 对相同的英文字母 s 出现在第 4 个位置（从 0 开始计数）上，代表第 4 分钟。现给定两对字符串，请帮助福尔摩斯解码得到约会的时间。

输入格式：

输入在 4 行中分别给出 4 个非空、不包含空格、且长度不超过 60 的字符串。

输出格式：

在一行中输出约会的时间，格式为 DAY HH:MM，其中 DAY 是某星期的 3 字符缩写，即 MON 表示星期一，TUE 表示星期二，WED 表示星期三，THU 表示星期四，FRI 表示星期五，SAT 表示星期六，SUN 表示星期日。题目输入保证每个测试存在唯一解。