这是《算法设计与分析》教材上的一道题，我们老师布置的第一道题。说的是统计出一本给定页码书中从0~9各个数字出现的次数，页码最高不差过10e9。
穷举法是很容易想到的，不过当输入过大时很耗时间。因此应该总结规律。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define LEN 20
int bs[] = 
{0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000};
int BS = 1111111111;
void StrtoNum(char *str, int *num)
{
int i, len;
len = strlen(str);
*num = 0;
for(i = 0; i < len; i++)
*num = *num * 10 + str[i] - '0';
}
int Pow(int a, int b)
{
int i, t;
t = a;
for(i = 0; i < b - 1; i++)
t *=a;
return t;
}
int GetMod(int a)
{
return BS % Pow(10, a);
}
int main()
{
int i, j;
int nb;// now bit
char nums[LEN];
int num;
int rs[10];// result
int len;
int mh;//most high
int nt;
while(gets(nums) != NULL)
{
memset(rs, 0, sizeof(rs));
len = strlen(nums);
StrtoNum(nums, &num);
//
//printf("num = %d\n", num);
//
mh = nums[len - 1] - '0';
for(i = 0; i <= mh; i++)//init the lowest bit
rs[i] = 1;
for( i = 1; i < len; i++)
{
nb = len - i -1;
mh = nums[nb] - '0';
StrtoNum(&nums[nb + 1], &nt);
//
//printf("mh = %d nt = %d\n", mh, nt);
//
rs[mh] += nt + 1;//@2, mh mh
for(j = 0; j < mh; j++)//@2 others
{
rs[j] += Pow(10, i);
}
for(j = 0; j < 10; j++)//@1
{
rs[j] += mh * bs[i];
}
}
rs[0] -= GetMod(len);
for(i = 0; i < 10; i++)
printf("%d %d\n", i, rs[i]);
}
//getchar();
}
统计出只有一位数的情况是很简单的，我们来当在统计好的一个数字前面再加上位数时统计结果会怎么增加。我们可以把这个增加的值看做两部分，一部分是因高位增加导致地位数的取值范围增大而导出的，另一部分是高位本身产生的。两方面的计算都有规律可循。要特别注意0的计算。
请注意库函数pow（）的返回值为double，转换为int时会有精度丢失（调试中的表现为无论数据多大，结果总跟标准答案相差1），因此这里特地写了一个Pow（）函数做返回值为int的乘方计算。
posted on 2012-03-08 19:38
小鼠标 阅读(1025)
评论(0) 编辑 收藏 引用