http://acm.hdu.edu.cn/showproblem.php?pid=3215题目大意是计算2^0到2^n中每个数的最左边一位，然后记录1-9每个数字出现的次数并依次打印出来；
考虑到n的范围 [0,10000]， 不可能去计算 2^n
hdu 1060 Leftmost Digit
http://acm.hdu.edu.cn/showproblem.php?pid=1060 与此题一样
/**
先看一个例子：
31415926 最左面那位数是3，如何得来？
取对数： lg(3.1415926 * 10^7) = lg(3.1415926) + 7
也就是说，一个整数取对数以后变为2部分，不妨设小数部分为A (0 <= A < 1)，整数部分为B
所以，一个整数可以写成 10^A * 10^B
至于 10^B 是大家熟悉的 10000……
而 10^A 是什么样子的呢？ 肯定是小于10的小数 (为什么呢，如果大于10了，B的值则加1)
那么 A 的整数部分就是我们要求的数
大致思路就是：对一个数x求对数，取出小数部分A，则10^A的整数部分就是x的最左面的那位数
进入本题：
x = 2^n
lg(x) = n * lg(2)
A = lg(x) - lg(x)的整数部分
10^A = ……
其实这道题卡的事精度问题，整数与小数来回转化肯定有精度损失 这里的A要加上1.0e-6
*/
#include <stdio.h>
#include <math.h>
#define eps (1.0e-6)
int f[10010][10];
int main()
{
int i, j, y;
double A, x, s=log10(2);
f[0][1]=1;
for (i=1; i<=10000; i++) {
for(j=1; j<10; j++)
f[i][j] = f[i-1][j];
x = i * s;
A = x - (int)x;
y = (int) (pow(10, A)+eps);
f[i][y]++;
}
while (scanf("%d",&y),y+1) {
printf("%d", f[y][1]);
for(i=2; i<10; i++)
printf(" %d",f[y][i]);
printf("\n");
}
return 0;
}
posted on 2009-11-27 14:25
西风萧瑟 阅读(1207)
评论(1) 编辑 收藏 引用 所属分类:
数学