ENIGMA

参考编译器介绍本次实验预备阶段主要学习参考了经典的Pascal编译器，现进行一定的介绍。 总体结构课程组提供的Pascal编译器总体结构为词法分析、语法分析、错误处理、语义分析、代码生成和代码优化六个部分。 接口设计该编译器并未进行模块化设计，而是将各函数放在一个文件下，在调用时设定形参实参进行数据的交互。主要函数如下： nextch 读取下一个字符 test 检查符号合法性 error 打印错误信息 typ处理类型 typedeclaration处理自定义类型 constant处理常量 adjustscale处理实数 variabledeclaration处理普通变量 procdeclaration处理过程和函数 parameterlist...

基础知识渐进符号渐进紧确界 、渐进上界 、渐进下界 。 三种符号图例如下： 分析方法三种分析标准：最好情况分析、最差情况分析、平均（期望）情况分析。 和式求解 ， ， 。 主定理法对形如 的递归式，存在解 。 进一步推导得出：当 时，存在 ；当 时，存在 ；当 时，存在 。 特别的，如果 的形式为 ，则可进一步简化为：当 时，存在 ；当 时，存在 ；当 时，存在 。 分治算法算法原理分解为子问题，递归求解，合并子问题。 经典问题归并排序对于一串数字数组进行排序。将原数组不断划分为小数组，直至该数组元素为 ，在进行比较。完成小数组比较后，比较合并数组。时间复杂度 。 对数列 从小到大排序。 分组为 。 第一次归并后 ，第二次归并后 ，第三次归并后 。 最大子数组在给定的数字数组（包含正数和负数）中，找到一个连续的子数组，使得这个子数组的元素和最大。将原数组不断划分为小数组，直至该数组元素为 ，计算元素和最大值。合并时比较中点左侧最大值，中点右侧最大值，跨中点最大值。时间复杂度为 。 对数列 ...

1 判断正误 对下面的每个描述，请判断其是正确或错误，或无法判断正误。对于你判为错误的描述，请说明它为什么是错的。 如果一个问题是 NP-Hard 问题，那么它一定是 NP 问题。 P 问题 ∩ NPC 问题 = 。 若 TSP 问题无法在多项式时间内被解决，则 3-SAT 问题也无法在多项式时间内被解决。 对某问题 X NP 而言，若可以证明规约式 3-SAT X ，则 X NPC 。 分析： 错误。所有的 NP 问题都能约化到 NP-Hard 问题，但是 NP-Hard 问题不一定是一个 NP 问题。 NP 问题可在多项式时间内验证其解正确性，而 NP-Hard 问题则不一定。 无法确定。P 问题指可以在多项式时间内解决的问题，而 NP 完全问题指可以在多项式时间内转化的 NP 问题。目前无法证明 P 问题与 NP 问题之间的关系，若 P = NP 那么 P = NPC，P 问题 ∩ NPC 问题 = 。 正确。TSP（旅行商问题）和 3-SAT（三可满足性问题）都属于 NP 完全问题，按照 NP 完全问题的性质，如果一种 NP...

1 医院排队问题 在一个医院中，有 个病人排队等待就诊，医院每次只能接诊 人。每个病人有一个病情严重度 ，不同病人的病情严重度可以相同。 越大表示病情越严重，病情越严重的病人应当越优先就诊，形式化地说：对于任意两个病人,，如果接诊顺序 ，那么一定有 。同时，每个病人还需要一定的时间 来完成就诊。记每个病人在排队时的等待时间为 ，即从第一个人开始看病，到自己看完病为止的时间。 请你安排病人接诊的顺序，在关注病人病情严重程度的前提下最小化总的等待时间 。 例如，有 , , 号三位病人前来就诊，，那么就诊顺序应该安排为 号 - 号 - 号，总等待时间为 。 请设计一个高效算法，描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。 分析：这是一个最优化队列问题。根据题目限制，病人病情严重程度具有排列的最高优先级，首先对 进行排序。剩余 个病人时， 病情相同的情况下，接诊病人 ，总等待时间增加 。因此，在病情相同的时候，应优先治疗就诊时间短的病人。因此，整体思路是以病情严重程度为高优先级标准，就诊时间为低优先级标准，同时对病人排序，获得接诊顺序 ...

1 不完美字符串问题 对于一个长度为 的仅由 和 构成的字符串 ，其不完美度定义为所有相邻字符对中互不相同的字符对数量的和。比如，长度为 的字符串 “” 的不完美度为 ，这是由 和 两个相邻数对贡献得到的。形式化地，字符串 的不完美度如下式： (运算的结果取决于其中布尔表达式的真值。若为假，其值为 ，若为真，其值为 ) 现给定一个长度为 的字符串 ，每一位仅由 、 和 组成。你需要将其中的每一个 替换成 或者 ，且最小化字符串 的不完美度 。 例如，给定的字符串为 “”，一种使不完美度最小的替换方案为 “”，其不完美度为 ，可以证明，没有其他替换方案，请使用动态规划算法求解最小的不完美度，并给出一个替换方案。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。 分析：本问题可以使用动态规划的方法求解，对于长度为 的字符串的第 个字符，其与前 个字符组成的字符串之间的关系会决定前 个字符组成的字符串的不完美度与前 个字符组成的字符串的不完美度间的关系。当 时， ；当 时， 。替换 获得最小不完美度字符串时，当 ...

请给出 T (n) 尽可能紧凑的渐进上界并予以说明。 答案： 说明：对于任意，存在，则可以得出。 答案： 说明：对于任意，存在，则可以得出或，其中。 答案： 说明：对于任意，存在，则可以得出，进一步可以得到。 答案： 说明：对于任意，存在，则可以得出，其中。 答案： 说明：对于任意，存在，则可以得出。 答案： 说明：对于任意，存在，则可以得出。 答案： 说明：对于任意，存在。 游戏获奖问题 在一场射击比赛中，有名选手参加比赛，每名选手的得分都不同，记为，其中第名选手的得分为，且对于任意的有。按照比赛规则，分数排名为前的选手可以获得与其得分相等的奖金（包括第名）。例如，当有名选手参加比赛，得分为时，排名位于前 的选手得分为 ，则主办方应该发放奖金元。请你设计一个算法，计算这次比赛主办方一共要发放多少奖金。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。 解： 该问题即求数组最大的个元素求和值为多少。将数组从大到小按照顺序排序，选取头部个元素求和即可。 伪代码如下，时间复杂度在： 奇数因子和问题 定义...

第一章 概论 低级语言：字位码、机器语言、汇编语言。与特定机器有关，功效高但使用复杂且易出错。 高级语言：C、Java等语言。不依赖具体机器，移植性好易维护。 源程序：汇编或高级语言编写的待翻译程序； 目标程序：目标语言编写的程序； 翻译程序：将源程序转换为目标程序的程序。 源程序使用汇编，目标程序是机器语言，此翻译程序就是汇编程序；源程序使用高级语言，此翻译程序就是编译程序。 编译过程指将高级语言程序翻译为目标语言程序的过程。 五个阶段：词法分析、语法分析、语义分析与生成中间代码、代码优化、生成目标程序。 七个逻辑部分：词法分析、语法分析、语义分析与生成中间代码、代码优化、生成目标程序、符号表管理、出错处理。 遍：对源程序（以及源程序中间形式）从头到尾扫描一次，并进行相应处理。 编译程序通常分为前端（分析，与源语言有关）和后端（综合，与目标机有关）。 第二章 文法与语言概念 文法/语法：对语言结构的定义与描述。 语法规则：描述句子的语法结构的规则。 用 ::=...

第一章 概述 文件系统：数据以文件形式保存在外存，存取以记录为单位，程序数据有一定独立性，文件与数据一一对应，数据共享性差冗余度大（存储消耗大，容易造成数据不一致性） 数据库系统：数据集成及共享（核心技术：数据模型、数据独立性） 数据库系统管理特点：全组织的复杂数据结构，数据冗余度小易扩充，数据和程序的独立性、映像功能、统一的数据控制、最小存取单位是数据项 数据库中模型分为两类：概念模型（信息模型）、数据模型（层次、网状、关系模型）。概念模型用于现实世界到信息世界，数据模型以计算机系统的形式对数据建模。 数据模型：抽象和表示现实世界中的是数据和信息。（严格定义的概念集合） 概念模型：基于信息世界主要概念，表达应用中各种语义。 概念模型基本概念： 实体（Entity）：客观存在并可区分的事物； 属性（Attribute）：实体所具有的某一特性； 码（Key）：唯一标识实体的属性集； 域（Domain）：某个/些属性的取值范围（一组具有相同数据类型值的集合）； 实体型（Entity...

实现不带 .b 后缀指令 你需要实现不带 .b 后缀的指令，但仍需兼容带有 .b 后缀的指令，如 ls 与 ls.b 都应能够正确列出当前目录下的文件。 外部指令的执行实际上是在spawn函数中打开可执行的指令文件创建新进程，并将其装载在新建子进程中，运行指令文件中的主程序。实现思路是更改文件打开程序，当文件名对应文件存在时直接打开即可，不存在时文件名末尾加.b再次尝试打开。 在spawn()函数中更改文件打开方式，具体代码如下： 1234567891011121314151617//user/lib/spawn.c spawn()if ((fd = open(prog, O_RDONLY)) < 0) //尝试打开文件{ int len = 0; char newProg[128]; for (len = 0; len < 128 && prog[len] != '\0'; len++) { newProg[len] = prog[len]; } newProg[len++] = '.'; newProg[len++] =...

思考题Thinking 6.1 更改前的代码： 123456789101112131415161718192021int main(){ switch (fork()) { case -1: break; case 0: /* 子进程 - 作为管道的读者 */ close(fildes[1]); /* 关闭不用的写端 */ read(fildes[0], buf, 100); /* 从管道中读数据 */ printf("child-process read:%s",buf); /* 打印读到的数据 */ close(fildes[0]); /* 读取结束，关闭读端 */ exit(EXIT_SUCCESS); default: /* 父进程 - 作为管道的写者 */ close(fildes[0]); /* 关闭不用的读端 */ write(fildes[1], "Hello world\n", 12); /* 向管道中写数据 */ close(fildes[1]); /* 写入结束，关闭写端...