題目：輸入一個整數 n ，求從 1 到 n 這 n 個整數的十進制表示中 1 出現的次數。例如輸入 12 ，從 1 到 12 這些整數中包含 1 的數字有 1 ， 10 ， 11 和 12 ，1 一共出現了5 次。

分析：

???????? 我們曾遇到過求給定數num的二進制表示中1出現的次數，但此題是求十進制數中1出現的次數。簡單的來想，可以用除法、取余來求的一個數中1的個數，然后再從1到n循環即可解決。但當n比較大時，速度會比較慢。我們現在來嘗試從另一種思路來尋求一種更高效的方法。

??????? 我們可以換一種思路，分別求每位出現1的次數，然后再將每位出現1的次數相加即是所求。 不妨假設要求的數是abcde(a>0)，一般地，我們求第3位，也就是百位數字出現1的次數，可分為如下三種情況：

????????? (1)，當c=0 時，則該位出現1的數分析如下：

????????? 00100--00199

????????? 01100--01199

????????? 02100--02199

????????? ……

???????? 0b100--0b199

???????? 上面一共是b*100，對于a，我們進行類似的分析，從0b200到0(b+1)099的數字中，百位數字是不會出現1的：

???????? 0(b+1)100--0(b+1)199

???????? 0(b+2)100--0(b+2)199

???????? ……

???????? 0(b+9)100--0(b+9)199

???????? 0(b+10)100--0(b+10)199即1b199

?????? 從0b200到1b199，共有10*(b*100)個百位數字為1的數字。那么類似的可以知道，從1b200到2b199同樣有10*b*100個百位數字為1的數字。依次類推，從2b200到3b199，……，(a-2)b200到(a-1)b199，由于c=0，因此百位出現1的最大的數字應該為a(b-1)199；那么一共有多少個這樣的數據段呢？應該比較容易看出來，一共有a個。由此可以看出當c=0時，低位數字是不影響本位數字為1的數字的個數的。

由以上分析可知，百位數字為1的數字共有a*10*100+b*100=ab*100個；

??????? (2)，當c=1時，則該位出現1的數分析如下：

???????? 在(1)情況分析的基礎上，因為c=1，所以從a(b-1)200到ab1de中，仍有百位數字為1的數字存在，且比較容易知道一共有de+1個：即從ab100一直到ab1de，由此可以發現，此時低位數字影響了本位數字為1的數字的個數。

??????? 所以，此種情況，百位數字為1的數字共有：ab*100+de+1

??????? (3)，當c>1時，則該位出現1的數分析如下：

???????? 仍然在(1)分析的基礎上，因為c>1，所以從a(b-1)200到ab199（因為c>1，所以abcde>ab199，而ab200到abcde中百位數字是不會出現1的）中，仍有1*100個百位數字為1的數字，在此情況下，我們同樣可以發現，此時低位數字又不影響本位數字為1的數字的個數了。

??????? 所以，此種情況，百位數字為1的數字共有：ab*100+1*100=(ab+1)*100.

分析到這里，我想就應該比較容易寫出程序了吧^_^

轉載于:https://blog.51cto.com/10622551/1694395

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。