学步园

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

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

问题描述：给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有"1"的个数。例如：
N ＝ 2，写下1，2。这样只出现了1个"1"。
N ＝ 12，写下1，2，……，12，这样有5个"1"。
写一个函数f(N)，返回1到N之间出现的"1"的个数，比如f(12) = 5。

    假设N ＝ abcde，这里a,b,c,d,e分别是十进制数N的各个数位上的数字。如果要计算百位上出现1

的次数，将受3方面因素影响：百位上的数字，百位以下(低位)的数字，百位(更高位)以上的数字。

    如果百位上的数字为0，则可以知道百位上可能出现1的次数由更高位决定，比如12 013，则可以知

道百位出现1的情况可能是100－199，1 100－1 199，……，11 100－11 199，一共有1 200个。也就是

由更高位数字(12) 决定，并且等于更高位数字(12)×当前位数(100)。

    如果百位上的数字为1，则可以知道，百位上可能出现1的次数不仅受更高位影响，还受低位影响，

也就是由更高位和低位共同决定。例如12 113， 受更高位影响，百位出现1的情况是100－199，1 100

－1 199，……，11 100－11 199，一共有1 200个，和上面第一种情况一样，等于更高位数字(12)×当

前位数(100)。但它还受低位影响，百位出现1的情况是12 100－12 113，一共114个，等于低位数字

(113)+1。

    如果百位上数字大于1(即为2－9)，则百位上可能出现1的次数也仅由更高位决定，比如12 213，则

百位出现1的情况是：100－199，1 100－1 199，……，11 100－11 199，12 100－12 199，共1300个

，并且等于更高位数字+1(12+1)×当前位数(100)。

代码如下：

// 1Count.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <windows.h>
using namespace std;

LONGLONG Sum1s( ULONGLONG n )
{
	ULONGLONG iCount = 0;
	ULONGLONG iFactor = 1;

	ULONGLONG iLowerNum = 0;
	ULONGLONG iCurrNum = 0;
	ULONGLONG iHigherNum = 0;

	while( n / iFactor != 0 )
	{
		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;
}

int main()
{
	cout << Sum1s(123)<<endl;
	system("pause");  
	return 0;
}

这个算法速度很快：

结果如下：