内容发布更新时间 : 2024/11/16 2:19:32星期一 下面是文章的全部内容请认真阅读。
算法设计与分析实验报告一
实验名称 统计数字问题 评分 实验日期 2014 年 11 月 15 日 指导教师 姓名 专业班级 学号
一.实验要求
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 s[10]; //记录0~9出现的次数 int a[10]; //a[i]记录n位数的规律 void sum(int n,int l,int m) { if(m==1) {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 for(int i=0;i } //求出输入数为10的n次方 int yushu=n%zero; //求出最高位以后的数 int zuigao=n/zero; //求出最高位zuigao for(i=0;i } //求出0~zuigao-1位的数的出现次数 for(i=0;i<10;i++) { s[i]+=zuigao*a[l]; } //求出与余数位数相同的0~zuigao-1位中0~9出现的次数 //如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数 if(yushu==0) //补上所缺的0数,并且最高位加1 { s[zuigao]++; s[0]+=l; } else { i=0; while((zero/=10)>yushu) { i++; } s[0]+=i*(yushu+1);//补回因作模操作丢失的0 s[zuigao]+=(yushu+1);//补回最高位丢失的数目 sum(yushu,l-i-1,m+1);//处理余位数 }} void main() { int i,m,n,N,l; cout<<\输入数字要查询的数字:\cin>>N; cout<<'\\n'; n = N; for(i=0;n>=10;i++) { n/=10; } //求出N的位数n-1 l=i; sum(N,l,1); for(i=0; i<10;i++) { cout<< \数字\出现了:\次\ }} 五.程序调试中的问题 调试过程，页码出现报错。 六.实验结果 算法设计与分析实验报告二 实验名称 分治法实现归并排序算法 评分 实验日期 2014 年 11 月 26 日 指导教师 姓名 专业班级 学号 一.实验要求 1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时， 如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1 2.掌握分治法的一般控制流程。 DanC(p,q) global n，A[1:n]; integer m,p,q; // 1?p?q?n if Small(p,q) then return G(p,q); else m=Divide(p,q); // p?m return Combine(DanC(p,m),DanC(m+1,q)); endif end DanC 3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。 2.输入10组相同的数据，验证排序结果和完成排序的比较次数。 3.与复杂性函数所计算的比较次数比较。 4.用表格列出比较结果。 5.给出文字分析。 三.程序算法 1. 归并排序算法 procedure MERGESORT(low，high) //A(low；high)是一个全程数组，它含 有high-low+1≥0个待排序的元素// integer low，high； if low then mid← ， //求这个集合的分割点// call MERGESORT(low，mid) //将一个子集合排序// call MERGESORT(mid+1，high) //将另一个子集合排序 call MERGE(low，mid，high) //归并两个已排序的子集合// endif end MERGESORT 归并两个已排序的集合 procedure MERGE(low，mid，high) //A(low：high)是一个全程数组// //辅助数组B(low；high)// integer h，i，j，k； h←low；i←low；j←mid+1； while h≤mid and j≤high do //当两个集合都没取尽时// if A(h)≤A(j) then B(i) ←A(h)；h←h+1 else B(i) ←A(j)；j←j+1 endif i←i+1 repeat if h>mid then for k←j to high do //处理剩余的元素// B(i) ←A(k)；i←i+1 repeat else for k←h to mid do B(i) ←A(k)；i←i+1 repeat endif 将已归并的集合复制到A end MERGE 2. 快速排序算法 QuickSort(p,q) //将数组A[1:n]中的元素 A[p], A[p+1], ? , A[q]按不降次序排列， 并假定A[n+1]是一个确定的、且大于 A[1:n]中所有的数。// int p,q; global n, A[1:n]; if p j=Partition(p, q+1); // 划分后j成为划分元素的位置 QuickSort(p,j-1);