[编程之美] 2.4 1的个数

本节给出的题目是：

给定一个十进制整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。

例如：

N = 2，写下1， 2。出现1个“1”。

N = 12，写下1， 2， 3，4，5，6，7，8，9，10，11，12。这样，1的个数是5。

（1）写一个函数f(N)，返回1到N之间出现的“1”的个数。

（2）满足条件f(N) = N的最大的N是多少。

书中给出的解法一是一般人看到这题就会想到的办法，依次遍历1到N的所有数，计算每个数字中的1的个数，然后累加。当然，这样的结果是时间复杂度很差。

解法二首先按照N的位数来进行分类讨论，然后再对各个位可能出现1的情况进行计算。

当N是1位数时：

比如N = 5，那么，从1到5中只有个位可能出现1，而且只有1次，因此，对1位数就有，当N = 0时，f(N) = 0，当N>=1时，f(N) = 1。

当N是2位数时：

比如N = 30，那么，十位和个位都可能出现1，个位出现1的情况有1，11，21，即个位出现1的次数等于N的十位上的数字，十位出现1的情况有10~19，为10，总共出现1的个数是3 + 10 = 13。

比如N = 31，4 + 10 = 14。

也就是，对于某一位来说，如果该位为0，那么，在该位可能出现1的情况就是该位以前的数从0一直到该位以前的数减1，也就是该位以前的数乘以该位所在位的基。

如果该位为1，那么，除了上面为0的情况，再加上该位为1，并且该位之后的数从0到该位之后的数，也就是上面为0的值加上该位之后的数再加1。

如果该位大于1，那么，该位可能出现1的情况就是该位以前的数从0到该位以前的数，也就是该位以前的数加1，然后乘以所在位的基。

从上面分析，可以很容易得到下面的程序：

long sum1s(long n)
{
	long icount = 0;
	long ifactor = 1;
	long ilowernum = 0;
	long icurrnum = 0;
	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;
}

[编程之美] 2.4 1的个数,布布扣,bubuko.com

[编程之美] 2.4 1的个数

原文：http://blog.csdn.net/luofengmacheng/article/details/20653871