题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。
编程之美上的原题。
基本思路1:
每次判断各位是否为1,计数。然后依次/=10即可。
时间复杂度O(N*lgN)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <stdio.h> int countone(int num) { int cnt = 0; while(num) { if(num%10==1) { cnt++; } num/=10; } return cnt; } int countone_all(int n) { int sum = 0; int i; for(i=1;i<=n;i++) { sum += countone(i); } return sum; } int main() { int n = 12; printf("%d\n", countone_all(n)); return 0; } |
思路2:
可以用归纳法搞出一个递推公式。
但是如书上所述,这个递推公式是有范围限制的,n最大为11111111[……]