【題 ? 目】輸入一個整數(shù)n，求從1到n這n個正數(shù)中，1出現(xiàn)的次數(shù)。例如：輸入12，出現(xiàn)一的數(shù)字有1，10，11，12共有5個1，則輸出5.

　　【思 路1】幾乎所有的算法題目都有很直觀容易想到的方法，當(dāng)然這類方法的效率通常都不是很好，然而解決問題是第一要義。所以還是從最容易想到的入手。我們可以遍歷從1到n的每一個數(shù)字k，對于k我們計算出它其中包含的1的個數(shù)，方法其實很簡單，只需要分別判斷個位，十位，百位，千位等的每一位是否為1，然后用計數(shù)器記錄就OK了。這種思路很簡單，我們很容易就可以寫出如下的代碼：

1 #include<iostream>
2 #include<string>
3 using namespace std;
4
5 //返回任意一個整數(shù)k中包含的1的個數(shù)
6 int NumbersOf1s(unsigned int k)
7 {
8 int cnt = 0;
9 while(k)
10 {
11 //該位是1，計數(shù)器就加1；
12 if(k % 10 == 1)
13 cnt++;
14
15 k = k / 10;
16 }
17
18 return cnt;
19 }
20
21 //返回從1到n的n個整數(shù)中所包含的1的個數(shù)
22 int NumbersOf1sFrom1ToN(unsigned int n)
23 {
24 if(n < 0)
25 return 0;
26
27 int count = 0;
28 for(int i = 1;i <= n;i++)
29 {
30 count += NumbersOf1s(i);
31 }
32
33 return count;
34 }
35
36 int main()
37 {
38 cout<<"Please Enter the number N:"<<endl;
39 unsigned int number = 0;
40 cin>>number;
41
42 cout<<"The Numbers of 1 From 1 to N is:"<<endl;
43 cout<<NumbersOf1sFrom1ToN(number)<<endl;
44
45 return 0;
46 }

　　運行結(jié)果如下：

　

---

【思 路2】上述算法的效率不是很好，尤其對于n非常大的情況，這種算法花費的時間很長。其實我們并不需要對于每一個數(shù)字計算出它包含的1的個數(shù)，我們可以逐位考慮，所有1的個數(shù)等于個位上1的個數(shù)+十位上1的個數(shù)+百位上1的個數(shù)+千位上1的個數(shù)+。。。接下來的問題，就是如何求解這些位上1的個數(shù)？

　　首先，我們有如下比較容易得到的結(jié)論，0-9中1的個數(shù)是1個，0-99中十位（10-19）上1的個數(shù)是10，0-999中百位上（100-199）上1的個數(shù)是100，以此類推。為什么需要這些數(shù)字，我們經(jīng)過簡單羅列，很容易發(fā)現(xiàn)：個位上1的個數(shù)，實際上和這個數(shù)字包含多少個10有關(guān)，因為對于個位來說，總是從0-9循環(huán)，十位上1的個數(shù)，實際上和這個數(shù)字包含多少個100有關(guān)，因為每包含1個100，就有0-99的循環(huán)，而0-99中十位上的1是10個；那么關(guān)系究竟是什么呢？我們看下面的例子來理解：

　　對于數(shù)字123：

　　123/10=12，包含12個10，每個10包含1個1（個位1）所以個位共包含12*1=12個1；余數(shù)的情況后面單獨討論；

　　123/100（或者12/10）=1，包含1個100，每個100包含10個1（十位1），所以十位共包含1*10=10個1；余數(shù)的情況后面單獨討論；

　　123/1000（或者1/10）=0，包含0個1000，每個1000包含100個1（百位1），所以百位共包含0*100=0個1；余數(shù)的情況后面單獨討論；

　　現(xiàn)在考慮余數(shù)的兩種情況：

　　（1）余數(shù)大于1的情況：

　　數(shù)個位時，余數(shù)3大于1；所以個位上1的個數(shù)要+1；

　　數(shù)十位時，余數(shù)2大于1；因為增加了100-120之間（10-19）的數(shù)字即110-119，所以十位上1的個數(shù)要+10；

　　（2）余數(shù)等于1的情況：

　　數(shù)百位時，余數(shù)等于1；我們應(yīng)該增加100-123這24個數(shù)字中百位上的1，共計24個；

　　在上面的計算中我們發(fā)現(xiàn)123/1000=0包含0個1000，所以百位包含0*100個1,這是常規(guī)的情況，實際上由于百位為1，從100到n（123）中還應(yīng)增加：123-100+1個1.

　　總結(jié)上面的情況：就是對于每一位（個位，十位，百位），我們計算他們“通常”情況下（即該數(shù)字包含多少個10，100，1000乘以對應(yīng)的1的個數(shù)）包含的1的個數(shù)+該位上余數(shù)大于1（等于1）的情況下包含的1的個數(shù) = 該位上1的總個數(shù)，所有的位遍歷，求和，就OK了。根據(jù)這種思路我們可以得到如下的代碼：

1 #include<iostream>
2 #include<string>
3 using namespace std;
4
5 int NumbersOf1sFrom1ToN(unsigned int n)
6 {
7 int currentN = n;
8
9 //計數(shù)器
10 int cnt = 0;
11
12 //商，計算該數(shù)字包含多少個10，100，1000等
13 int quotient = 0;
14
15 //余數(shù)，計算除去“整”的包含，剩下的數(shù)字包含的1的個數(shù)
16 int remainder = 0;
17
18 //每一輪循環(huán)中的權(quán)重，分別記錄10，100，1000中包含多少個位1，十位1，百位1；
19 int mult = 1;
20
21 while(currentN)
22 {
23 quotient = currentN / 10;
24 remainder = currentN % 10;
25
26 //包含多少個10，100，1000，乘以對應(yīng)的數(shù)量的個位1，十位1，百位1
27 cnt += quotient * mult;
28
29 //余數(shù)大于1，多加一個該輪下的權(quán)重
30 if(remainder > 1)
31 {
32 cnt += mult;
33 }
34 //余數(shù)等于1
35 else if(remainder == 1)
36 {
37 cnt += n - currentN * mult + 1;
38 }
39
40
41 currentN = currentN / 10;
42 mult *= 10;
43 }
44
45 return cnt;
46 }
47
48 int main()
49 {
50 cout<<"please enter the number N:"<<endl;
51 unsigned int number = 0;
52 cin>>number;
53
54 cout<<"the number of 1s From 1 to N is:"<<endl;
55 cout<<NumbersOf1sFrom1ToN(number)<<endl;
56
57 return 0;
58 }

　　運行結(jié)果如下：

---

?

References:

程序員面試題精選100題：http://zhedahht.blog.163.com/blog/static/25411174200732494452636/

注：

1）本博客所有的代碼環(huán)境編譯均為win7+VC6。所有代碼均經(jīng)過博主上機調(diào)試。

2）博主python27對本博客文章享有版權(quán)，網(wǎng)絡(luò)轉(zhuǎn)載請注明出處http://www.cnblogs.com/python27/。對解題思路有任何建議，歡迎在評論中告知。

轉(zhuǎn)載于:https://www.cnblogs.com/python27/archive/2011/12/14/2288205.html

總結(jié)

以上是生活随笔為你收集整理的【算法21】从1到n的正数中1的出现次数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。