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
西風蕭瑟 閱讀(1224)
評論(1) 編輯 收藏 引用 所屬分類:
數學