学步园

方法1：将从1到N的所有数枚举出来，每个数都计算一下出现了多少个1，最后相加就可以得到结果，复杂度是O(n*lnn)

方法2：通过每一个位上1出现的次数来计算总的出现次数，举例来说512，

各位出现1的数包括：

1 (1)

11, 21,31,..91  (9)

101,121,131,...191(10)

201,211,221...291(10)

301,311,321,...391(10)

401,411,421,...491(10)

501,511, (2)

各位贡献的是52个，（51+1）*1 

十位贡献的1的个数为：

10, 11 ,12,....19(10)

110,111,...119 (10)

210, 211...219(10)

310,311,...319(10)

410,411,...419(10)

510, 511，512

(5)*10 + 2 +1

百位贡献的1的个数为：

100，，199 （100）

（0+1）*100

经过不断的这么分析，可以发现一个规律：

如果p位为0，那么该位贡献的结果为高位的数*10^p；

如果p为为1，那么该位贡献的结果为高位的数字*10^p + 低位数字 +1

如果p位为大于1，那么该位贡献的结果为（高位数字+1）*10^p

这个算法只和输入数字的长度有关系，输入数字的的长度为lnN，因此复杂度为lnN

依据上面的分析编写程序如下：

#include <stdio.h>
int Count1(int value) {
  int num = 0;
  while (value) {
    if (value % 10 ==1) {
      num++;
    }
    value = value / 10;
  }
  return num;
}
int Power(int radix, int exp) {
  int result = 1;
  for (int i = 0; i < exp; ++i) {
    result *= radix;
  }
  return result;
}
int Count1_1(int value) {
  int current_number = 0;
  int higher_parts = 0;
  int lower_parts = 0;
  int radix = 1;
  int num = 0;
  while (value / radix) {
    current_number = (value / radix) % 10;
    lower_parts = value - (value / radix) * radix;
    higher_parts = value / (radix * 10);
    switch (current_number) {
      case 0:
        num += higher_parts * radix ;
        break;
      case 1:
        num += higher_parts * radix  + lower_parts + 1;
        break;
      default:
        num += (higher_parts + 1) * radix ;
    }
    radix *= 10;
  }
  return num;
}  
  
int main(int argc, char** argv) {
  const int kValue = 512;
  int num = 0;
  for (int i = 0; i <= kValue; ++i) {
    num += Count1(i);
  }
  printf("%d\n", num);
  printf("%d\n", Count1_1(kValue));
}

参考文献：

http://www.nowamagic.net/algorithm/algorithm_CountOccurrencesOfOne.php

编程之美 2.4