這是《算法設計與分析》教材上的一道題，我們老師布置的第一道題。說的是統計出一本給定頁碼書中從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
小鼠標 閱讀(1128)
評論(0) 編輯 收藏 引用