算法全部实验梅俊瑞

《算法全部实验梅俊瑞》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一算法基础一、实验耍求1.学握算法的计算复杂性概念。2.学握算法渐近复杂性的数学表述。3.掌握描述算法的方法。4.实现具体的编程与上机实验，验证算法的时间复杂性函数。二、实验内容统计数字问题1•问题描述一本书的页码从自然数1开始顺序编码直到自然数no书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2,…，9o2.编程任务给定表示书的总页码的10进制整数n(l

2、<109)。编程计算书的全部页码屮分别用到多少次数字0,1,2,・・.，9o三、程序算法本程序主要通过字符数组的遍历来进行数字的统计、因为string消耗的资源过多、不考虑、通过循环和来得到字串、避免了处理前置0、进而得出结果四、程序代码#define_CRT_SECURE_NO_WARNINGS#include#includeusingnamespacestd;longcountNum[10];voidcountT(char*temp>inttotal){char=n

3、ewchar[2];intselect;for(inti=0;i〈total;i++){t[0]=temp[i];t[l]='';select=atoi(t);countNum[select]++;}}intmain(){intn;cout<<"输入页码数”<>n;for(inti=1;i<=n;i++){charemp二newchar[109];_itoa(i，temp,10);countT(temp,strlen(temp));}cout<<“统计结果“rendl;for(in

4、ti=0;i<10;i++)endl;甚至于无法得解cout«“数字,,<

5、0017000000700000070000007000000700000070000007000000700000010000000境结果奴字0的次数,效字1的次数:数字2的次数:数字3的次数:数字4的次数:奴字5的次数:奴字6的次数:奴字7的次数:咬字8的次薮I牧字9的次数,青按任意键继续・・・.实验二分治法一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n,且n的取值相当大的问题时，2.如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题,其中l

6、性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分冇效的。3.掌握分治法的一般控制流程。4.3.实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。二.实验内容循环赛H程表二、程序算法通过把所有选手分成两半、把大问题分解成小问题、把复杂的问题转化成简单的问题、然后推广到更大的问题、解出答案四、程序代码#includeusingnamespacestd;voidTable(intkJint**a){intn=1;for(inti=1;i<=k;i++

7、)n*=2;for(inti=1;i<=n;i++)a[l][i]intm=1;for(ints=1;s<=k;s++){n/=2;for(intt=1;t<=n;t++)for(inti<=2*for(intj=m+1;j<=a[i][j+(t-l)*m*a[i][j+(t-l)*m*m;i++)2*m;j++){2]=a[i・m][j+(t・l)*m*2・m];2-m]=a[i-m][j+(t-l)*m*2];m*=2;}voidpt(intn，int**a){for(inti=1;i<=n;i++)

8、{for(intj=1;j<=n;j++){cout<>n;a=newint*[100];for(inti=0;i<100;i++){a[i]=newint[100];}Table(n/2,a);Pt(n,a);return0;}五、程序调试中的问题开始没有注意数组边界问题导致越界六、实验结果8C:WINDOWSsystem