? ? ?任務(wù)：給定一個(gè)十進(jìn)制的正整數(shù)，寫下從1開始，到N的所有整數(shù)，然后數(shù)一下其中出現(xiàn)“1”的個(gè)數(shù)。

? ? ?要求： 寫一個(gè)函數(shù) f(N) ，返回1 到 N 之間出現(xiàn)的 “1”的個(gè)數(shù)。例如 f(12) = 5。

? ? ? ? ? ? ? ?在32位整數(shù)范圍內(nèi)，滿足條件的“f(N) =N”的最大的N是多少。

?

1.設(shè)計(jì)思想：因?yàn)樯险n很多同學(xué)都給出了一個(gè)一個(gè)數(shù)地求出所出現(xiàn)的1，最多每個(gè)數(shù)也就求5、6次，但是所給的整數(shù)很大的時(shí)候計(jì)算機(jī)會(huì)一下循環(huán)遞歸N次來計(jì)算1的次數(shù)，這樣會(huì)導(dǎo)致效率非常低。我們都知道每個(gè)位數(shù)上都有一定的規(guī)律，每一位上出現(xiàn)1的次數(shù)都和其前一位和后一位以及當(dāng)前位上的數(shù)字有關(guān)系，所以得通過大量的數(shù)據(jù)一位一位的進(jìn)行分析，進(jìn)而找到每個(gè)數(shù)的規(guī)律。

?

通過對(duì)1位數(shù)、2位數(shù)、3位數(shù)，，，進(jìn)行分析統(tǒng)計(jì)，發(fā)現(xiàn)如果當(dāng)前位上的數(shù)字為0，1，大于等于1時(shí)有不同的情況；則此位上出現(xiàn)的1的次數(shù)分別會(huì)由更高位數(shù)上、更低位或者當(dāng)前位的數(shù)字決定，具體如下：

假設(shè)一個(gè)數(shù)為abcde

如果百位上數(shù)字c為0，百位上可能出現(xiàn)1的次數(shù)由更高位決定。比如：33033，則可以知道百位出現(xiàn)1的情況可能是：100~199，1100~1199,2100~2199，，.........，32100~32199，一共3300個(gè)。可以看出是由更高位數(shù)字（12）決定，并且等于更高位數(shù)字（ab）乘以 當(dāng)前位數(shù)（100）。

如果百位上數(shù)字為1，百位上可能出現(xiàn)1的次數(shù)不僅受更高位影響還受低位影響。比如：33133，則可以知道百位受高位影響出現(xiàn)的情況是：100~199，1100~1199,2100~2199，，.........，32100~32199，一共3300個(gè)。和上面情況一樣，并且等于更高位數(shù)字（ab）乘以 當(dāng)前位數(shù)（100）。但同時(shí)它還受低位影響，百位出現(xiàn)1的情況是：33100~33133,一共134個(gè)，等于低位數(shù)字（cde）+1。

如果百位上數(shù)字大于1（2~9），則百位上出現(xiàn)1的情況僅由更高位決定，比如12213，則百位出現(xiàn)1的情況是：100~199,1100~1199，2100~2199，...........，11100~11199,12100~12199,一共有1300個(gè)，并且等于更高位數(shù)字+1（ab+1）乘以當(dāng)前位數(shù)（100）。

除了百位上其他位數(shù)也都符合這個(gè)規(guī)律，所以只需要循環(huán)整數(shù)的位數(shù)次就可以求出最終的結(jié)果。

然后第二步實(shí)現(xiàn)的時(shí)候，開始以為只需要一個(gè)循環(huán)就行了，讓計(jì)算機(jī)循環(huán)。不過由于基數(shù)太大所以會(huì)用很長(zhǎng)時(shí)間

將要計(jì)算的范圍劃分為幾個(gè)區(qū)間，然后對(duì)每個(gè)區(qū)間進(jìn)行計(jì)算。比如說：

1到999，先將這些數(shù)劃分為10個(gè)區(qū)間：1-99、100-199 … 900-999

由f(999) = 300可知，300以后的區(qū)間段可以不計(jì)算。當(dāng)計(jì)算200時(shí)，可以先計(jì)算299，由于f(299)=160<200，200-299的區(qū)間可以都不必計(jì)算。對(duì)要計(jì)算的區(qū)間，再將它劃分為10個(gè)區(qū)間，重復(fù)進(jìn)行。這樣劃分的另一個(gè)好處是利用公式：f(10^n-1) ＝ n * 10^(n-1)，保存上次算得的f(n)直接計(jì)算下個(gè)數(shù)的f(n)。

2.源代碼：

#include<iostream> using namespace std;int Count(int n){int count = 0;//1的個(gè)數(shù)int CurrentPosition = 1;//當(dāng)前位int LowerNum = 0;//低位數(shù)字int CurrNum = 0;//當(dāng)前位數(shù)字int HigherNum = 0;//高位數(shù)字while(n / CurrentPosition != 0){LowerNum = n - (n / CurrentPosition) * CurrentPosition;//低位數(shù)字 CurrNum = (n / CurrentPosition) % 10;//當(dāng)前位數(shù)字 HigherNum = n / (CurrentPosition * 10);//高位數(shù)字if(CurrNum == 0)//如果為0,出現(xiàn)1的次數(shù)由高位決定 {count += HigherNum * CurrentPosition;//等于高位數(shù)字 * 當(dāng)前位數(shù) }else if(CurrNum == 1)//如果為1,出現(xiàn)1的次數(shù)由高位和低位決定 {count += HigherNum * CurrentPosition + LowerNum + 1;//高位數(shù)字 * 當(dāng)前位數(shù) + 低位數(shù)字 + 1 }else//如果大于1,出現(xiàn)1的次數(shù)由高位決定 {count += (HigherNum + 1) * CurrentPosition;//（高位數(shù)字+1）* 當(dāng)前位數(shù) }CurrentPosition *= 10;//前移一位 }return count; }void main() {int a;cout << "請(qǐng)輸入一個(gè)正整數(shù)：";cin >> a;cout << a;cout << "從1到該數(shù)字出現(xiàn)的1的次數(shù)為：" << Count(a) << endl;for (int i = 0; i < 4294967295 ; i++){if( Count(i) == i){cout << i << " ";}} }

改進(jìn)之后：

#include<iostream> using namespace std;int Count(int n){int count = 0;//1的個(gè)數(shù)int CurrentPosition = 1;//當(dāng)前位int LowerNum = 0;//低位數(shù)字int CurrNum = 0;//當(dāng)前位數(shù)字int HigherNum = 0;//高位數(shù)字while(n / CurrentPosition != 0){LowerNum = n - (n / CurrentPosition) * CurrentPosition;//低位數(shù)字 CurrNum = (n / CurrentPosition) % 10;//當(dāng)前位數(shù)字 HigherNum = n / (CurrentPosition * 10);//高位數(shù)字if(CurrNum == 0)//如果為0,出現(xiàn)1的次數(shù)由高位決定 {count += HigherNum * CurrentPosition;//等于高位數(shù)字 * 當(dāng)前位數(shù) }else if(CurrNum == 1)//如果為1,出現(xiàn)1的次數(shù)由高位和低位決定 {count += HigherNum * CurrentPosition + LowerNum + 1;//高位數(shù)字 * 當(dāng)前位數(shù) + 低位數(shù)字 + 1 }else//如果大于1,出現(xiàn)1的次數(shù)由高位決定 {count += (HigherNum + 1) * CurrentPosition;//（高位數(shù)字+1）* 當(dāng)前位數(shù) }CurrentPosition *= 10;//前移一位 }return count; }inline unsigned count_digits(unsigned long long num) {unsigned long long n = 1;unsigned ret = 0;while (n <= num) { n *= 10; ++ret; }return ret; }void get_nums() {unsigned long long x = 1e11 - 1, y;unsigned count = 0;unsigned idx = 0;while (true){++count;y = Count(x);if (x < y) {//x在1到10時(shí)，均不滿足x<y,所以x>10，下面的k值肯定大于0 unsigned k = count_digits(x) - 1;x -= (y - x - 1)/k + 1; }else if (x > y) { x = y; } else{cout<< ++idx << ": " << x << endl;//break;--x;if (x == 0) break;} } }void main() {int a;cout << "請(qǐng)輸入一個(gè)正整數(shù)：";cin >> a;cout << a;cout << "從1到該數(shù)字出現(xiàn)的1的次數(shù)為：" << Count(a) << endl;cout << "整數(shù)與次數(shù)相同的有以下這些，最大值為第一個(gè)數(shù)：";get_nums(); }

?

3.實(shí)驗(yàn)截圖：

4.實(shí)驗(yàn)總結(jié)：

? ? （1）這個(gè)題目跟之前的同樣是數(shù)學(xué)題類型的程序，需要利用大量的來分析統(tǒng)計(jì)，從中得出規(guī)律，否則就失去了編程的高效性；

? ? （2）而當(dāng)完成第一步之后以為第二步很簡(jiǎn)單，其實(shí)不然。感覺當(dāng)時(shí)一定是被成功的喜悅蒙蔽了雙眼，只是看它一直在滾動(dòng)數(shù)字，而且也得出了最后的結(jié)果，然而卻沒想到效率的問題，之才發(fā)現(xiàn)第二步的設(shè)計(jì)也包含了好多規(guī)律，所以一定要從頭到尾保持清醒的頭腦。

轉(zhuǎn)載于:https://www.cnblogs.com/mengxiangjialzh/p/4548613.html

總結(jié)

以上是生活随笔為你收集整理的Task 10 统计从1到某个整数之间出现的1的次数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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