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 西风萧瑟 阅读(1190) 评论(1)  编辑 收藏 引用 所属分类: 数学

评论:
# re: hdu3215 The first place of 2^n(对数思想) 2009-11-30 18:03 | 匿名
不错~  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理