算法设计与分析实验报告-统计数字问题.doc

算法设计与分析实验报告

实验名称统计数字问题评分

实验日期年月日指导教师

姓名专业班级学号

一.实验要求

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次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。

四.程序代码

#includeiostream.h

ints[10];//记录0~9出现的次数

inta[10];//a[i]记录n位数的规律

voidsum(intn,intl,intm)

{

if(m==1)

{

intzero=1;

for(inti=0;i=l;i++)//去除前缀0

{

s[0]-=zero;

zero*=10;

}

}

if(n10)

{

for(inti=0;i=n;i++)

{

s[i]+=1;

}

return;

}//位数为1位时,出现次数加1

//位数大于1时的出现次数

for(intt=1;t=l;t++)//计算规律f(n)=n*10^(n-1)

{

m=1;inti;

for(i=1;it;i++)

m=m*10;

a[t]=t*m;

}

intzero=1;

for(inti=0;il;i++)

{

zero*=10;

}//求出输入数为10的n次方

intyushu=n%zero;//求出最高位以后的数

intzuigao=n/zero;//求出最高位zuigao

for(i=0;izuigao;i++)

{

s[i]+=zero;

}//求出0~zuigao-1位的数的出现次数

for(i=0;i10;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);//处理余位数

}

}

voidmain()

{

inti,m,n,N,l;

cout输入数字要查询的数字:;

cinN;

cout\n;

n=N;

for(i=0;n=10;i++)

{

n/=10;

}//求出N的位数n-1

l=i;

sum(N,l,1);

for(i=0;i10;i++)

{

cout数字i出现了:s[i]次\n;

}

}

程序调试中的问题

调试过程中总是有这样那样的问题，通过一步步的修改，最终得以实现。

六.实验结果