問題：
給定一個十進制正整數(shù)N，寫下從1開始，到N的所有整數(shù)，然后數(shù)一下其中出現(xiàn)的所有“1”的個數(shù)。
例如：
N= 2，寫下1，2。這樣只出現(xiàn)了1個“1”。
N= 12，我們會寫下1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12。這樣，1的個數(shù)是5。
問題一：
寫一個函數(shù)f(N),返回1到N之間出現(xiàn)1的個數(shù)，比如f（12）= 5。
解法一：
讓我們首先想到的一個方法是：遍歷1~N，統(tǒng)計每個數(shù)1出現(xiàn)的個數(shù)，相加便得到所有1的個數(shù)。
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很大，需要很長時間才能得出計算結果。
?
?
解法二：
分析的出規(guī)律。
<1> 1位數(shù)情況
這個簡單，如果N = 3，那么從1到3的所有數(shù)字：1,2,3，只有個位數(shù)出現(xiàn)1，而且只出現(xiàn)一次。可以發(fā)現(xiàn)，N是個位數(shù)時，N >=1,那么f（N）= 1；N = 0，f（N）= 0；
<2> 2位數(shù)情況
<3> 3位數(shù)情況
?
同理分析4位數(shù)，5位數(shù)。。。。。
設N = abcde ,其中abcde分別為十進制中各位上的數(shù)字。
如果要計算百位上1出現(xiàn)的次數(shù)，它要受到3方面的影響： 百位上的數(shù)字，百位一下（低位）上的數(shù)字，百位一上（高位）上的數(shù)字 。
如果 百位上數(shù)字為0 ，百位上可能出現(xiàn)1的次數(shù)由更高位決定。比如：12013，則可以知道百位出現(xiàn)1的情況可能是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200個?？梢钥闯鍪怯筛呶粩?shù)字（12）決定，并且等于更高位數(shù)字（12）乘以 當前位數(shù)（100）。
如果 百位上數(shù)字為1 ，百位上可能出現(xiàn)1的次數(shù)不僅受更高位影響還受低位影響。比如：12113，則可以知道百位受高位影響出現(xiàn)的情況是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200個。和上面情況一樣，并且等于更高位數(shù)字（12）乘以 當前位數(shù)（100）。但同時它還受低位影響，百位出現(xiàn)1的情況是：12100~12113,一共114個，等于低位數(shù)字（113）+1。
如果 百位上數(shù)字大于1（2~9） ，則百位上出現(xiàn)1的情況僅由更高位決定，比如12213，則百位出現(xiàn)1的情況是：100~199,1100~1199，2100~2199，...........，11100~11199,12100~12199,一共有1300個，并且等于更高位數(shù)字+1（12+1）乘以當前位數(shù)（100）。
1
/*
N = abcde 百位上數(shù)字是c
2
僅以求百位上出現(xiàn)1的情況為例。
3
*/
4
int
count =
0
;
5
//
百位上數(shù)字為0,百位上可能出現(xiàn)1的次數(shù)由更高位決定
6
if
(c ==
0
){
7
//
等于更高位數(shù)字（ab）* 當前位數(shù)（100）
8
count += ab*
100
;
9
}
10
//
百位上數(shù)字為1,百位上可能出現(xiàn)1的次數(shù)不僅受更高位影響還受低位影響
11
else
if
(c ==
1
){
12
//
更高位數(shù)字（ab） * 當前位數(shù)（100） + 低位數(shù)字（de）+1
13
count += ab*
100
+ de +
1
;
14
}
15
//
百位上數(shù)字大于1（2~9）,百位上出現(xiàn)1的情況僅由更高位決定
16
else
{
17
//
（更高位數(shù)字+1（ab+1））* 當前位數(shù)（100）
18
count += (ab +
1
) *
100
;
19
}
1
#include<stdio.h>
2
3
long
long
int
Count(
long
long
int
n){
4
//
1的個數(shù)
5
long
long
int
count =
0
;
6
//
當前位
7
long
long
int
Factor =
1
;
8
//
低位數(shù)字
9
long
long
int
LowerNum =
0
;
10
//
當前位數(shù)字
11
long
long
int
CurrNum =
0
;
12
//
高位數(shù)字
13
long
long
int
HigherNum =
0
;
14
if
(n <=
0
){
15
return
0
;
16
}
17
while
(n / Factor !=
0
){
18
//
低位數(shù)字
19
LowerNum = n - (n / Factor) *
Factor;
20
//
當前位數(shù)字
21
CurrNum = (n / Factor) %
10
;
22
//
高位數(shù)字
23
HigherNum = n / (Factor *
10
);
24
//
如果為0,出現(xiàn)1的次數(shù)由高位決定
25
if
(CurrNum ==
0
){
26
//
等于高位數(shù)字 * 當前位數(shù)
27
count += HigherNum *
Factor;
28
}
29
//
如果為1,出現(xiàn)1的次數(shù)由高位和低位決定
30
else
if
(CurrNum ==
1
){
31
//
高位數(shù)字 * 當前位數(shù) + 低位數(shù)字 + 1
32
count += HigherNum * Factor + LowerNum +
1
;
33
}
34
//
如果大于1,出現(xiàn)1的次數(shù)由高位決定
35
else
{
36
//
（高位數(shù)字+1）* 當前位數(shù)
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
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
