欢迎来到天天文库
浏览记录
ID:22291624
大小:364.93 KB
页数:27页
时间:2018-10-28
《算法设计与分析实验报告格式》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、算法设计与分析实验报告一实验名称统计数字问题评分实验日期年月日指导教师刘长松姓名刘飞初专业班级计算机0901学号10一.实验要求1、掌握算法的计算复杂性概念。2、掌握算法渐近复杂性的数学表述。3、掌握用C++语言描述算法的方法。4、实现具体的编程与上机实验,验证算法的时间复杂性函数。二.实验内容统计数字问题1、闷题描述一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6页用数字6表示,而不是06或006等。数字计数闷题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,
2、2,…,9。2、编程任务给定表示书的总页码的10进制整数n(匕1^109)。编程计算书的企部页码中分别用到多少次数字0,1,2,...,9。三.程序算法将页码数除以10,得到一个整数商和余数,商就代表页码数减余数外有多少个1一9作为个位数,余数代表冇1一余数本身这么多个数作为剩余的个位数,此外,商还代表1一商本身这些数出现了10次,余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。四.程序代码#includeints[10];//记录0〜9出现的次数inta[10];//a[i]记录n位数的规律voidsum
3、(intn,intI,intm)intzero=1;for(inti=O;i<=l;i++)//去除前缀0{s[0]-=zero;zero*=10;>>if(n<10){for(inti=O;i<=n;i十+){s[i]+=l;}return;}//位数为1位时,出现次数加1//位数大于1时的出现次数for(intt=l;t<=l;t++)//计算规律f(n)=n*1OA(n-l){m=l;inti;for(i=l;iintzero=1;for(inti=O;i4、输入数为10的n次方intyushu=n%zero;//求出最战位以后的数intzuigao=n/zero;//求出最时位zuigaofor(i=0;i5、}else{i=0;while((zero/=l0)>yushu){i+十;}s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-l,m+l);//处理余位数voidmain(){inti,m,n,N,l;cout«n输入数字要查询的数字:";cin»N;cout«’’;n=N;for(i=0;n>=l0;i++){n/=10;}//求出N的位数n-1l=i;sum(N,l,l);for(i=0;i<10;i++)cout«"数字"《i«"出现了6、:一.程序调试中的问题调试过程屮总是有这样那样的W题,通过•-步步的修改,最终得以实现。二.实验结果输入数字要查询的数字:5652叙子0出现次數字1出现1:2?36次斂宇2出现Z:2?36次數字3出现]>2?35次教字4出现]>2?35次數字5出现1:23时次教字?出现1:1625次邀字8出现:[:1625达数字9出现了:1625次Pressanykeytocontinue数宇0数字2数字3敎X4载丈5―數字?出数孛8出现了:5久现了=15达现了=15达现了=15达现了:1咏T:6vX现了:s疼现了:S次输入数字要查询的数字:50出LJLJLJp9$l7、y=^Pressanykeytocontinue.算法设计与分析实验报告二实验名称分治法实现归并排序算法评分实验日期年月日指导教师刘长松姓名刘飞初专业班级计算机0901学号10一.实验要求1.了解用分治法求解的问题:当要求解一个输入规模为n,且n的取值相当大的问题时,如采问题可以分成k个不同子集合,得到k个不同的可独立求解的子问题,其中l8、;//l
4、输入数为10的n次方intyushu=n%zero;//求出最战位以后的数intzuigao=n/zero;//求出最时位zuigaofor(i=0;i5、}else{i=0;while((zero/=l0)>yushu){i+十;}s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-l,m+l);//处理余位数voidmain(){inti,m,n,N,l;cout«n输入数字要查询的数字:";cin»N;cout«’’;n=N;for(i=0;n>=l0;i++){n/=10;}//求出N的位数n-1l=i;sum(N,l,l);for(i=0;i<10;i++)cout«"数字"《i«"出现了6、:一.程序调试中的问题调试过程屮总是有这样那样的W题,通过•-步步的修改,最终得以实现。二.实验结果输入数字要查询的数字:5652叙子0出现次數字1出现1:2?36次斂宇2出现Z:2?36次數字3出现]>2?35次教字4出现]>2?35次數字5出现1:23时次教字?出现1:1625次邀字8出现:[:1625达数字9出现了:1625次Pressanykeytocontinue数宇0数字2数字3敎X4载丈5―數字?出数孛8出现了:5久现了=15达现了=15达现了=15达现了:1咏T:6vX现了:s疼现了:S次输入数字要查询的数字:50出LJLJLJp9$l7、y=^Pressanykeytocontinue.算法设计与分析实验报告二实验名称分治法实现归并排序算法评分实验日期年月日指导教师刘长松姓名刘飞初专业班级计算机0901学号10一.实验要求1.了解用分治法求解的问题:当要求解一个输入规模为n,且n的取值相当大的问题时,如采问题可以分成k个不同子集合,得到k个不同的可独立求解的子问题,其中l8、;//l
5、}else{i=0;while((zero/=l0)>yushu){i+十;}s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-l,m+l);//处理余位数voidmain(){inti,m,n,N,l;cout«n输入数字要查询的数字:";cin»N;cout«’’;n=N;for(i=0;n>=l0;i++){n/=10;}//求出N的位数n-1l=i;sum(N,l,l);for(i=0;i<10;i++)cout«"数字"《i«"出现了
6、:一.程序调试中的问题调试过程屮总是有这样那样的W题,通过•-步步的修改,最终得以实现。二.实验结果输入数字要查询的数字:5652叙子0出现次數字1出现1:2?36次斂宇2出现Z:2?36次數字3出现]>2?35次教字4出现]>2?35次數字5出现1:23时次教字?出现1:1625次邀字8出现:[:1625达数字9出现了:1625次Pressanykeytocontinue数宇0数字2数字3敎X4载丈5―數字?出数孛8出现了:5久现了=15达现了=15达现了=15达现了:1咏T:6vX现了:s疼现了:S次输入数字要查询的数字:50出LJLJLJp9$l
7、y=^Pressanykeytocontinue.算法设计与分析实验报告二实验名称分治法实现归并排序算法评分实验日期年月日指导教师刘长松姓名刘飞初专业班级计算机0901学号10一.实验要求1.了解用分治法求解的问题:当要求解一个输入规模为n,且n的取值相当大的问题时,如采问题可以分成k个不同子集合,得到k个不同的可独立求解的子问题,其中l8、;//l
8、;//l
此文档下载收益归作者所有