学步园

#include <iostream>

using namespace std;
/**
* @author: jiq
* ---问题描述: 
*	给定一个正整数n，要求统计1-n的所有整数中1出现的次数。
*	比如11，那么1-11总共出现三次1。
*	(from the Beauty of Programming)
*
* --- 分析
*	很明显最直接的方法就是依次循环每一个数，然后对1的次数累加。
*	不过更好的方法是找规律。但是什么样的规律最简单？
*	
*	可以将问题表示为：
*	1-n所有个位是1的数字个数，
*	1-n所有十位是1的数字个数，
*	1-n所有百位是1的数字个数，...
*	这样1-n所有整数1出现的次数 = 上面的和
*	
*	那么给定一个数n，其1-n所有数字中x位是1的数字有多少个呢？
*	我们就是要找这个规律，以123为例子：
*	1-123个位是1的数字有：1,11,21...,91,101,111,121共13个
*	1-123十位是1的数字有：10,11,12...19,110,111,112...119共20个
*	1-123百位是1的数字有：100,101,102...123共24个。
*	所以1-123所有数字中1出现的次数是13+20+24 = 57个。
*	有什么规律呢？
*	
* ---结论(规律)：
*	对于数字n = abxcd。
*	(1) 若n的x位是0，那么1-n所有数字x位是1的数字总共有：ab*x个；
*	(2) 若n的x位是1，那么1-n所有数字x位是1的数字总共有：ab*x+cd+1个；
*	(3) 若n的x位是2-9，那么1-n所有数字x位是1的数字总共有：(ab+1)*x个；
*	注意：其中x可以为个位，十位，百位...对应值为1,10,100...
*
* ---编程：
*	至此，便可以依次循环数字n的每一位，根据n的当前位的值
*	用公式计算出1-n所有数字中第当前位是1的数字有多少个。
*	
*/

long cal_1_numbers(int n){
	int factor = 1;	//从个位开始
	int count = 0;	//1的次数
	int highNum = 0;//当前位前面的数值
	int lowNum = 0; //当前位后面的数值
	int currNum = 0;//当前位的数值

	//开始循环n的每一位，计算1-n中所有当前位是1的数字个数
	while(n/factor != 0){
	
		highNum = n / (factor * 10);
		lowNum = n - (n/factor)*factor;
		currNum = n/factor%10;

		//开始分情况计算
		switch(currNum){
		case 0:
			count += highNum * factor;
			break;
		case 1:
			count += highNum * factor + (lowNum + 1);
			break;
		default:
			count += (highNum + 1) * factor;
			break;
		}

		factor *= 10;	//个十百...分别对应1,10,100
	}

	return count;
}

int main(void){

	cout<<"cal_1_numbers(13) = "<<cal_1_numbers(13)<<endl;

	cout<<"cal_1_numbers(20) = "<<cal_1_numbers(20)<<endl;

	cout<<"cal_1_numbers(123) = "<<cal_1_numbers(123)<<endl;

	cout<<"cal_1_numbers(1203) = "<<cal_1_numbers(1203)<<endl;
	return 0;
}