本文主要是介绍计算1到N的十进制数中1的出现次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
转自：http://hi.baidu.com/zhaoshengjin/blog/item/f1df6618cb1debbe4bedbc5d.html
问题描述：给定一个十进制正整数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，一共14个，等于低位数字
(13)+1。一共为1200+14 = 1214.
如果百位上数字大于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)。
今天百度之星的第二题就是求几个数出现的次数，比如求12388以内以88结尾的所有数的数量，如果最后两位>=88则数量为123+1，但是如果最后两位<88，数量为123。一定要谨慎，多少次教训了！
按照位来统计在这个位上所有的1的个数
#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;
//从数n的最低位开始，n/iFactor表示的是当前处理的数的数值
//譬如数1234，则n/iFactor依次表示 1234，123,12,1
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(100000000);
cin.get();
return 0;
}
这篇关于计算1到N的十进制数中1的出现次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
