问题：
给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。
例如：
N= 2，写下1，2。这样只出现了1个“1”。
N= 12，我们会写下1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12。这样，1的个数是5。
问题一：
写一个函数f(N),返回1到N之间出现1的个数，比如f（12）= 5。
解法一：
让我们首先想到的一个方法是：遍历1~N，统计每个数1出现的个数，相加便得到所有1的个数。
1
#include<stdio.h>
2
#include<stdlib.h>
3
#include<
string
.h>
4
long
long
int
Count(
long
long
int
n){
5
long
long
int
count =
0
;
6
while
(n){
7
count += (n %
10
==
1
)?
1
:
0
;
8
n = n /
10
;
9
}
10
return
count;
11
}
12
int
main()
13
{
14
long
long
int
n,i,count;
15
while
(scanf(
"
%lld
"
,&n) !=
EOF){
16
count =
0
;
17
for
(i =
1
;i <= n;i++
){
18
count +=
Count(i);
19
}
20
printf(
"
%lld\n
"
,count);
21
}
22
return
0
;
23
}
这个方法虽然很容易想，但是不是一个好方法。致命问题就是效率问题。如果给定的N很大，需要很长时间才能得出计算结果。
解法二：
分析的出规律。
<1> 1位数情况
这个简单，如果N = 3，那么从1到3的所有数字：1,2,3，只有个位数出现1，而且只出现一次。可以发现，N是个位数时，N >=1,那么f（N）= 1；N = 0，f（N）= 0；
<2> 2位数情况
<3> 3位数情况
同理分析4位数，5位数。。。。。
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数，它要受到3方面的影响： 百位上的数字，百位一下（低位）上的数字，百位一上（高位）上的数字 。
如果 百位上数字为0 ，百位上可能出现1的次数由更高位决定。比如：12013，则可以知道百位出现1的情况可能是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200个。可以看出是由更高位数字（12）决定，并且等于更高位数字（12）乘以 当前位数（100）。
如果 百位上数字为1 ，百位上可能出现1的次数不仅受更高位影响还受低位影响。比如：12113，则可以知道百位受高位影响出现的情况是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200个。和上面情况一样，并且等于更高位数字（12）乘以 当前位数（100）。但同时它还受低位影响，百位出现1的情况是：12100~12113,一共114个，等于低位数字（113）+1。
如果 百位上数字大于1（2~9） ，则百位上出现1的情况仅由更高位决定，比如12213，则百位出现1的情况是：100~199,1100~1199，2100~2199，...........，11100~11199,12100~12199,一共有1300个，并且等于更高位数字+1（12+1）乘以当前位数（100）。
1
/*
N = abcde 百位上数字是c
2
仅以求百位上出现1的情况为例。
3
*/
4
int
count =
0
;
5
//
百位上数字为0,百位上可能出现1的次数由更高位决定
6
if
(c ==
0
){
7
//
等于更高位数字（ab）* 当前位数（100）
8
count += ab*
100
;
9
}
10
//
百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响
11
else
if
(c ==
1
){
12
//
更高位数字（ab） * 当前位数（100） + 低位数字（de）+1
13
count += ab*
100
+ de +
1
;
14
}
15
//
百位上数字大于1（2~9）,百位上出现1的情况仅由更高位决定
16
else
{
17
//
（更高位数字+1（ab+1））* 当前位数（100）
18
count += (ab +
1
) *
100
;
19
}
1
#include<stdio.h>
2
3
long
long
int
Count(
long
long
int
n){
4
//
1的个数
5
long
long
int
count =
0
;
6
//
当前位
7
long
long
int
Factor =
1
;
8
//
低位数字
9
long
long
int
LowerNum =
0
;
10
//
当前位数字
11
long
long
int
CurrNum =
0
;
12
//
高位数字
13
long
long
int
HigherNum =
0
;
14
if
(n <=
0
){
15
return
0
;
16
}
17
while
(n / Factor !=
0
){
18
//
低位数字
19
LowerNum = n - (n / Factor) *
Factor;
20
//
当前位数字
21
CurrNum = (n / Factor) %
10
;
22
//
高位数字
23
HigherNum = n / (Factor *
10
);
24
//
如果为0,出现1的次数由高位决定
25
if
(CurrNum ==
0
){
26
//
等于高位数字 * 当前位数
27
count += HigherNum *
Factor;
28
}
29
//
如果为1,出现1的次数由高位和低位决定
30
else
if
(CurrNum ==
1
){
31
//
高位数字 * 当前位数 + 低位数字 + 1
32
count += HigherNum * Factor + LowerNum +
1
;
33
}
34
//
如果大于1,出现1的次数由高位决定
35
else
{
36
//
（高位数字+1）* 当前位数
37
count += (HigherNum +
1
) *
Factor;
38
}
39
//
前移一位
40
Factor *=
10
;
41
}
42
return
count;
43
}
44
45
int
main(){
46
long
long
int
a;
47
while
(scanf(
"
%lld
"
,&a) !=
EOF){
48
printf(
"
%lld\n
"
,Count(a));
49
}
50
return
0
;
51
}
转载：http://blog.csdn.net/sjf0115/article/details/8600599
