学步园

输入任意正整数n，统计1到n中1出现的次数，比如输入12，其中1，10,11,12出现了5次。

我知道的两种c++实现算法如下，写在一起比较起来方便：

#include <iostream>  
#include <sstream>
#include <string>
#include <time.h>

using namespace std;

void main(){
	clock_t start1,start2,end1,end2;
	double n;
	cin>>n;

	start1 = clock();
	int count = 0;	
	for(int i = 1;i <= n;i++){
		string nStr = to_string(i);
		int pos = nStr.find_first_of('1');
		if( pos != string::npos) {
			count++;			
			for(;nStr.find_first_of('1',pos + 1) != string::npos; count++, pos = nStr.find_first_of('1', pos + 1));
		}
	}
	end1 = clock();
	cout<<count<<" run time:"<<end1 - start1<<endl;
	
	start2 = clock();
	int length=0,sum=0;	
	int number=n;
	while(number>0)	
	{	 
		number/=10;	
		length++;	
	}	
	for(int i=1;i<=length;i++)	{	
		sum+=(int) (n / pow(10,i)) * pow(10,i-1);	
		int tmp=(int)(n/pow(10,i-1))%10;	
		if(tmp>1)
			sum+=pow(10,i-1);	
		if(tmp==1)	
			sum+=int(n)%(int)(pow(10,i-1))+1;	
	}
	end2 = clock();

	cout<<sum<<" run time:"<<end2 - start2<<endl;
}

应该也没有比第二种更快的算法了，因为已经超过了int的最大值，用double测试的结果都基本上运行时间为0