【微软面试题】请计算出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到N之间出现"1"的个数，比如 f(12)=5

分析：

先计算个位1的数目，再计算十位、百位、千位...上1的个数。

个位：0到9是一个周期，10到19也是一个周期，一个周期一定包括一个1，余下的不完整周期如果个位大于等于1，则包含1个1。

十位：0到99是一个周期，100到199也是一个周期，一个周期一定包括10个1，N%100如果小于10，则不包含1；如果大于等于20，则有10个１；否则有N%100-9个。

百位：N/1000个周期，每个周期有100个1；余下的不完整周期有N%1000个数，如果N%1000小于100，则不再包含1；如果N%1000大于200，则有100个1；否则有N%1000-99个1。

代码：

#include "stdafx.h"
#include "stdio.h"
#include "math.h"
void main()
{
 printf("请输入N/n");
 int n = 0 ;
 scanf("%d",&n);
 int iNumOf1 = 0 ;//
 for(int i = 0 , int t = 1 ; n >= t;i++,t*=10)
 {//依次处理个位、十位、百位、千位... 
  iNumOf1 += (n/(10*t))*t;//周期数乘每个周期1的字数
  int iResidue = n%(10*t) - (t - 1);//周期的的
  if( iResidue > 0 )
  { 
   //该位包1的数余数在区间[t,2t)
   iNumOf1 += ( iResidue > t ? t : iResidue);
  }
 }
 printf("/n有%d个1/n",iNumOf1);
}