首页 > ACM题库 > HDU-杭电 > HDU 3215-The first place of 2^n-动态规划-[解题报告]HOJ
2014
03-07

HDU 3215-The first place of 2^n-动态规划-[解题报告]HOJ

The first place of 2^n

问题描述 :

LMY and YY are mathematics and number theory lovers. They like to find and solve interesting mathematic problems together. One day LMY calculates 2n one by one, n=0, 1, 2,… and writes the results on a sheet of paper: 1,2,4,8,16,32,64,128,256,512,1024,……

LMY discovers that for every consecutive 3 or 4 results, there must be one among them whose first digit is 1, and comes to the conclusion that the first digit of 2n isn’t evenly distributed between 1 and 9, and the number of 1s exceeds those of others. YY now intends to use statistics to prove LMY’s discovery.

输入:

Input consists of one or more lines, each line describing one test case: an integer N, where 0≤N≤10000.

End of input is indicated by a line consisting of -1.

输出:

Input consists of one or more lines, each line describing one test case: an integer N, where 0≤N≤10000.

End of input is indicated by a line consisting of -1.

样例输入:

0
1
3
10
-1

样例输出:

1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
1 1 0 1 0 0 0 1 0
4 2 1 1 1 1 0 1 0

链接:http://acm.hdu.edu.cn/showproblem.php?pid=3215

利用对数求 N 的最高位 s=pow(10, log10(N)-[log10(N)])  ;  

#include <stdio.h>
  #include <math.h>
  const double eps=1.0e-6;
  int dp[10010][10];
  void Init( )
  {
      int y;
      double s=log10(2), t, x;
      dp[0][1]=1;
      for( int i=1; i<=10000; ++ i ){
          for( int j=1; j<10; ++ j ){
              dp[i][j]=dp[i-1][j];
          }
          t=s*i;
          x=t-(int)t;
          y=( int )(pow( 10, x )+eps);// 注意有精度损失 
          dp[i][y]++;
      }
  }
  int main( )
  {
      Init( );
      int N;
      while( ~scanf( "%d", &N ) ){
          if( N==-1 )break;
          for( int i=1; i<10; ++i ){
              printf( i==9?"%d\n":"%d ", dp[N][i] );
          }
      }
      return 0;
  }

参考:http://www.cnblogs.com/jian1573/archive/2012/09/19/2694236.html