這是《算法設(shè)計與分析》教材上的一道題，我們老師布置的第一道題。說的是統(tǒng)計出一本給定頁碼書中從0~9各個數(shù)字出現(xiàn)的次數(shù)，頁碼最高不差過10e9。
窮舉法是很容易想到的，不過當(dāng)輸入過大時很耗時間。因此應(yīng)該總結(jié)規(guī)律。
#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();
}
統(tǒng)計出只有一位數(shù)的情況是很簡單的，我們來當(dāng)在統(tǒng)計好的一個數(shù)字前面再加上位數(shù)時統(tǒng)計結(jié)果會怎么增加。我們可以把這個增加的值看做兩部分，一部分是因高位增加導(dǎo)致地位數(shù)的取值范圍增大而導(dǎo)出的，另一部分是高位本身產(chǎn)生的。兩方面的計算都有規(guī)律可循。要特別注意0的計算。
請注意庫函數(shù)pow（）的返回值為double，轉(zhuǎn)換為int時會有精度丟失（調(diào)試中的表現(xiàn)為無論數(shù)據(jù)多大，結(jié)果總跟標(biāo)準(zhǔn)答案相差1），因此這里特地寫了一個Pow（）函數(shù)做返回值為int的乘方計算。
posted on 2012-03-08 19:38
小鼠標(biāo) 閱讀(1111)
評論(0) 編輯 收藏 引用