Apriori算法实验报告
题目Apriori算法实现学生姓名
学生学号
专业班级
指导教师
2014-12-27
实验一Apriori算法实现
一、实验目的
1.加强对Apriori算法的理解；
2.锻炼分析问题、解决问题并动手实践的能力。
二、实验要求
使用一种你熟悉的程序设计语言，如C++或Java，实现Apriori算法，至少在两种不同的数据集上比较算法的性能。
三、实验环境
Win7 旗舰版+ Visual Studio 2010
语言：C++
四、算法描述
1、Apriori算法说明
在Apriori算法中，寻找频繁项集的基本思想是：
A.简单统计所有含一个元素项目集出现的频率，找出不小于最小支持度的
项目集, 即频繁项集；
B.从第二步开始，循环处理直到再没有最大项目集生成。循环过程是: 第
k步中, 根据第k-1步生成的频繁(k-1)项集产生侯选k项集。根据候选k
项集，算出候选k项集支持度，并与最小支持度比较, 找到频繁k项集。
下文中遇到的以下符号,分别代表相应的内容
k-itemset k项集
Lk频繁k项集
Ck侯选k项集
2、Apriori算法描述
数据结构说明
double minsup; //设置最小支持度
map
vector
vector
vector
ofstream outFile;
int round=1; //生成项集轮次
long trancount=0; //原始事务总数
//判断某个项目在某一个事务中是否存在，存在则值为1，反之为0
vector
Apriori算法的第一步是简单统计所有含一个元素的项集出现的频率，来决定频繁1项集。在第k步,分两个阶段：1，用函数genCanItemsetK，通过第(k-1)步中生成的频繁(k-1)项集来生成侯选k项集；2.计算侯选k项集的支持度，并找出频繁k项集。
Apriori算法描述如下
getOriData(); //获取原始数据集，并统计事务个数
genCanItemset1(); //产生输出候选1项集
genFreItemset1(); //产生频繁项集
if(!frequentvec.empty()) //根据频繁1项集，执行程序
{
do
{
genCanItemsetK(); //生成并输出候选k项集
genFreItemsetK(); //计算并输出频繁k项集
}while(!frequentvec.empty()); //频繁项集不为空,则循环继续}
其中，产生候选k项集函数genCanItemsetK中涉及两个重要函数，项集合并函数mergeItem和剪枝函数cutNotCanItemsetK。
3、函数方法说明
//获取原始数据集，并统计事务个数
void getOriData();
//合并生成新的候选项集
vector
//判断项集item是否已经存在候选项集集合items中,存在则返回1
int isExist(vector
//产生并输出候选1项集
void genCanItemset1();
//产生并输出频繁1项集
void genFreItemset1();
//产生并输出候选k-项集（k>=2）
void genCanItemsetK();
//产生并输出频繁k-项集（k>=2）
void genFreItemsetK();
//剪枝：剪去合并后项集中含有非频繁项集中的项
void cutNotCanItemsetK(vector
五、实验截图
1.程序运行界面
2.输出文件截图1
3.输出文件截图1
六、实验总结
做完这个实验，有如下收获：
1.同一数据集，最小支持度越小，那么产生的频繁项集维数越高，程序运
行时间越长；
2.更加深刻理解了：频繁子集的任何子集一定是频繁的，子集频繁父亲一
定频繁；
3.Apriori也存在缺点：第一在每一步产生侯选项目集时循环产生的组合过
多，没有排除不应该参与组合的元素；第二,每次计算项集的支持度时，
开销会随着数据的增多而成几何级增长。
七、附
1.程序源码main.cpp
#include
#include
#include
#include
#include
#include
#include
using namespace std;
double minsup; //设置最小支持度
map
vector
vector
vector
ofstream outFile;
int round=1; //生成项集轮次
long trancount=0; //原始事务总数
//判断某个项目在某一个事务中是否存在，存在则值为1，反之为0
vector
//获取原始数据集，并统计事务个数
void getOriData();
//合并生成新的候选项集
vector
//判断项集item是否已经存在候选项集集合items中,存在则返回1
int isExist(vector
//产生并输出候选1项集
void genCanItemset1();
//产生并输出频繁1项集
void genFreItemset1();
//产生并输出候选k-项集（k>=2）
void genCanItemsetK();
//产生并输出频繁k-项集（k>=2）
void genFreItemsetK();
//剪枝：剪去合并后项集中含有非频繁项集中的项
void cutNotCanItemsetK(vector
int main()
{
getOriData(); //获取原始数据集，并统计事务个数
cout << "请输入结果文件名："; //pause
string fName;
cin >> fName;
cout << "请输入最小支持度：";
cin >> minsup;
outFile.open(fName,ios::trunc);
outFile << "最小支持度为minsup = " << minsup << endl;
genCanItemset1();
genFreItemset1();
if(!frequentvec.empty()) //判断频繁1项集是否为空，为空则退出
{
do
{
genCanItemsetK();
genFreItemsetK();
}while(!frequentvec.empty()); //频繁项集不为空,则循环继续}
outFile.close();
cout << "\n结果已保存到" << fName << "文件！\n";
system("pause");
return 0;
}
//获取原始数据集，并统计事务个数
void getOriData()
{
int flag;
cout << "数据集文件：\n1.dataA.txt\n2.dataB.txt\n请输入（1选择dataA，其他选择2）\n";
cin >> flag;
string filename;
if(flag == 1)
filename = "dataA.txt"; //打开数据文件
else
filename = "dataB.txt";
ifstream file(filename);
if(!file) //检查文件是否打开成功
{
cout<<"Fail to open data file!"< system("pause"); exit(0); } else { string temp; vector cout<<"原始数据集："< int begin,end; while(getline(file,temp)) //一行一行读入数据 { trancount++; begin=0; temp.erase(0,temp.find_first_not_of("\r\t\n ")); //去除字符串首部的空格 temp.erase(temp.find_last_not_of("\r\t\n")+1); //去除字符串尾部的空格 while((end=temp.find(' ',begin))!=string::npos) //每一个事务中的项是以空格为分隔符的 { item.push_back(temp.substr(begin,end-begin)); //将每一个项插入item中 begin=end+1; } item.push_back(temp.substr(begin)); //一个事务中的最后一项 datavec.push_back(item); //将一个事务中的所有项当成一个整体插入另一个大的vector中 item.clear(); //清空item cout < } } file.close(); } //产生并输出候选1项集 void genCanItemset1() { map for(int ix=0;ix!=datavec.size();++ix) { for(int iy=0;iy!=datavec[ix].size();++iy) { items_count[datavec[ix].at(iy)]++; //该项集的计数加1 item_map[datavec[ix].at(iy)]=true; //表示该项目在该事务中存在，值为1，否则默认为0 } bitmap.push_back(item_map); item_map.clear(); //这里一定要清空一下 } map outFile << "候选1项集:" << endl; while(map_it!=items_count.end()) //输出候选1项集 { outFile <<"{"< map_it++; } } //产生并输出频繁1项集 void genFreItemset1() { map outFile<<"频繁1项集:"< vector while(map_it!=items_count.end()) //频繁1项集 { if(((float)map_it->second/(float)trancount)>minsup||fabs(((float)map_it->sec ond/(float)trancount)-minsup)<1.0e-7) //支持度大于0.2 { outFile.setf(ios::fixed); outFile <<"{"< item.push_back(map_it->first); frequentvec.push_back(item); //插入频繁1项集的vector中 item.clear(); } map_it++; } } //产生并输出候选k-项集（k>=2） void genCanItemsetK() { //生成下一轮的候选项集 vector int st=frequentvec.size(); candidatevec.clear(); //清除上一轮的候选项集 for(int st1=0;st1 { for(int st2=st1+1;st2 { item=mergeItem(frequentvec[st1],frequentvec[st2],round); //调用函数合并生成下一轮的候选项集 if(!item.empty()&&!isExist(item,candidatevec)) //若经过判断处理后返回的vector不为空且还不存在该项集，则作为候选项集加入候选vector中 { cutNotCanItemsetK(item); } } } round++; outFile<<"候选"< for(int ix=0;ix!=candidatevec.size();++ix) //输出候选项集 { outFile<<"{"; for(int iy=0;iy!=candidatevec[ix].size();++iy) { outFile< } outFile<<"}"< } if(candidatevec.empty()) //候选项集为空 { outFile<<"候选"< } } //产生并输出频繁k-项集(k>=2) void genFreItemsetK() { int flag; //标记某个项集在某条事务中是否出现，出现为1，不出现为0，如：{I1I2} int count; //统计某个想集在整个交易的事务集中出现的次数 string tempstr; //临时string，用于串接各个项成一个字符串：如: I1 I2 I3 串接为"I1I2I3" int mark; //为避免执行多余的字符串串接工作 frequentvec.clear(); //清除上一轮的频繁项集 for(int sx=0;sx!=candidatevec.size();++sx) //构造下一轮的频繁项集{ mark=1; count=0; for(int sy=0;sy!=bitmap.size();++sy) { flag=1; //初始化为1，表出现 for(int sz=0;sz!=candidatevec[sx].size();++sz) { if(bitmap[sy][candidatevec[sx].at(sz)]==false) //存在某一个子项不存在，则没出现项集 { flag=0; } if(mark==1) //只串接一次，如I1I2 否则为10个I1I2的串接 { tempstr+=candidatevec[sx].at(sz); //串接字符串 } } if(flag) //flag仍然为1，表示该项集在该条事务中出现了，计数加1 { count++; } mark++; } if(((float)count/(float)trancount)>minsup||fabs(((float)count/(float)trancount)-minsup)<1.0e-7) //支持度大于0.2 { frequentvec.push_back(candidatevec[sx]); //插入频繁项集} items_count[tempstr]=count; //对应该项集的计数值 /////////假设此时生成的tempstr为I1I2I3,为便于后面的求置信度的计算，这里需要产生I2I1I3,I1I3I2等组合，并 //在items_count中给它们赋予和I1I2I3相同的值 sort(candidatevec[sx].begin(),candidatevec[sx].end()); //排序 string tempstr2; while(next_permutation(candidatevec[sx].begin(),candidatevec[sx].end())) //取下一排列组合 { for(int tempst=0;tempst!=candidatevec[sx].size();tempst++) //拼接出该字符串组合 { tempstr2+=candidatevec[sx][tempst]; } items_count[tempstr2]=count; //对应该项集的计数值 tempstr2.erase(); } tempstr.erase(); } if(!frequentvec.empty()) //频繁项集不为空 { outFile<<"频繁"< for(int sx=0;sx!=frequentvec.size();++sx) //输出频繁项集 { outFile.setf(ios::fixed); outFile<<"{"; for(int sz=0;sz!=frequentvec[sx].size();++sz) { outFile< tempstr+=frequentvec[sx].at(sz); //串接字符串 } outFile<<"}"; outFile<<" 支持度:"< tempstr.erase(); } } else { outFile<<"没有"< } } //两个项集合并(要求只有一项不同)成一个新的项集（做为候选集）vector int count=0; //统计两个vector中相同的项的数目 vector map for(unsigned int st=0;st { tempMap[vect1[st]]++; vect.push_back(vect1[st]); } for(unsigned int st=0;st { tempMap[vect2[st]]++; if(tempMap[vect2[st]]==2) //表示这两项相同 { count++; } else { vect.push_back(vect2[st]); } } if((count+1)!=round) //要求两个项目集只有一个项目不相同，其他都相同,如:I1 I2 I4 和I1 I2 I3 { vect.clear(); } return vect; } //剪枝：剪去合并后项集中含有非频繁项集中的项 void cutNotCanItemsetK(vector { ////////实现剪枝////////////////////////// string tempstr; vector bool found = false; //是否包含有非频繁的子集,为1表示含有，有的话进行剪枝，如假设I1I4为非频繁项集，则I1I2I4要剪枝掉 string teststr; int testint; tempvec=item; sort(tempvec.begin(),tempvec.end()); while(next_permutation(tempvec.begin(),tempvec.end())) //遍历所有的组合I1I2I4,要变成I1I4I2或其他如I2I1I4才能判断它包含I1I4这个非频繁项集 { for(int tempst=0;tempst!=tempvec.size();tempst++) //拼接出该字符串组合 { tempstr+=tempvec[tempst]; } for(map tempit=items_count.begin();tempit!=items_count.end();tempit++) { if(((float)(tempit->second)/(float)trancount) { if(tempstr.find(tempit->first)!=string::npos) //表示包含有非频繁子项集 { found=true; teststr=tempit->first; testint=tempit->second; break; } } } tempstr.erase(); if(found) //包含非频繁子项集 { break; } } if(!found) //只有不包含有非频繁子项集才加入候选项集中，否则剪枝掉 candidatevec.push_back(item); else { outFile<<"剪去项集:"; for(int st2=0;st2!=item.size();st2++) outFile< outFile<<" 含有非频繁子项集:"< printf("\n"); for(i=0;i 操作系统实验报告 课题：页面淘汰算法 专业： 班级： 学号： 姓名： 年月日 目录 一实验目的……………………………………………………错误！未定义书签。 二实验要求 (3) 三背景知识 (3) 四总体设计 (4) 五详细设计……………………………………………………错误！未定义书签。 六运行结果分析 (9) 七心得体会 (13) 八参考文献 (14) 附：源代码 (15) 一、实验目的 本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。利用简单的数据结构，模拟实现操作系统中的页面置换机制，通过写程序模拟实现上述三种内存页面置换算法，使学生进一步掌握内存页面置换的方法。对操作系统中内存的管理有一个实践上的认识。 1、用C语言编写OPT、FIFO、LRU三种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 二、实验要求 ●设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的 影响 ●编写页面淘汰算法(FIFO、OPT、LRU) ●结果数据的显示或提取 ●结果数据的分析 几点说明： ●设计并绘制算法流程，附加说明所需的数据结构 ●如何标记时间的先后、最久的将来、最久未被使用 ●描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实 现。 1）初始化：输入作业可占用的总页框数，初始化置空。 2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用； 3）Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock 算法，淘汰1个页面后装入新的页号。 4）显示当前分配淘汰序列：显示淘汰的页号序列。 三、背景知识： 兰州交通大学 《算法设计与分析》 实验报告3 题目03-动态规划 专业计算机科学与技术 班级计算机科学与技术2016-02班学号201610333 姓名石博洋 第3章动态规划 1. 实验题目与环境 1.1实验题目及要求 (1) 用代码实现矩阵连乘问题。 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。 确定一个计算顺序，使得需要的乘的次数最少。 (2) 用代码实现最长公共子序列问题。 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj 。例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 (3) 0-1背包问题。 现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W i，价值为正整数V i，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分） 使用动态规划使得装入背包的物品价值之和最大。 1.2实验环境： CPU：Intel(R) Core(TM) i3-2120 3.3GHZ 内存：12GB 操作系统：Windows 7.1 X64 编译环境：Mircosoft Visual C++ 6 2. 问题分析 (1) 分析。 《计算机操作系统》实验报告 实验五：页面调度算法模拟 学校：╳╳╳ 院系：╳╳╳ 班级：╳╳╳ 姓名：╳╳╳ 学号：╳╳╳ 指导教师：╳╳╳ 目录 一、实验题目 (3) 二、实验学时 (4) 三、指导老师 (4) 四、实验日期 (4) 五、实验目的 (4) 六、实验原理 (4) 6.1页面的含义 (4) 6.2 页面置换算法的含义 (4) 6.3 置换算法 (4) 6.3.1最佳置换算法(Optimal) (5) 6.3.2先进先出(FIFO)页面置换算法 (5) 6.3.3 LRU置换算法 (5) 七、实验步骤及结果 (5) 7.1 验证最佳置换算法 (5) 7.1.1 实验截图 (5) 7.1.2 实验分析 (6) 7.2 验证先进先出(FIFO)页面置换算法 (7) 7.2.1 实验截图 (7) 7.2.2 实验分析 (7) 7.3 验证LRU置换算法 (8) 7.3.1 实验截图 (8) 7.3.2 实验分析 (8) 八、报告书写人 (9) 附录一最佳置换算法(Optimal) (9) 附录二先进先出(FIFO)页面置换算法 (15) 附录三LRU置换算法 (20) 实验五：页面调度算法模拟 一、实验题目 页面调度算法模拟 二、实验学时 2学时 三、指导老师 ╳╳╳ 四、实验日期 2018年12月10日星期一 五、实验目的 (1)熟悉操作系统页面调度算法 (2)编写程序模拟先进先出、LRU等页面调度算法，体会页面调度算法原理 六、实验原理 6.1页面的含义 分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。 6.2 页面置换算法的含义 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 6.3 置换算法 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。 材料专业实验报告 题目：扫描电镜(SEM)物相分析实验学院：先进材料与纳米科技学院专业：材料物理与化学 姓名： 学号：1514122986 2016年6月30日 扫描电镜(SEM)物相分析实验 一．实验目的 1.了解扫描电镜的基本结构与原理 2.掌握扫描电镜样品的准备与制备方法 3.掌握扫描电镜的基本操作并上机操作拍摄二次电子像 4.了解扫描电镜图片的分析与描述方法 二．实验原理 1.扫描电镜的工作原理 扫描电镜（SEM）是用聚焦电子束在试样表面逐点扫描成像。试样为块状或粉末颗粒，成像信号可以是二次电子、背散射电子或吸收电子。其中二次电子是最主要的成像信号。由电子枪发射的电子，以其交叉斑作为电子源，经二级聚光镜及物镜的缩小形成具有一定能量、一定束流强度和束斑直径的微细电子束，在扫描线圈驱动下，于试样表面按一定时间、空间顺序作栅网式扫描。聚焦电子束与试样相互作用，产生二次电子发射以及背散射电子等物理信号，二次电子发射量随试样表面形貌而变化。二次电子信号被探测器收集转换成电讯号，经视频放大后输入到显像管栅极，调制与入射电子束同步扫描的显像管亮度，得到反映试样表面形貌的二次电子像。 本次实验中主要通过观察背散射电子像及二次电子像对样品进行分析表征。 1）背散射电子 背散射电子是指被固体样品原子反射回来的一部分入射电子，其中包括弹性背反射电子和非弹性背反射电子。弹性背反射电子是指被样品中原子和反弹回来的，散射角大于90度的那些入射电子，其能量基本上没有变化（能量为数千到数万电子伏）。非弹性背反射电子是入射电子和核外电子撞击后产生非弹性散射，不仅能量变化，而且方向也发生变化。非弹性背反射电子的能量范围很宽，从数十电子伏到数千电子伏。背反射电子的产生范围在100nm-1mm深度。背反射电子产额和二次电子产额与原子序数的关系背反射电子束成像分辨率一般为50-200nm（与电子束斑直径相当）。背反射电子的产额随原子序数的增加而增加，所以，利用背反射电子作为成像信号不仅能分析形貌特征，也可以用来显示原子序数衬 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、简单时钟(钟表)算法（CLOCK） 命中率＝１－页面失效次数／页地址流(序列)长度 三、实验原理 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 四、算法描述 本实验的程序设计基本上按照实验内容进行。即使用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’ D：顺序执行一条指令，其地址为m’+1 预测分析表方法 一、实验目的 理解预测分析表方法的实现原理。 二、实验内容： 编写一通用的预测法分析程序，要求有一定的错误处理能力，出错后能够使程序继续运行下去，直到分析过程结束。可通过不同的文法（通过数据表现）进行测试。 三、实验步骤 1．算法数据构造： 构造终结符数组：char Vt[10][5]={“id”,”+”……}； 构造非终结符数组：char Vn[10]={ }; 构造follow集数组：char *follow[10][10]={ } (可将follow集与预测分析表合并存放) 数据构造示例（使用的预测分析表构造方法1）： /*data1.h简单算术表达式数据*/ char VN[10][5]={"E","E'","T","T'","F"}; //非终结符表 int length_vn=5; //非终结符的个数 char VT[15][5]={"id","+","*","(",")","#"}; //终结符表 int length_vt=6; //终结符的个数 char Fa[15][10]={"TE'","+TE'","","FT'","*FT'","","(E)","id"}; //产生式表:0:E->TE' 1:E'->+TE' 2:E'->空 // 3:T->FT' 4:T'->*FT' 5:T'->空 6:F->(E) 7:F->id int analysis_table[10][11]={0,-1,-1,0,-2,-2,0,0,0,0,0, -1,1,-1,-1,2,2,0,0,0,0,0, 3,-2,-1,3,-2,-2,0,0,0,0,0, -1,5, 4,-1,5, 5,0,0,0,0,0, 7,-2,-2,6,-2,-2,0,0,0,0,0}; //预测分析表,-1表示出错，-2表示该行终结符的follow集合，用于错误处理，正数表示产生式在数组Fa 中的编号，0表示多余的列。 （1）预测分析表的构造方法1 给文法的正规式编号：存放在字符数组中，从0开始编号，正规式的编号即为该正规式在数组中对应的下标。如上述Fa数组表示存储产生式。 构造正规式数组：char P[10][10]={“E->TE’”,”E’->+TE’”,……..}; (正规式可只存储右半部分，如E->TE’可存储为TE’，正规式中的符号可替换，如可将E’改为M ) 构造预测分析表：int analyze_table[10][10]={ } //数组元素值存放正规式的编号，-1表示出错 （2）预测分析表的构造方法2 可使用三维数组 Char analyze_table[10][10][10]={ } 力学与材料学院 材料现代分析方法实验报告二 XRD图谱分析 专业年级：1 姓名：1 指导老师：1 学号：1 2016年12月 中国南京 目录 实验名称：XRD图谱分析…………………………………………… 一、实验目的…………………………………………………… 二、实验要求…………………………………………………… 三、操作过程…………………………………………………… 四、结果分析与讨论……………………………………………… 实验名称：XRD图谱分析 一、实验目的 了解XRD基本原理及其应用，不同物相晶体结构XRD图谱的区别，熟练掌握如何来分析利用X射线测试得到的XRD图谱。 二、实验要求 1、熟练掌握如何来利用软件打开、分析XRD图谱，以及输出分析结果。 2、明确不同物质的XRD图谱，掌握XRD图谱包含的晶体结构的关系，通过自己分析、数据查找和鉴别的全过程，了解如何利用软件正确分析和确定不同物相的XRD图谱，并输出分析结果。 3、实验报告的编写，要求报告能准确的反映实验目的、方法、过程及结论。 三、操作过程 1、启动Jade 6.0，并打开实验数据。 2、点击图标使图谱平滑后，再连续两次点击图标扣除背景影响。 3、右击工具栏中的图标，全选左侧的项目，取消选择右侧中的Use Chemistry Filter，最后在下方选择S/M Focus on Major Phases（如图一），并点击OK。 图一 4、得到物相分析，根据FOM值（越小，匹配性越高）可推断出该物相为以ZnO为主，可能含有CaF2、Al2O3、Mg(OH)2混合组成的物质（如图二），双击第一种物质可以得到主晶相的PDF卡片（如图三），点击图三版面中的Lines可以观察到不同角度处的衍射强度（如图四）。 图二 学生实验报告书 实验课程名称算法设计与分析开课学院计算机科学与技术学院 指导教师姓名李晓红 学生姓名 学生专业班级软件工程zy1302班2015-- 2016学年第一学期 实验课程名称：算法设计与分析 同组者实验日期2015年10月20日第一部分：实验分析与设计 一．实验内容描述（问题域描述） 1、利用分治法，写一个快速排序的递归算法，并利用任何一种语言，在计算机上实现，同时 进行时间复杂性分析； 2、要求用递归的方法实现。 二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） 本次的解法使用的是“三向切分的快速排序”，它是快速排序的一种优化版本。不仅利用了分治法和递归实现，而且对于存在大量重复元素的数组，它的效率比快速排序基本版高得多。 它从左到右遍历数组一次，维护一个指针lt使得a[lo..lt-1]中的元素都小于v，一个指针gt 使得a[gt+1..hi]中的元素都大于v，一个指针i使得a[lt..i-1]中的元素都等于v，a[i..gt]中的元素都还未确定，如下图所示： public class Quick3way { public static void sort(Comparable[] a, int lo, int hi) { if (lo >= hi) return; int lt = lo, i = lo + 1, gt = hi; Comparable pivot = a[lo]; 第二部分：实验调试与结果分析 一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等） 1、调试方法描述： 对程序入口进行断点，随着程序的运行，一步一步的调试，得到运行轨迹； 2、实验数据： "R", "B", "W", "W", "R", "W", "B", "R", "R", "W", "B", "R"； 3、实验现象： 4、实验过程中发现的问题： （1）边界问题： 在设计快速排序的代码时要非常小心，因为其中包含非常关键的边界问题，例如： 什么时候跳出while循环，递归什么时候结束，是对指针的左半部分还是右半部分 排序等等； （2）程序的调试跳转： 在调试过程中要时刻记住程序是对那一部分进行排序，当完成了这部分的排序后， 会跳到哪里又去对另外的那一部分进行排序，这些都是要了然于心的，这样才能准 确的定位程序。 二、实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等） 1、实验结果： 综合性实验报告 一、实验目的 通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。 页面置换算法是虚拟存储管理实现的关键，通过本次实验理解内存页面调度的机制，在模拟实现FIFO、LRU、OPT、LFU、NUR几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。 二、总体设计 1、编写函数计算并输出下述各种算法的命中率 ①OPT页面置换算法 OPT所选择被淘汰的页面是已调入内存，且在以后永不使用的，或是在最长时间内不再被访问的页面。因此如何找出这样的页面是该算法 的关键。可为每个页面设置一个步长变量，其初值为一足够大的数，对 于不在内存的页面，将其值重置为零，对于位于内存的页面，其值重置 为当前访问页面与之后首次出现该页面时两者之间的距离，因此该值越 大表示该页是在最长时间内不再被访问的页面，可以选择其作为换出页 面。 ②FIFO页面置换算法 FIFO总是选择最先进入内存的页面予以淘汰，因此可设置一个先进先出的忙页帧队列，新调入内存的页面挂在该队列的尾部，而当无空闲 页帧时，可从该队列首部取下一个页帧作为空闲页帧，进而调入所需页 面。 ③LRU页面置换算法 LRU是根据页面调入内存后的使用情况进行决策的，它利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以 淘汰。该算法主要借助于页面结构中的访问时间time来实现，time记 录了一个页面上次的访问时间，因此，当须淘汰一个页面时，选择处于 内存的页面中其time值最小的页面，即最近最久未使用的页面予以淘 汰。 ④LFU页面置换算法 LFU要求为每个页面配置一个计数器（即页面结构中的counter），一旦某页被访问，则将其计数器的值加1，在需要选择一页置换时，则 将选择其计数器值最小的页面，即内存中访问次数最少的页面进行淘 汰。 ⑤NUR页面置换算法 NUR要求为每个页面设置一位访问位（该访问位仍可使用页面结构中的counter表示），当某页被访问时，其访问位counter置为1。需要 进行页面置换时，置换算法从替换指针开始（初始时指向第一个页面） 顺序检查处于内存中的各个页面，如果其访问位为0，就选择该页换出， 否则替换指针下移继续向下查找。如果内存中的所有页面扫描完毕未找 到访问位为0的页面，则将替换指针重新指向第一个页面，同时将内存 中所有页面的访问位置0，当开始下一轮扫描时，便一定能找到counter 为0的页面。 2、在主函数中生成要求的指令序列，并将其转换成页地址流；在不同 的内存容量下调用上述函数使其计算并输出相应的命中率。 三、实验步骤（包括主要步骤、代码分析等） 主要步骤： 、通过随机数产生一个指令序列，共320条指令。其地址按下述原则生成： ①50%的指令是顺序执行的； ②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； 具体的实施方法是： A.在[0，319]的指令地址之间随机选区一起点M； B.顺序执行一条指令，即执行地址为M+1的指令； C.在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’； D.顺序执行一条指令，其地址为M’+1； E.在后地址[M’+2，319]中随机选取一条指令并执行； 材料分析与表征方法实验报告 热重分析实验报告 一、实验目的 1.了解热重分析法的基本原理和差热分析仪的基本构造。 2.掌握热重分析仪的使用方法。 二、实验原理 热重分析指温度在程序控制时，测量物质质量与温度之间的关系的技术。热重分析所用的仪器是热天平，它的基本原理是，样品重量变化所引起的天平位移量转化成电磁量，这个微小的电量经过放大器放大后，送入记录仪记录；而电量的大小正比于样品的重量变化量。当被测物质在加热过程中有升华、汽化、分解出气体或失去结晶水时，被测的物质质量就会发生变化。 三、实验原料 一水草酸钙CaC2O4·H2O 四、实验仪器 美国TA公司TGA55 升温与降温速率（K/min）0.1-100℃/min 天平灵敏度（μg）0.1μg 温度范围（°C）室温-1000℃ 五、操作条件 第一组：10℃／min空气条件下和20℃／min空气条件下，对TG和DTG 曲线进行对比。 第二组：10℃／min空气条件下和10℃／min氮气条件下，对DSC进行对比。 第三组：10℃／min氮气条件下，得到TG、DTG、DSC曲线。 六、结果与讨论 含有一个结晶水的草酸钙(242CaC.OHO)在100℃以前没有失重现象,其热重曲线呈水平状,为TG曲线的第一个平台。DTG曲线在0刻度。 在100℃和200℃之间失重并出现第二个平台。DTG曲线先升后降，在108.4℃达到最大值，即失重速率的最大值。DSC曲线先降后升，在188.4℃达到最小值，即热功率的最小值。这一步的失重量占试样总质量的12.47%，相当于每mo CaC2O4·H2O失掉1mol H2O,其热分解反应为： CaC2O4·H2O CaC2O4 + H2O 在400℃和500℃之间失重并开始呈现第三个平台,DTG曲线先升后降，在 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 实验报告 课程名称 学生所在系部 年级 专业、班级 学生姓名 学号 任课教师 实验成绩 软件工程系制 一、实验题目： 先进先出（FIFO）页面置换算法和最近最久未使用（LRU）置换算法程序设计 二、实验目的： 通过对FIFO，LRU算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。 三、实验设备及环境： 1. 硬件设备：PC机一台 2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C \C++\Java 等编程语言环境。 四、实验内容及要求： （1）用C语言编程实现对FIFO，LRU算法的模拟。 （2）每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段： 五、实验方法内容 1.算法流程图 2.主要的常量变量 char a; int m=4,n=12,i,y[12]={1,2,3,4,1,2,5,1,2,3,4,5}; 主要模块 void FIFO(void); void LRU(void); void Xunhuan() void main() 四．代码 #include"stdio.h" #include"stdlib.h" #include"time.h" void FIFO(void); void LRU(void); char a; int m=4,n=12,i,y[12]={1,2,3,4,1,2,5,1,2,3,4,5}; /*m为物理块数，n为要访问的页面数*/ typedef struct page{ int num; int time; }Page; Page x[10]; int GetMax(page *x) { int i; int max=-1; int tag=0; for(i=0;i 六、附录 A #include { if((c[j][r]+cost[r]) 本科生实验报告 实验课程材料研究方法与分析测试实验 学院名称材料与化学化工学院 专业名称材料科学与工程(无机非金属方向) 学生姓名 学生学号 指导教师 实验地点 实验成绩 二〇一四年12月15日——二〇一五年12月19日 填写说明 1、适用于本科生所有的实验报告（印制实验报告册除外）； 2、专业填写为专业全称，有专业方向的用小括号标明； 3、格式要求： ①用A4纸双面打印（封面双面打印）或在A4大小纸上用蓝黑色水 笔书写。 ②打印排版：正文用宋体小四号，1.5倍行距，页边距采取默认形 式（上下2.54cm，左右2.54cm，页眉1.5cm，页脚1.75cm）。字符间距为默认值（缩放100%，间距：标准）；页码用小五号字底端居中。 ③具体要求： 题目（二号黑体居中）； 摘要（“摘要”二字用小二号黑体居中，隔行书写摘要的文字部分，小4号宋体）； 关键词（隔行顶格书写“关键词”三字，提炼3-5个关键词，用分号隔开，小4号黑体)； 正文部分采用三级标题； 第1章××(小二号黑体居中，段前0.5行) 1.1 ×××××小三号黑体×××××（段前、段后0.5行） 1.1.1小四号黑体（段前、段后0.5行） 参考文献（黑体小二号居中，段前0.5行），参考文献用五号宋体，参照《参考文献著录规则（GB/T 7714－2005）》。 实验一扫描电镜实验（SEM） 一、实验目的 1、了解扫描电子显微镜的原理、结构； 2、运用扫描电子显微镜进行样品微观形貌观察。 二、实验原理 扫描电镜（SEM）是用聚焦电子束在试样表面逐点扫描成像。试样为块状或粉末颗粒，成像信号可以是二次电子、背散射电子或吸收电子。其中二次电子是最主要的成像信号。由电子枪发射的电子，以其交叉斑作为电子源，经二级聚光镜及物镜的缩小形成具有一定能量、一定束流强度和束斑直径的微细电子束，在扫描线圈驱动下，于试样表面按一定时间、空间顺序作栅网式扫描。聚焦电子束与试样相互作用，产生二次电子发射以及背散射电子等物理信号，二次电子发射量随试样表面形貌而变化。二次电子信号被探测器收集转换成电讯号，经视频放大后输入到显像管栅极，调制与入射电子束同步扫描的显像管亮度，得到反映试样表面形貌的二次电子像。扫描电镜由下列五部分组成，如图1（a）所示。各部分主要作用简介如下： 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 实验四存储管理 常用页面置换算法模拟实验 一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、最不经常使用算法（LFU） 5、最近未使用算法（NUR） 命中率＝１－页面失效次数／页地址流长度 三、实验过程 1.进入LINUX系统。打开虚拟机，在vi中编写程序，在终端输入文件名（），输入执行指令，屏幕上无反应，按下^C后，显示最终结果。 2、页面置换算法 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 常用的页面置换算法有 1、最佳置换算法（Optimal） 2、先进先出法（FisrtInFirstOut） 3、最近最久未使用（LeastRecentlyUsed） 4、最不经常使用法（LeastFrequentlyUsed） 5、最近未使用法（NoUsedRecently） 3.运行结果: 四、回答问题 1、为什么OPT在执行时会有错误产生？ 当需要淘汰一个内存页面时，这种算法力图选择该进程内存各个页面中永远不再需要的页，若找不到，则选择最久以后才会用到的页。这种算法有最小的缺页率。问题是它需要知道运行进程今后的整个访问踪迹，这往往难以做到，因而它只有理论上的意义。页面淘汰算法实验报告
算法分析_实验报告3
实验五-页面调度算法模拟实验报告
材料分析(SEM)实验报告
算法分析实验报告--分治策略
页面置换算法实验报告
编译原理实验报告材料(预测分析报告表方法)
材料现代分析方法实验报告
武汉理工大学算法分析实验报告
存储管理实验报告
材料分析与表征方法实验报告
算法设计与分析实验报告
FIFO算法实验报告
动态规划算法分析实验报告
材料研究方法与分析测试实验
算法设计与分析实验报告 统计数字问题
实验报告四