编程之美计算0到N中包含数字1的个数
轉(zhuǎn)自：http://blog.csdn.net/hongjuntu123/article/details/8743266
有這樣一個函數(shù)f(n),對于任意正整數(shù)n,它表示從 0 到 n 之間出現(xiàn)“1”的個數(shù),比如 f(1) = 1, f(13) = 6,請列出從 1 到 1234567890 中所有的 f(n) = n 的n, 要求準(zhǔn)確快速.
?
相信很多人都能立刻得出以下的解法：
??for(n:N)
??{
??????????判斷n包含1的個數(shù)；
??????????累加計數(shù)器；
??}
這是最直接的解法，但遺憾的是，時間復(fù)雜程度為O(N*logN)。因為還需要循環(huán)判斷當(dāng)前的n的各位數(shù)，該判斷的時間復(fù)雜程度為O(logN)。
接下來就應(yīng)該思考效率更高的解法了。說實話，這道題讓我想起另外一道簡單的算法題：
N為正整數(shù)，計算從1到N的整數(shù)和。
很多人都采用了循環(huán)求解。然后利用初等數(shù)學(xué)知識就知道S=N*(N+1)/2，所以用O(1)的時間就可以處理。
再回到本道題目，同理應(yīng)該去尋找到結(jié)果R與N之間的映射關(guān)系。
分析如下：
假設(shè)N表示為a[n]a[n-1]...a[1]，其中a[i](1<=i<=n)表示N的各位數(shù)上的數(shù)字。
c[i]表示從整數(shù)1到整數(shù)a[i]...a[1]中包含數(shù)字1的個數(shù)。
x[i]表示從整數(shù)1到10^i - 1中包含數(shù)字1的個數(shù)，例如，x[1]表示從1到9的個數(shù)，結(jié)果為1；x[2]表示從1到99的個數(shù)，結(jié)果為20；
當(dāng)a[1]=0時，c[1] = 0;
當(dāng)a[1]=1時，c[1] = 1;
當(dāng)a[1]>1時，c[1] = 1;
?
當(dāng)a[2]=1時，c[2] = a[1] +1+ c[1] + x[1];
當(dāng)a[2]>1時，c[2] = a[2]*x[1]+c[1]+10;
?
當(dāng)a[3]=1時，c[3] = a[2]*a[1] +1+ c[2] + x[2];
當(dāng)a[3]>1時，c[3] = a[3]*x[2]+c[2]+10^2;
......
?
以此類推
當(dāng)a[i]=1時，c[i] = a[i-1]*...*a[1] +1+ c[i-1]+x[i-1];
當(dāng)a[i]>1時，c[i] = a[i]x[i-1]+c[i-1]+10^(i-1);
?
?
實現(xiàn)的代碼如下：
?
Java代碼??
?
而以上解法的時間復(fù)雜程度只有O(logN)
?
?
?
?
?
?
/
編程之美之1的數(shù)目
2010/09/07?異淚?技術(shù)?309views |?Go to comment1 的數(shù)目
給定一個十進制正整數(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。
這個問題看上去并不是一個困難的問題，因為不需要太多的思考，大家都能找到一個最簡單的方法來計算 f（N），那就
是從1開始遍歷到N,將其中每一個數(shù)中含有“1”的個數(shù)加起來，
自然就得到了從1到N所有“1”的個數(shù)的和.C語言實現(xiàn)如下:
int?Count1(int?n)
{
????int?iNum=0;
????while(n!=0)
????{
????????iNum+=(n%10==1)?1:0;
????????n/=10;
??????????????
????}
????return?iNum;
}
int?Count2(int?n)
{
????int?iCount=0;
????for(int?i=0;i<=n;i++)
????{
????????iCount+=Count1(i);
????}?
????return?iCount;?
}
int?main()
{
?????int?x;
?????scanf("%d",&x);
?????printf("%d",Count2(x));
?????return?0;
}
但是這個算法的致命問題是效率，它的時間復(fù)雜度是O（N）×計算一個整數(shù)數(shù)字里面“1”的個數(shù)的復(fù)雜度 = O（N *log2 N）,如果給定的 N 比較大，則需要很長的運算時間才能得到計算結(jié)果。我試著輸入100000000,一共用了大概12秒,貌似有點長,不夠比作者說的40S快多了,作者的電腦有點舊…….- .-
解法二
<編程之美>先從一些簡單的情況開始觀察:
如果N是一位數(shù),可以確定f(N)=1
如過是二位數(shù),如果 N=13，那么從 1 到 13 的所有數(shù)字：1、2、3、4、5、6、
7、8、9、10、11、12、13，個位和十位的數(shù)字上都可能有 1，我們可以將它們分開來考慮，個位出現(xiàn) 1 的次數(shù)有兩次：1 和 11，十位出現(xiàn) 1 的次數(shù)有 4 次：10、11、12 和 13，所以 f（N）=2+4=6。要注意的是 11 這個數(shù)字在十位和個位都出現(xiàn)了 1， 但是 11 恰好在個位為 1 和十位為 1 中被計算了兩次，所以不用特殊處理，是對的。再考慮 N=23 的情況，它和 N=13 有點不同，十位出現(xiàn) 1 的次數(shù)為 10 次，從 10 到 19，個位出現(xiàn) 1 的次數(shù)為 1、11 和 21，所以f（N）=3+10=13。通過對兩位數(shù)進行分析，我們發(fā)現(xiàn)，個位數(shù)出現(xiàn) 1 的次數(shù)不僅和個位數(shù)字有關(guān)，還和十位數(shù)有關(guān)：如果 N 的個位數(shù)大于等于 1，則個位出現(xiàn) 1 的次數(shù)為十位數(shù)的數(shù)字加 1；如果N 的個位數(shù)為 0，則個位出現(xiàn) 1 的次數(shù)等于十位數(shù)的數(shù)字。而十位數(shù)上出現(xiàn) 1 的次數(shù)不僅和十位數(shù)有關(guān)，還和個位數(shù)有關(guān)：如果十位數(shù)字等于 1，則十位數(shù)上出現(xiàn) 1 的次數(shù)為個位數(shù)的數(shù)字加 1；如
果十位數(shù)大于 1，則十位數(shù)上出現(xiàn) 1 的次數(shù)為 10。
f(13) = 個位出現(xiàn)1的個數(shù) + 十位出現(xiàn)1的個數(shù) = 2 + 4 = 6；
f(23) = 個位出現(xiàn)1的個數(shù) + 十位出現(xiàn)1的個數(shù) = 3 + 10 = 13；
f(33) = 個位出現(xiàn)1的個數(shù) + 十位出現(xiàn)1的個數(shù) = 4 + 10 = 14；
…
f(93) = 個位出現(xiàn)1的個數(shù) + 十位出現(xiàn)1的個數(shù) = 10 + 10 =
20；
接著分析 3 位數(shù),
如果 N = 123：
個位出現(xiàn) 1 的個數(shù)為 13：1, 11, 21, …, 91, 101, 111, 121
?十位出現(xiàn) 1 的個數(shù)為 20：10～19, 110～119
?百位出現(xiàn) 1 的個數(shù)為 24：100～123
?f（23）= 個位出現(xiàn) 1 的個數(shù) + 十位出現(xiàn) 1 的個數(shù) + 百位出現(xiàn) 1 的次數(shù) = 13 + 20 + 24 = 57；同理我們可以再分析 4 位數(shù)、 位數(shù)。???根據(jù)上面的一些嘗試，下面我們推導(dǎo)出一般情況下，從 N 得
到 f（N）的計算方法：?假設(shè) N=abcde，這里 a、b、c、d、e 分別是十進制數(shù) N 的各個數(shù)位上的數(shù)字。如果要計算百位上出現(xiàn) 1 的次數(shù)，它將會受到三個因素的影響：百位上的數(shù)字，百位以下（低位）的數(shù)字，百
位（更高位）以上的數(shù)字。如果百位上的數(shù)字為 0，則可以知道，百位上可能出現(xiàn) 1 的次
數(shù)由更高位決定，比如 12 013，則可以知道百位出現(xiàn) 1 的情況可能
是 100～199，1 100～1 199，2 100～2 199，…，11 100~11 199，
一共有 1 200 個。也就是由更高位數(shù)字（12）決定，并且等于更高
位數(shù)字（12）×當(dāng)前位數(shù)（100）。
如果百位上的數(shù)字為 1，則可以知道，百位上可能出現(xiàn) 1 的次數(shù)不僅受更高位影響，還受低位影響，也就是由更高位和低位共同決定。例如對于 12 113，受更高位影響，百位出現(xiàn) 1 的情況是 100～199，1 100～1 199，2 100～2 199，…，11 100~11 199，一共 1 200個，和上面第一種情況一樣，等于更高位數(shù)字（12）×當(dāng)前位數(shù)（100）。但是它還受低位影響，百位出現(xiàn) 1 的情況是 12 100～12 113，一共114 個，等于低位數(shù)字（123）+1。?如果百位上數(shù)字大于 1（即為 2~9），則百位上可能出現(xiàn) 1的次數(shù)也僅由更高位決定，比如 12 213，則百位出現(xiàn) 1 的可能性為：100～199，1 100～1 199，2 100～2 199，…，11 100～11 199，12 100～12 199，一共有 1 300 個，并且等于更高位數(shù)字+1（12+1）
×當(dāng)前位數(shù)（100）。通過上面的歸納和總結(jié)，我們可以寫出如下的更高效算法來
計算 f（N）：
int?Sumls(int?n)
{
????int?iCount=0,iFactor=1,iLowerNum=0,iCurrNum=0,iHigherNum=0;
????while(n/iFactor!=0)
????{
????????iLowerNum=n-(n/iFactor)*iFactor;
????????iCurrNum=(n/iFactor)%10;
????????iHigherNum=n/(iFactor*10);
???????
????????switch(iCurrNum)
????????{
????????????case?0:
????????????????iCount+=iHigherNum*iFactor;
????????????????break;
????????????case?1:
????????????????iCount+=iHigherNum*iFactor+iLowerNum+1;
????????????????break;
????????????default:
????????????????iCount+=(iHigherNum+1)*iFactor;
????????????????break;
???????????????????????
????????}
????????iFactor*=10;
???????
????}
????return?iCount;?
}
int?main()
{
????int?x;
????scanf("%d",&x);???
????printf("%d",Sumls(x));
????return?0;
}
我試著輸入100000000瞬間就顯示出結(jié)果了,編程之美說效率至少提高了40000倍…
轉(zhuǎn)載于:https://www.cnblogs.com/vipwtl/p/5366877.html
總結(jié)
以上是生活随笔為你收集整理的编程之美计算0到N中包含数字1的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 屏蔽掉{{}}
- 下一篇： 正则表达式的顺序优先级