题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

编程之美上的原题。

基本思路1：

每次判断各位是否为1，计数。然后依次/=10即可。

时间复杂度O(N*lgN)

#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最大为1111111110。

归纳如下：

如果N为0~9 ，当N>=1时，f(N)=1，否则f(N)=0。

如果N为两位数，f(N)不仅和各位有关，还和十位有关：

(1)如果个位数大于等于1，则个位出现1的次数为十位数的数字加一（加个位的一个1）。如果N的个位数为0，个位出现1的次数就是0。

(2)如果十位数字等于1，则十位上出现1的次数为个位数字加1，如果十位数大于1，则十位数上出现1的次数为10。

可写出程序如下：

long long countone_plus(long long n)
{
	long long iCount = 0;
	long long iFactor = 1;
	long long iLowerNum = 0;
	long long iCurrNum = 0;
	long long iHigherNum = 0;

	while( n/iFactor )
	{
		iLowerNum = n - (n / iFactor) * iFactor;
		iCurrNum = (n/iFactor) % 10;
		iHigherNum = n / (iFactor * 10);

		switch(iCurrNum)
		{
			case 0:
				iCount += iHigherNum * iFactor;
				break;
			case 1:
				iCount += iHigherNum * iFactor + iLowerNum + 1;
				break;
			default:
				iCount += (iHigherNum + 1) * iFactor;
				break;
		}
		iFactor *= 10;
	}
	return iCount;
}