Counting Ones (30)

题目描述：
首先，翻译一下这个题。
题目的意思是：给出一个正整数，应该返回0到该正整数之间的十进制形式的 1出现的个数。
解题思路：
（1）将0 1----n数字列出  为了方便这里假设n为121  也就是000-121
（2）首先看所有数字的个位 这里分为三种情况就是n的个位大于1 小于1  等于1。 
  n的个位为1  那么  1出现的次数为00“1”-12“1”  前面的数字是变化的从00-12 有13中情况；  n的个位大于1  那么 如122的情况 1出现的次数将是 00“1”-12“1” 也是13，但是如果讨论的是十位就不一样了，这是需要重点考虑的。
  n的个位小于1  那么  如120的情况 1出现的次数将是 00“1”-11“1”  出现的情况是11次。
 （3）对每个十进制位进行讨论，将结果相加。但是当n是十位 、百位（非个位的）的情况下，要相对复杂一点，上面的只是启发一下解题思路。

下面的是正式的解题方法：  假设数字为abcde，对于abcde中的每一个数字，可以根据该数字与1的关系，求在该数字对应位置上1出现的次数。
具体来说：
假设我们要求百位出现1的次数，此时我们可以根据c与1的关系，求出百位1出现的次数。
（1）如果c = 0，则1出现的次数等于ab * 100，即 c前面的数 * c对应的基数
在该情况下，百位出现1的次数只与c前面的数有关。
（2）如果c = 1，则1出现的次数等于（ab * 100） + （de + 1），即（c前面的数 * c对应的基数） +（ c后面的数 + 1）
在该情况下，百位出现1的次数与c前面和c后面的数有关。
（3）如果c = 2，则1出现的次数等于（ab + 1）*100，即（c前面的数 +1）* c对应的基数

题目代码：
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int NumberOf1Between1AndN(int n)
{
   	int result=0,sum=0,std=1,i=n;
	while(i/std){
		int temp=i/(std*10);
		int num_bit=(i%(std*10))/std;
		if(num_bit==0) sum=temp*std;
		else if(num_bit==1) sum=temp*std+i%std+1;
		else 
			sum=(temp+1)*std;
		result=result+sum;
		std=std*10;
		sum=0;
	}
	return result;
}
int main(){
        int num=0;
        scanf("%d",&num);
        num=NumberOf1Between1AndN(num);
        printf("%d\n",num);
    return 0;
}
复杂度分析：
从解题思路的分析中可以看出：
其复杂度为输入正整数的n的十进制位数，也就是如果输入的是2位数（10-99） 执行次数为2，为5位数则while的执行次数为5，所以这里这里复杂度为log10（n），即log以10为低b的对数。