编程之美 2.4 1的数目

      这道题的意思是，给定一个数n，那么从1到n这n个数中，1出现了几次。这个问题开始看，肯定不容易做，往往都是利用最笨的方法，一个数一个数的找就行了，那么如果n很大，就需要非常多的时间了，书中提供了更好的方法，需要发现数字中存在的相关规律：

      上面的意思就是，对于每一位出现1的情况都和它的高位和低位是相关的，所以，我们只要获取当前位，高位，低位就可以了，所以，首先，给出函数定义：

/*2.4 1的数目*/
int DutCountOf1InN(int);

/*
 * 对于数abcde，c这位出现1的次数分以下情况:
 * 1.若c > 1,结论是（ab + 1）* 100;
 * 2.若c == 1,结论是（ab）* 100 + de + 1;
 * 3.若c < 1,结轮是 ab * 100 + de + 1;
*/
int DutCountOf1InN(int n)
{
	if (n <= 0)
		return 0;

	int count = 0;
	/*乘数因子，以10倍递增*/
	int factor = 1;

	int lowerNum = 0;
	int currNum = 0;
	int highNum = 0;

	while (n / factor != 0)
	{
		/*低位数字*/
		lowerNum = n - (n / factor) * factor;
		/*当前位数字*/
		currNum = (n / factor) % 10;
		/*高位数字*/
		highNum = n / (factor * 10);

		switch (currNum)
		{
		case 0:
			count += highNum * factor;
			break;
		case 1:
			count += highNum * factor + lowerNum + 1;
			break;
		default:
			count += (highNum + 1) * factor;
			break;
		}

		factor *= 10;
	}

	return count;
}

      函数声明

/*c的数目*/
int DutCountOfCInN(int, int);

/*
 *对于数abmde，m这位出现c的次数分以下情况:
 * 1.若m > c,结论是（ab + 1）* 100;
 * 2.若m == c,结论是（ab）* 100 + de + 1;
 * 3.若m < c,结轮是 ab * 100 + de + 1;
*/
int DutCountOfCInN(int N, int c)
{
	if (N <= 0)
		return 0;

	int sum = 0;
    int low = 0, cur = 0, high = 0;
    int ifactor = 1;

    while (N / ifactor != 0)
    {
        low = N - (N / ifactor) * ifactor;
        cur = (N / ifactor) % 10;
        high = (N / ifactor) / 10;

        if (cur < c)
        {
            sum += high * ifactor;
        }
        else if (cur == c)
        {
            sum += high * ifactor + low + 1;
        }
        else
        {
            sum += (high + 1) * ifactor;
        }

        ifactor *= 10;
    }

    return sum;
}

编程之美 2.4 1的数目

原文：http://blog.csdn.net/dlutbrucezhang/article/details/39553499