PAT A1049 Counting Ones (30 分)

The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (≤2^ ​30​ ).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input:

12

Sample Output:

5

以下是AC的代碼：

#include<cstdio>
int main(void){
	int n,a=1,ans=0;
	int left,now,right;
	scanf("%d",&n);
	while(n/a != 0){
		left=n/(a*10);
		now = n/a%10;
		right=n%a;
		if(now==0) ans+=left*a;
		else if(now == 1) ans+=left*a+right+1;
		else ans+=(left+1)*a;
		a*=10;
	}
	printf("%d",ans);
	return 0;
}
           

思路：

這道題難就難在找數 1 出現次數的規律。

比如數字 30710，1，2，3，4，5位分别對應，0，1，7，0，3，我們可以分别數出來每一位上能出現1的個數，加起來就是總的1的個數。

第一位 0，這是小于1 的，在0的左邊為 0000 到 3070 的時候，0位才可能取到1，總的有3071次；

第二位 1，等于1，隻有左邊取000 到 306，右邊取0-9，一共3070次，或者左邊取307，右邊隻能取0，+1次；

第三位，7大于1，隻有左邊取00-30，右邊取00-99，可以取到1，一共3100次；

第四位，0小于1，隻有左邊取0-2，右邊取000-999，才可能取到1，一共3000次；

第五位，3大于1，右邊可以是0000-9999，一共10000個；

是以總的1有 ans = 3071+3071+3100+3000+10000個。

用類似的思路處理題目給的數字就可以了。