编程之美：1的数目

问题1描述：

求1~N十进制中1的数目f，f(12)=5

#include <stdio.h>

typedef long long LL;

LL Sum1s(LL n){
	LL iCount=0;
	LL iFactor=1;

	LL iLowerNum=0;
	LL iCurrNum=0;
	LL iHigherNum=0;

	while(n/iFactor!=0){
		iLowerNum = n-(n/iFactor)*iFactor;
		iCurrNum = (n/iFactor)%10;
		iHigherNum = n/(iFactor*10);

		switch(iCurrNum){
		case 0:
			iCount+=iHigherNum*iFactor;
			break;
		case 1:
			iCount+=iHigherNum*iFactor+iLowerNum+1;
			break;
		default:
			iCount+=(iHigherNum+1)*iFactor;
			break;
		}
		iFactor*=10;
	}
	return iCount;
}
int main(){  
	
	printf("%ld\n",Sum1s(12));
    return 0;  
}  

找规律：

9以下： 1个

99以下： 20个

999以下： 300个

9999以下： 4000个

...

999999999以下： 900000000个

9999999999以下： 10000000000个

99999999999以下： 110000000000个 //a

所以满足f(N)=N的值必然不会大于a，所以只要从后向前便利，找到第一个f(N)=N即为所求

#include <stdio.h>

typedef long long LL;

LL Sum1s(LL n){
	LL iCount=0;
	LL iFactor=1;

	LL iLowerNum=0;
	LL iCurrNum=0;
	LL iHigherNum=0;

	while(n/iFactor!=0){
		iLowerNum = n-(n/iFactor)*iFactor;
		iCurrNum = (n/iFactor)%10;
		iHigherNum = n/(iFactor*10);

		switch(iCurrNum){
		case 0:
			iCount+=iHigherNum*iFactor;
			break;
		case 1:
			iCount+=iHigherNum*iFactor+iLowerNum+1;
			break;
		default:
			iCount+=(iHigherNum+1)*iFactor;
			break;
		}
		iFactor*=10;
	}
	return iCount;
}
int main(){  
	
	LL N=99999999999;
	for(int i=N;i>0;i--){
		if(Sum1s(i)==i){
			printf("%lld\n",i);
			break;
		}
	}
    return 0;  
}  

编程之美：1的数目,布布扣,bubuko.com

编程之美：1的数目

原文：http://blog.csdn.net/starcuan/article/details/21250957