求取大规模顺序文件存储问题的一个可行解

实验名称：求取大规模顺序文件存储问题的一个可行解一、实验内容及要求（一）实验内容假设有n个程序{1,2,…,n}，每个程序对应的文件数K依次为{k1,k2,…,kn}，每个文件的长度L分别是{{1l,2l,…,1kl},{1l,2l,…,2kl},…,{1l,2l,…,knl}}。该n个程序存放在若干个顺序存取设备上，并且同一程序的所有文件必须存储在同一个设备上。1．给定36000n；2．一维数组K={k1,k2,...,kn}随机产生，要求数组K的元素ki的取值范围为120ki，1in；3．二维数组L={{1l,2l,…,1kl},{1l,2l,…,2kl},…,{1l,2l,…,knl}}随机产生，数组L的元素jl的取值范围为1100jl，11inijki；4．L的全部元素之和11inijkijjSl；5．第一个存取设备的容量0.2CS。设计一个存储算法，要求第一个存取设备存储的文件数量最多。（二）实验要求1．设计实验方案，方案中应包括：（1）至少3种问题求解算法，其中必须包括动态规划算法和分支限界法；（2）算法多次执行时间的获取方法；（3）抗时间噪声的方法；（4）时间结果分析对比方法。2．分析各算法的特点，根据本题给出的条件比较各算法的优劣。3．选择一种程序设计语言实现算法，验证各种算法运行结果的正确性。4．运行抗噪声程序执行时间的计数程序，统计各算法的时间开销，并与理论分析的结果进行比较。二、实验思路1.问题分析与实验一问题相似，但是文件数量大规模增加，使用动态规划算法；2.数据生成（1）利用文件存储生成的随机数，避免分配大规模数组；（2）随机数的产生以及其时间为种子；三、程序代码及运行结果（一）程序代码#includestdio.h#includetime.h//时间函数#includestdlib.h#defineN36000//设置N容量intc;//容量inta[N+1];//每个程序文件长度intk[N+1];//每个程序文件数目intcurrentl=0;//当前存入文件长度intcurrentk=0;//当前存入文件数目intbestk=0;//当前存入最多的文件数intbestAnswer[N+1];//以数组形式当前最优解intbp=0;intbA[N+1];//当前最优解inti;voidBacktrack(inti,inta[],intc,intk[]);//其中a为文件长度存储数组，k为文件数目存储数组，c为当前容量voidmain(){time_tstart,end;staticinti;srand((int)time(NULL));printf(\n每个程序的文件数为:\n);for(i=1;i=N;i++)//产生文件数目{k[i]=rand()%20+1;//设定Ki范围printf(k[%d]=%4d,i,k[i]);if(i%19==0)printf(\n);}staticints1=0,a[N+1],l[N+1][20];printf(\n每个程序文件长度为:\n);for(i=1;i=N;i++){for(intj=1;j=k[i];j++){l[i][j]=rand()%100+1;//产生文件长度s1=s1+l[i][j];}a[i]=s1;printf(a[%d]=%4d,i,a[i]);if(i%13==0)printf(\n);s1=0;}//生成容量intc,s2=0;for(i=1;i=N;i++)s2=s2+a[i];c=s2*2/10;printf(\n\n\n容量为:%d,c);start=clock();Backtrack(1,a,c,k);end=clock();printf(\n时间为:%fs,(end-start)/CLOCKS_PER_SEC);//计算时间}voidBacktrack(inti,inta[],intc,intk[])//其中a为文件长度存储数组，k为文件数目存储数组，c为当前容量{if(iN)//未搜索到叶节点{if(bestk=bp){bp=bestk;printf(\n可行解为:\n);for(intj=1;j=N;j++){bA[j]=bestAnswer[j];printf(%d,,bA[j]);if(j%26==0)printf(\n);}printf(}\n);}return;}if(currentl+a[i]=c){//搜索左子树bestAnswer[i]=1;currentl+=a[i];bestk+=k[i];Backtrack(i+1,a,c,k);currentl-=a[i];bestk-=k[i];}bestAnswer[i]=0;Backtrack(i+1,a,c,k);（二）运行结果（部分截图）四、结论分析与实验体会分析：算法多次执行时间的获取方法：让程序重复运行，即设置循环体。计算开始到结束的时间，再除以重复的次数。抗时间噪声的方法；将一些不必要的语句放到时间检测语句之外。此次实验做的是有关大规模顺序文件存储全部可能解的问题，求解最优值其中之一的解应选用的方法是分支限界法，求解最优值全部解则应选择的方法是回溯法。因此在本题中选用的方法是回溯法。实验获取时间的方法是利用系统时间差来得到算法的执行时间。通过这次试验，我对大规模顺序文件存储有了较为深刻的了解，在以后的学习中，我会充分的利用此次学到的知识。