随机全排列实验报告.docx

实验一 随机全排列 生成程序及其应用开发课程：姓名：学号：班级：实验内容编制生成 0~n（n≤255）的一个全排列的程序，可选择方法 ：从一个随机文件读取 n+1 字节数据 d0, d1……dn。由预先取定的一个 0~n 的全排列 P（比如，可为 0~n 的自然排列）开始，依次对 i=n, n-1,1，计算：j=(di-1+di )mod i,交换 P 的第 i 项和第 j 项（在此注意我们假定 P 从第 0 项开始）。要求：程序须对不超过 255 的正整数 n 都容易生成 0~n 的一个全排列；对较小的 n，抓图显示随机全排列生成程序的计算结果（附页），数据不能出现明显错误；每位同学设计的“一种对于随机全排列生成程序的应用”须有个性化特点、不与别人雷同。 实验分析这个方法主要就是对于文件的使用，得到一组随机序列，然后就用简单的算法让自然序列P打乱成为一组新的随机全排列P。其实这可以作为密钥算法将我们的铭文变换成密文，防止重要信息被他人截获知悉（但是内容不能有重复之处），或是应用于日常生活，比如彩票开奖，排考试座位号。。。1、随机全排列：“一个 0~n 随机全排列”中的随机性是指：某种相应的生成方法可以做到“让0~n 中任意数等可能地出现在任一位置”。全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。2、要打开并读取文件的内容，就要使用fopen，fscanf，fclose等函数 1）声明文件指针FILE *fp； 2）格式fopen(const char * path,const char * mode); 参数path/view/263416.htm字符串包含欲打开的文件路径及文件名，参数mode字符串则代表着流形态。r 以只读方式打开文件，该文件必须存在。而且文件是txt格式时，加t，当mode后什么都不加时默认为是t。注意此时文件名后要加.txt。如果文件顺利打开后，指向该流的文件指针就会被返回。如果文件打开失败则返回NULL例如：fp=fopen(name,r)；3）fscanf(要读文件指针,类型参数%d,d[i]) 从一个流中执行格式化输入,fscanf遇到空格和换行时结束，注意空格时也结束。返回值为整型，成功返回读入的参数的个数，失败返回EOF（可以判断是否读取成功）。4）fclose（文件指针）关闭文件，后面记得fp=NULL（指向空，否则会指向原打开文件地址）。 3、将自然序列P打乱成随机全排列P 先定义自然序列p[256]， for(i=n;i0;i--) //进行交换i，j位置的操作{ j=(d[i]+d[i-1])%i;//比较随机的找到j temp=p[i]; p[i]=p[j]; p[j]=temp;}最后输出随机全排列P.实验代码及其测试#includestdio.h#includeiostream using namespace std;int main(){FILE *fp=NULL;char name[10];//随机文件名 int i,j,n;int temp;int d[256];//随机文件中序列 int p[256];//全排列序列 printf(请输入数字n(0=n=255)\n);scanf(%d,n);printf(请输入随机文件名(文件名后加.txt)：\n);//输入所要打开随机文件的名称路径scanf(%s,name);fp=fopen(name,r);/*文件顺利打开后，指向该流的文件指针就会被返回。如果文件打开失败则返回NULL r 以只读方式打开文件，该文件必须存在。 */ if(fp==NULL) //判断文件是否打开成功{printf(无法找到文件);return 0;}printf(文件打开成功\n);for(i=0;i=n;i++){if(fscanf(fp,%d,d[i])==EOF) /*从一个流中执行格式化输入,fscanf遇到空格和换行时结束，注意空格时也结束。 返回值为整型，成功返回读入的参数的个数，失败返回EOF(-1)。*/ {printf(文件读取错误); return 0;}fscanf(fp,%d,d[i]);} for(i=0;i=n;i++) //生成自然P全排列{p[i]=i;}for(i=n;i0;i--) //进行交换位置的操作{ j=(d[i]+d[i-1])%i; temp=p[i]; p[i]=p[j]; p[j]=temp; }fclose(fp);fp=NULL; //需要指向空，否则会指向原打开文件地址printf(0~n的一个随机全排列为：\n);for(i=0;i=n;i++){coutp[