南京邮电大学算法实验报告

南邮操作系统实验三实验报告（ 2014/ 2015 学年第一学期）课程名称操作系统教程实验名称页面调度算法的模拟实现实验时间2014 年12 月 3 日指导单位计算机软件学院指导教师徐鹤学生姓名楚灵翔班级学号B12040731 学院(系) 计算机学院专业软件工程实验报告实验名称页面调度算法的模拟实现指导教师徐鹤实验类型上机实验学时 2 实验时间2014.12.3一、实验目的和要求1、模拟实现页面调度算法中的FIFO、LRU和OPT算法2、进程的页面请求序列，即一系列页面号（页面号用整数表示，用空格作为分隔符），用来模拟待换入的页面；3、输出要求：显示缺页的总次数和缺页中断率二、实验环境(实验设备)VMware Workstation，Ubuntu三、实验过程描述#define n 12#define m 3int page[n]; //保存需要访问的页面int i,j,q,mem[m]={0},List[m][n],sum;char flag,f[n];void Init();void FIFO();void LRU();void main(){cout<<"*********************实验***********************"<<endl;< bdsfid="127" p=""></endl;<> cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;< bdsfid="129" p=""></endl;<>cout<<" ┃页面调度算法的模拟实现┃"<<endl;< bdsfid="131" p=""></endl;<>cout<<" ┠───────────────────────┨"<<endl;< bdsfid="133" p=""></endl;<>cout<<" ┃先进先出算法FIFO ┃"<<endl;< bdsfid="135" p=""></endl;<>cout<<" ┃最近追少使用算法LRU ┃"<<endl;< bdsfid="137" p=""></endl;<>cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;< bdsfid="139" p=""></endl;<>cout<<" 请输入页面访问序列:\n"<<" ";for(i=0;i<n;i++)< bdsfid="142" p=""></n;i++)<>cin>>page[i];cout<<endl;< bdsfid="145" p=""></endl;<>FIFO();Init();LRU();}void Init() //初始化函数{sum=0; //初始化计算缺页次数的变量for(int i=0;i<m;i++)< bdsfid="153" p=""></m;i++)<>mem[i]=0;for(i=0;i<m;i++)< bdsfid="156" p=""></m;i++)<>for(j=0;j<n;j++)< bdsfid="158" p=""></n;j++)<>List[i][j]=0;}void FIFO(){for(i=0;i<="">{q=0;while((page[i]!=mem[q])&&(q!=m))q++;if(q==m)flag='*'; //缺页，则置标志flag为'*' elseflag=' ';if(flag=='*'){for(j=m-1;j>0;j--) //淘汰最先调入的页面调入当前访问的mem[j]=mem[j-1];mem[0]=page[i];}for(j=0;j<m;j++)< bdsfid="178" p=""></m;j++)<>List[j][i]=mem[j];f[i]=flag;}cout<<" 0代表为空,*代表有缺页:\n";cout<<endl;< bdsfid="184" p=""></endl;<>cout<<"-----------FIFO算法结果------------"<<endl;< bdsfid="186" p=""></endl;<>for(i=0;i<m;i++)< bdsfid="188" p=""></m;i++)<>{for(j=0;j<n;j++)< bdsfid="191" p=""></n;j++)<>cout<<list[i][j]<<" ";<="" bdsfid="193" p=""></list[i][j]<<"> cout<<endl;}< bdsfid="195" p=""></endl;}<>for(i=0;i<n;i++)< bdsfid="197" p=""></n;i++)<>{if(f[i]=='*')sum++;cout<<f[i]<<" ";<="" bdsfid="202" p=""></f[i]<<">}cout<<"\n-----------------------------------"<<endl;<bdsfid="205" p=""></endl;<>cout<<"缺页次数是:"<<sum<<"缺页率是:"<<<endl;<="" bdsfid="207" p=""></sum<<"缺页率是:"<}void LRU(){for(i=0;i<="">{q=0;while((page[i]!=mem[q])&&(q!=m))q++;if(q==m)flag='*'; //缺页，则置标志flag为'*'elseflag=' ';for(j=q;j>0;j--)mem[j]=mem[j-1];mem[0]=page[i];for(j=0;j<m;j++)< bdsfid="225" p=""></m;j++)<>List[j][i]=mem[j];f[i]=flag;}cout<<endl;< bdsfid="229" p=""></endl;<>cout<<"------------LRU算法结果------------"<<endl;< bdsfid="231" p=""></endl;<>for(i=0;i<m;i++)< bdsfid="233" p=""></m;i++)<>{for(j=0;j<n;j++)< bdsfid="236" p=""></n;j++)<>cout<<list[i][j]<<" ";<="" bdsfid="238" p=""></list[i][j]<<"> cout<<endl;< bdsfid="240" p=""></endl;<>}for(i=0;i<n;i++)< bdsfid="243" p=""></n;i++)<>{if(f[i]=='*')sum++;cout<<f[i]<<" ";}<="" bdsfid="248" p=""></f[i]<<">cout<<endl;< bdsfid="250" p=""></endl;<>cout<<"-----------------------------------"<<endl;<bdsfid="252" p=""></endl;<>cout<<"缺页次数是:"<<sum<<"缺页率是:"<<<=""></sum<<"缺页率是:"<实验结果：四、实验小结（包括问题和解决方法、心得体会、意见与建议等）通过本次实验,我对于页面调度算法有了更加深刻的认识。

实验报告（2013/2014学年第一学期）课程名称算法分析与设计实验名称密码算法实验时间2014 年 5 月23 日指导单位计算机学院软件工程系指导教师张怡婷学生姓名班级学号B******** 学院(系) 软件工程专业软件工程实验报告三、实验原理及内容（包括操作过程、结果分析等）实验步骤1、RSA 算法是由麻省理工学院的Ron Rivest,Adi Shamir 和Len Adleman 于1977 年研制并于1978 年首次发表的一种算法，是第一个能同时用于加密和数字签名的算法，且易于理解和操作，因此作为一种通用公开密钥加密方式而受到推崇。

RSA 是一种分组密码，其中明文和密文都是小于某个n 的从0 到n-1 的整数，则分组的二进制值长度必须小于或等于log2n。

若以M 表示明文分组，而C 表示密文分组，则加密和解密的过程如下：C=Me mod nM=Cd mod n=(Me)d mod n=Med mod n发送方和接受方都必须知道n 的值。

发送方知道 e 的值，而只有接受方知道d 的值。

因此这是一种公开密钥为{e,n}，且私有密钥为{d,n}的公开密钥加密算法。

此时算法要能够满足公开密钥加密的要求，则必须满足以下条件：（1）有可能找到e、d、n 的值，使得对所有M<n 有Med=M mod n。

（2）对于所有M<n 的值，要计算Me和Cd 相对来说是简单的。

（3）在给定e 和n 时，判断出 d 是不可行的。

2、重点考虑第一个条件：由Euler 定理的一个推论：给定两个素数p和q以及两个整数n 和m，使得n=pq 而且0<m<n，并且对于任意整数k，下列关系成立：mkΦ(n)+1=mk(p-1)(q-1)+1≡m mod n其中Φ(n)是欧拉函数，也就是不超过n 且与n 互素的整数个数。

对于素数p 和q，有Φ(pq)=(p-1)(q-1)。

因此得到需要的关系：ed=kΦ(n)+1，等价于: ed≡1 mod Φ(n)d≡e-1 mod Φ(n)也就是说：d 和 e 是以Φ(n)为模的乘法逆元。

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

南邮数据结构实验一实验报告（2014 / 2015学年第一学期）课程名称数据结构实验名称二叉树基本操作以及哈夫曼编码译码系统实验时间年月日指导单位指导教师学生姓名班级学号学院(系) 专业二叉树的基本运算：一、问题描述1.设计递归算法，实现二叉树的运算：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树，交换一棵二叉树的左右子树2.设计算法，自上而下，自左向右即按层次遍历一棵二叉树3.设计main函数，测试上述每个运算二、系统分析和概要设计首先用maketree构造一棵二叉树，然后遍历二叉树，然后交换每个结点的左右子树，接着算出输得高度和叶子节点，最后删除。

三、详细设计2. 核心算法建立二叉树的void MakeTree(const T& x,BinaryTree& left,BinaryTree& right)和计算叶子节点的int Size();3. 算法分析删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树等都是用递归的方法实现。

四、程序代码流程图#includetemplatestruct BTNode{BTNode(){lChild=rChild=NULL;}BTNode(const T &x){element=x;lChild=rChild=NULL;}BTNode(const T &x,BTNode* l,BTNode* r) {element=x;lChild=l;rChild=r;}T element;BTNode* lChild,* rChild;};templateclass BinaryTree{public:BinaryTree(){root=NULL;}~BinaryTree(){Clear();}void Copy(BinaryTree&r) const;bool IsEmpty()const{return root == NULL;}void Clear();void Exchange();bool Root(T& x)const;int GetHeight();void MakeTree(const T& x,BinaryTree& left,BinaryTree& right);void BreakTree(T& x,BinaryTree& left,BinaryTree& right);void PreOrder(void (*Visit)(T &x));void LevelOrder(void (*Visit)(T& x));int Size();BinaryTree(BinaryTree&t)root=Copy(t.root);}// void InOrder(void (*Visit)(T &x));// void PostOrder(void (*Visit)(T &x));BTNode* Copy(BTNode* t);protected:BTNode * root;private:static int number;void Clear(BTNode* &t);void Exchange(BTNode* t);int GetHeight(BTNode* t);int Size(BTNode* t);void PreOrder(void (*Visit)(T &x),BTNode* t);void LevelOrder(void (*Visit)(T& x),BTNode* t); // void InOrder(void (*Visit)(T &x),BTNode* t);// void PostOrder(void (*Visit)(T &x),BTNode* t); };templatebool BinaryTree::Root(T &x)const{if(root){x=root->element;return true;}elsereturn false;}templatevoid BinaryTree::Clear(){Clear(root);}templatevoid BinaryTree::Clear(BTNode* &t){if(t)Clear(t->lChild);Clear(t->rChild);delete t;t=NULL;}}templatevoid BinaryTree::MakeTree(const T& x,BinaryTree& left,BinaryTree& right) {if(root||&left==&right)return;root=new BTNode (x,left.root,right.root);left.root=right.root=NULL;}templatevoid BinaryTree::BreakTree(T& x,BinaryTree& left,BinaryTree& right) {if(!root||&left==&right||left.root||right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;delete root;root=NULL;}templateBTNode* BinaryTree::Copy(BTNode* t){if(!t)return NULL;BTNode*q=new BTNode(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);return q;}templatevoid Visit(T &x){cout<<x<<" ";<="" bdsfid="252" p=""></x<<">}templatevoid BinaryTree::PreOrder(void (*Visit)(T& x)){PreOrder(Visit,root);}templatevoid BinaryTree::PreOrder(void (*Visit)(T& x),BTNode* t) { if(t){Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}templatevoid BinaryTree::Exchange(){Exchange(root);}templatevoid BinaryTree::Exchange(BTNode* t){if(!t)return;BTNode* temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);}templateint BinaryTree::GetHeight(){return GetHeight(root);}int BinaryTree::GetHeight(BTNode* t) {int templ;int tempr;if(!t)return 0;templ=GetHeight(t->lChild);tempr=GetHeight(t->rChild);if(templ++>tempr++)return templ;elsereturn tempr;}templateint BinaryTree::number=0; templateint BinaryTree::Size(){Size(root);return number;}templateint BinaryTree::Size(BTNode* t){if(t!=NULL){Size(t->lChild);if(t->lChild ==NULL&&t->rChild ==NULL)number++;Size(t->rChild);}return number;}templatevoid BinaryTree::LevelOrder(void (*Visit)(T& x)) { PreOrder(Visit,root);}void BinaryTree::LevelOrder(void (*Visit)(T& x),BTNode* t) { BTNode *quene[50],*p;int pre=1,rear=1;quene[++pre]=t;while(pre!=0){p=quene[++rear];cout<element<<" ";if(p->lChild !=NULL)quene[++pre]=p->rChild ;if(p->rChild !=NULL)quene[++pre]=p->lChild ;}}void main(){BinaryTree a,b,x,y,z;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('D',a,b);z.MakeTree('B',y,x);cout<<"二叉树z的先序遍历:"<<endl;< bdsfid="378" p=""></endl;<>z.PreOrder(Visit);cout<<endl;< bdsfid="381" p=""></endl;<>cout<<"层次遍历二叉树:";z.LevelOrder(Visit);cout<<endl;< bdsfid="385" p=""></endl;<>BinaryTree q(z);cout<<"复制的二叉树q的先序遍历:"<<endl;< bdsfid="389" p=""></endl;<>q.PreOrder(Visit);cout<<endl;< bdsfid="392" p=""></endl;<>cout<<"树的高度:";cout<<z.getheight()<<endl;< bdsfid="395" p=""></z.getheight()<<endl;<>cout<<"叶子节点数量:";cout<<z.size()<<endl;< bdsfid="398" p=""></z.size()<<endl;<>z.Exchange();cout<<"二叉树左右子树交换后的先序遍历:"<<endl;< bdsfid="401" p=""></endl;<>z.PreOrder(Visit);cout<<endl;< bdsfid="404" p=""></endl;<>}五、测试用例和运行结果测试用例如main函数中所示，结果如下图所示。

南邮数学实验报告
实验目的：
本实验旨在帮助学生基于对不同数学概念的理解和应用，掌握
数学实验中的基本技能和科学方法，以及加强团队协作和实验报
告撰写能力。

实验内容：
1.选择适当的数列，并利用不同的方法来研究和描述该数列的
性质和规律。

2.利用数学软件工具如Mathematica和Excel等来验证和分析数
列的特征，并通过可视化图形进行展示。

3.完成实验报告和展示，并与同学和教师之间进行交流和互动。

实验步骤：
1.选择一个数列，并介绍其基本特征和规律。

2.利用手工计算和计算机软件工具进行数列的推导和验证。

3.绘制数列的图形表示，并通过图形分析来说明数列性质。

4.进行更深入的探索，如在数列之间搜索、联系和推理，并加
强对数学概念和方法的理解。

5.结合实验数据，形成文献综述和分析，并撰写实验报告。

实验结果：
通过实验学习和探索，我们深入了解了数列的性质和规律。

我
们还掌握了一些基本的数学实验技能，如数据分析、可视化图形、以及实验报告撰写等。

最重要的，我们加强了团队协作和沟通，
更好地理解和应用数学知识。

结论：
数学实验是帮助学生理解和应用数学知识的重要途径。

它不仅可以促进学生的动手能力和创新思维，还可以帮助学生加强团队协作和实验报告撰写能力。

对于未来从事科研工作的学生来说，数学实验将是非常有益的经验和见识。

数值计算实践I 、方程求根一、实验目的熟悉和掌握Newton 法,割线法,抛物线法的方法思路，并能够在matlab 上编程实现二、问题描述(1).给定一个三次方程,分别用Newton 法,割线法,抛物线法求解. 方程的构造方法:(a)根:方程的根为学号的后三位乘以倒数第二位加1再除以1000. 假设你的学号为B06060141,则根为141*(4+1)/1000=0.564(b)方程:以你的学号的后三位数分别作为方程的三次项,二次项,一次项的系数,根据所给的根以及三个系数确定常数项. 例如:你的学号是B06060141,则你的方程是x 3+4x 2+x+a 0=0的形式. 方程的根为0.564,因此有0.5643+4*0.5642+0.564+a0=0,于是a0=-2.015790144 你的方程为x 3+4x 2+x-2.015790144=0.(2)假设方程是sinx+4x 2+x+a0=0的形式（三个系数分别是学号中的数字），重新解决类似的问题(3)构造一个五次方程完成上面的工作.四次方程的构造:将三次多项式再乘以(x-p*)2得到对应的五次多项式(p*为已经确定的方程的根,显然,得到的五次方程有重根).(4)将（2）中的方程同样乘以(x-p*)得到一个新的方程来求解注:(1)Newton 法取0.5为初值,割线法以 0,1为初值,抛物线法以0,0.5,1为初值, (2)计算精度尽量地取高.终止准则：根据ε<--||1n n p p 来终止(3)可供研究的问题：（一）ε的取值不同对收敛速度有多大的影响（二）将注（1）中的初值该为其它的初值，对收敛性以及收敛速度有无影响 （三）能否求出方程的所有的根 （4）实验报告的撰写实验报告包含的内容：（一）实验目的（二）问题描述（三）算法介绍（包括基本原理）（四）程序（五）计算结果（六）结果分析（七）心得体会三、算法介绍在本问题中，我们用到了newton 法，割线法，抛物线法。

南京邮电大学实验报告实验名称：采样、系统性质及滤波系统频率响应和样本处理算法实现加窗和离散傅氏变换数字滤波器设计课程名称：数字信号处理姓名：学号开课时间2011 /2012 学年，第 2 学期实验一一．实验名称：采样、系统性质及滤波 二．实验目的和任务，实验内容：一、观察采样引起的混叠。

设模拟信号为)3sin()2sin(4)5cos()(t t t t x πππ⋅+=，t 的单位为毫秒(ms)。

1. 设采样频率为3kHz ，确定与)(t x 混叠的采样重建信号)(t x a 。

2. 画出)(t x 和)(t x a 在)(60ms t ≤≤范围内的连续波形。

（因数字计算机无法真正画出连续波形，可用较密的离散点的连线来近似。

）3. 分别用"" 和""⨯在两信号波形上标记出3kHz 采样点。

两信号波形是否相同？采样后的两序列是否相同？二、判别离散时间系统的时不变性。

（来源：p105 例3.2.2）设输入序列为)(n x ，系统)2()(n x n y =实现对)(n x 的抽取。

1. 设500,...,2,1),1002sin()(==n n n x π。

取延迟量D （例如D ＝30）。

记)()(D n x n x D -=，画出)(n x 、)(n x D 的序列波形。

2. 编程求出系统对)(n x 的响应)(n y 以及对)(n x D 的响应)(n y D3. 画出)(D n y -、)(n y D 的波形。

该系统是否为时不变的？三、利用卷积计算信号通过FIR 滤波器的输出，并观察输出信号的input-on 暂态、input-off暂态和稳态阶段。

（来源：p144 例4.1.8）考虑两个滤波器，⎩⎨⎧≤≤⋅=其它0140)75.0(25.0)(1n n h n ，]1,5,10,105,1[51--=，－2h ；输入)(n x 为周期方波，第一个周期内⎩⎨⎧≤≤≤≤=492502401)(x x n x 。

第1篇一、实验目的1. 理解快速排序算法的基本原理和实现方法。

2. 掌握快速排序算法的时间复杂度和空间复杂度分析。

3. 通过实验验证快速排序算法的效率。

4. 提高编程能力和算法设计能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理快速排序算法是一种分而治之的排序算法，其基本思想是：选取一个基准元素，将待排序序列分为两个子序列，其中一个子序列的所有元素均小于基准元素，另一个子序列的所有元素均大于基准元素，然后递归地对这两个子序列进行快速排序。

快速排序算法的时间复杂度主要取决于基准元素的选取和划分过程。

在平均情况下，快速排序的时间复杂度为O(nlogn)，但在最坏情况下，时间复杂度会退化到O(n^2)。

四、实验内容1. 快速排序算法的代码实现2. 快速排序算法的时间复杂度分析3. 快速排序算法的效率验证五、实验步骤1. 设计快速排序算法的C++代码实现，包括以下功能：- 选取基准元素- 划分序列- 递归排序2. 编写主函数，用于生成随机数组和测试快速排序算法。

3. 分析快速排序算法的时间复杂度。

4. 对不同规模的数据集进行测试，验证快速排序算法的效率。

六、实验结果与分析1. 快速排序算法的代码实现```cppinclude <iostream>include <vector>include <cstdlib>include <ctime>using namespace std;// 生成随机数组void generateRandomArray(vector<int>& arr, int n) {srand((unsigned)time(0));for (int i = 0; i < n; ++i) {arr.push_back(rand() % 1000);}}// 快速排序void quickSort(vector<int>& arr, int left, int right) { if (left >= right) {return;}int i = left;int j = right;int pivot = arr[(left + right) / 2]; // 选取中间元素作为基准 while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr[i], arr[j]);i++;j--;}}quickSort(arr, left, j);quickSort(arr, i, right);}int main() {int n = 10000; // 测试数据规模vector<int> arr;generateRandomArray(arr, n);clock_t start = clock();quickSort(arr, 0, n - 1);clock_t end = clock();cout << "排序用时：" << double(end - start) / CLOCKS_PER_SEC << "秒" << endl;return 0;}```2. 快速排序算法的时间复杂度分析根据实验结果，快速排序算法在平均情况下的时间复杂度为O(nlogn)，在最坏情况下的时间复杂度为O(n^2)。