统计0到1亿中1出现的个数

时间:2014-07-22 14:51来源: 作者: 点击: 次

分享到：

p答《a href=http://www.oschina.net/question/218746_36212 target=_blank rel=nofollowPHP循环一亿次，怎样写效率高点？/a》/p p题目中给的例子比较特殊，是一亿。这样只需把一亿单独考虑，但如果遇到 12

答《PHP循环一亿次，怎样写效率高点？》

题目中给的例子比较特殊，是一亿。这样只需把一亿单独考虑，但如果遇到 1234567890 这样的数据，还是需要计算机程序辅助比较合适。

PHP 我没接触过，我一开始是用 newLisp 写了一段，然后照葫芦画瓢翻译成 PHP。就麻烦熟悉 PHP 的同学自己优化一下。

注：这个函数可以用来统计 1-9，但不能统计 0，因为前导 0 比较特殊。

function count_n($limit, $n) {
  if ($limit < $n) {
    return 0;
  }

  if ($limit == $n) {
    return 1;
  }

  $power = floor(log10($limit));
  $unit = pow(10, $power);
  $high = floor($limit / $unit);
  $low = $limit % $unit;

  return $high * $power * $unit / 10
      + (($high > $n)? $unit: (($high == $n)? 1 + $low: 0))
      + count_n($low, $n);
}

echo count_n(100000000, 1); // 80000001

2. [代码]最初用 newLisp 写的函数跳至 [1] [2] [全屏预览]

(define (count-n limit n)
  (if (< limit n) 0
    (= limit n) 1
    (letn (high (int ((string limit) 0))
           low (int (1 (string limit)))
           power (int (log limit 10)))
      (+ (count-n low n)
         (* high power (pow 10 (- power 1)))
         (if (> high n) (pow 10 power)
           (= high n) (+ 1 low)
           0)))))

(println (count-n 100000000 1))