編程之美：1的數目

問題1描述：

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

#include 

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 

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;  
}