算法设计与分析实验报告格式 - 实验报告 - 书业网.docVIP

算法设计与分析实验报告格式 - 实验报告 - 书业网 算法设计与分析实验报告一 实验名称 统计数字问题 评分 实验日期 年月 日指导教师 刘长松 姓名 刘飞初 专业班级计算机0901 学号 10 一.实验要求 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次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #includelt;iostream.hgt; 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;ilt;=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(nlt;10) { for(int i=0;ilt;=n;i++) { s[i]+=1; } return; }//o; //求出最高位以后的数 int zuigao=n/zero; //求出最高位zuigao for(i=0;ilt;zuigao;i++) { s[i]+=zero; } //求出0~zuigao-1位的数的出现次数 for(i=0;ilt;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)gt;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; coutlt;lt;quot;输入数字要查询的数字:quot;; cingt;gt;N; coutlt;lt;#39;\n#39;; n = N; for(i=0;ngt;=10;i++) { n/=10; } //求出N的位数n-1 l=i; sum(N,l,1); for(i=0; ilt;10;i++) { coutlt;lt; quot;数字quot;lt;lt;ilt;lt;quot;出现了:quot;lt;lt;s[i]lt;lt;quot;次quot;lt;lt;#39;\n#39;; } } 五.程序调试中的问题 调试过程中总是有这样那样的问题，通过一步步的修改，最终得以实现。 六.实验结果 算法设计与分析实验报告二 实验名称分治法实现归并排序算法评分 实验日期 年月 日指导教师 刘长松姓名 刘飞初 专业班级 计算机0901 学号10 一.实验