学步园

/*
30.在从 1到n 的正数中 1出现的次数
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
例如输入 12，从 1到12这些整数中包含 1的数字有 1， 10， 11  和 12， 
1一共出现了 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的情况是一共有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)。

如求123104
十万位1的次数：100000
万位1的次数    ：(1+1)*10000(110000,010000)
千位1的次数    ：(12+1)*1000
百位1的次数    ：(123)*100+（4+1）
十位1的次数    ：(1231)*10
个位1的次数    ：12310+1
思路： 求出整数十进制表示中1在每一位上出现的次数

        1.如果当前位==1
            if当前位不是最后一位 num1=当前位前几位表示的整数*后面的基数+后面的几位表示的整数+1;
            if当前位是最后一位，num1=当前位前几位表示的整数+1;
            所以： num1=（High）*iFactor+Low+1;;  
        2.如果当前位==0
            if当前位不是最后一位，num1=当前位前几位表示的整数*后面的基数
            if当前位是最后一位，num1=当前位前几位表示的整数
            所以： num1=（High）*iFactor;  
        3.如果当前位>1
            num1=（当前位前几位表示的整数+1）*后面的基数 
            所以： num1=（High+1）*iFactor;  
*/
#include <iostream>  
#include <stdio.h>  
using namespace std;  
  
int Sum1s( int n )  
{  
    int iCount = 0;  
    int iFactor = 1; //位数 
  
    int Low = 0;  
    int Cur = 0;  
    int High= 0;  
  
    while(n/iFactor!=0)  
    {  
        Low=n-(n/iFactor)*iFactor;  
        Cur=(n/iFactor)%10;  
        High=n/(iFactor*10);  
  
        switch(Cur)  
        {  
        case 0:  
            iCount+=High*iFactor;  
            break;  
        case 1:  
            iCount+=High*iFactor+Low+1;  
            break;  
        default:  
            iCount+=(High+1)*iFactor;  
            break;  
        }  
        iFactor*= 10;  
    }  
    return iCount;  
}  
  
int main()  
{  
    cout << Sum1s(123)<<endl;     
    return 0;  
}