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 (<=230).
Output Specification:
For each test case, print the number of 1’s in one line.
Sample Input:
|
1 |
12 |
Sample Output:
|
1 |
5 |
The task is not simple. 试了几次才将遗漏的部分补上……
对某个数 Counting Ones 的话，可以针对每一位依次进行，计算该位为一时共有多少个数。
以 XXXXXYZZ 为例，现关注第 2 位。
- Y>1 时，有 ( XXXXX + 1 ) * 10^( ZZ的位数 ) 个第 2 位为 1 的数字；
- Y==1 时，则有 ZZ + ( XXXXX ) * 10^( ZZ的位数 ) 个第 2 位为 1 的数字；
- Y==0 时，则有 ( XXXXX ) * 10^( ZZ的位数 ) 个第 2 位为 1 的数字。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<stdio.h> #include<string.h> int power(int n) { int i,result=1; for(i=0;i<n;i++) { result*=10; } return result; } int main() { char buf[21],digit; int i,j,n,temp,total=0,pre,post; buf[0]='0'; gets(buf+1); n=strlen(buf); for(i=1;i<n;i++) { if(buf[i]=='1') { if(i!=n-1) { sscanf(buf+i+1,"%d",&post); post++; total+=post; } else { total+=1; } buf[i]=0; sscanf(buf,"%d",&pre); buf[i]='1'; post=power(n-i-1); total+=pre*post; } else if(buf[i]>'1') { digit=buf[i]; buf[i]=0; sscanf(buf,"%d",&pre); buf[i]=digit; pre++; post=power(n-i-1); total+=pre*post; } else { buf[i]=0; sscanf(buf,"%d",&pre); buf[i]='0'; post=power(n-i-1); total+=pre*post; } } printf("%d\n",total); } |