1的数目
题目：给定一个十进制正整数N，写下从1开始到N的所有整数，数一下其中出现所有1的个数。
例如N=12，写下1，2，3，4，。。。，12，1的个数为5。
问题一
写出函数f(N)，表示对于给定的N，计算1到N之间的"1"的个数。
解法一
最直接的解法：从1遍历到N，将其每一个数中含有"1"的个数加起来。
此方法复杂度太高，为O(nlogn)。每个数计算此数的每一个位的数。
解法二
此方法是《编程之美》给的解法。
计算每一位的出现1的个数，如2345，分别计算千位、百位、十位、个位上可能出现1的个数。
以百位为例，可以找到以下规律：
- 当百位上的数字为0，如12023，百位上出现1的个数由更高位12决定。每一千个数0~999或1000~1999中，百位数出现1的数量为100次。因此，出现的1的个数为更高位(12)*当前位数（100）=1200.
- 当百位上的数字为1，如12123，百位上出现1的个数由更高位（12）和低位（23）决定。除了上一情况出现的个数，还有12100~12123中百位数中1出现的个数。即：出现的1的个数为更高位(12)*当前位数（100）+低位（23）+1.
- 当百位上出现的数字>1，如12223和第一种情况类似，但是要将高位+1（因为12***中的那一个也要考虑进去）。即：出现的1的个数为更高位+1(12+1)*当前位数（100）=1300.
[cpp]
int oneCount(int n){
int iCount=0;
int iFactor=1;
int iLow=0,iCurrent=0,iHigh=0;
while(n/iFactor!=0){
iLow=n%iFactor;
iCurrent=(n/iFactor)%10;
iHigh=n/(iFactor*10);
switch(iCurrent){
case 0:
iCount+=iHigh*iFactor;
break;
case 1:
iCount+=(iHigh*iFactor+iLow+1);
break;
default:
iCount+=(iHigh+1)*iFactor;
break;
}
iFactor*=10;
}
return iCount;
}
[/cpp]
解法3
此方法是我自己想的解法。
分析发现以下规律：
f(9)=1,f(99)=20,f(999)=300,f(9999)=4000。及f(10^b-1)=b*10^(b-1)。（定理一）
为什么会这样呢。因为对于每个位，出现1的概率为1/10，然后乘以位的数量。如999，个位出现1的概率为1/10，则个位出现100个1，同理，十位100个，百位100个。即300个。
解法：
- 将数字2345分解为2000+300+40+5，分别计算他们中含有的1的数量。
- 对于每个数字，如2000，我们知道(0~999)中1的个数为300，1000~1999中除了千位1出现的个数同样为300.即2*300.
-
在以上基础上，考虑千位出现1的个数，分为以下情况：
- 如果千位为0，不会出现。
- 如果千位为1（如1234），则千位出现的数量为千位后面的数+1，即234+1.
- 如果千位>1，则千位出现1的数量为1000.
[cpp]
int bitCount(int n){
int b=0;
int flag=n/(pow((float)10,b));
while(flag!=0){
b++;
int t=pow((float)10,b);
flag=n/t;
}
return b;
}
int oneCount2(int n){
int count=0;
int b=bitCount(n);
for(int i=b;i>0;i--){
int tennow=pow((float)10,i-1);
int tCur=n/tennow;
n%=tennow;
if(tCur==0){
continue;
}
if(tCur==1){
count+=n+1;
}
else{
count+=tennow;
}
count+=(tCur*((tennow/10)*(i-1)));
}
return count;
}
[/cpp]
问题二：
满足条件f(N)=N的最大的N是多少？
根据定理一可知，当N的位数b<=10时，N=10^b-1，f(N)=b*10^(b-1)，则N>f(N)。
而b=11时，f(N)>N。
当n>10^(11-1)时，能否证明不可能出现f(n)<n？如果可以证明，则在b=10~11中肯定能找到一个最大的N，使f(N)=N.
我证明不太出来，但是大体感觉是不能出现。因此，最大的N应该在b=10~11。
因此，令N=10^11-1=99 999 999 999，使n从N递减，检查是否f(n)=n,第一个就是最大的。
| 思想：找到N的范围，然后使用穷举法。不能直接使用穷举法，第一，时间复杂度太大。第二，因为要求最大的，因此没有一个终止条件。 当求最大的某个数的时候，首先要去判断一个上界，然后可以从上界朝下去穷举。 |
扩展问题：
对于其他进制，如二进制，f(1)的计算方法。
类比于问题一中的解法二和解法三，可以有两种解法。
解法一（对应于问题一解法二）
计算每个位出现1的次数。对于每一位：
根据当前位b的值（0或1），如果当前的值为0，则根据此位之前的数乘以当前位数（2^b）。
若当前值为1，此位之前的数乘以当前位数+此位之后的数+1.
解法二（对应问题一中解法三）
分析发现f(1)=1,f(11)=4,f(1…1<b个>)=b*2^(b-1)
将10101分为10000+100+1分别计算1的个数。
f(10101)=f(10000)+count(10000后面的数中该位1的数量)+f(100)+count(100后该位1的数量)+f(1)
根据定义可知f(1000)=f(1000-1)+1;
综上所述：
f(10101)= f(10000)+(101+1) +f(100)+(1+1)+f(1)= f(9999)+1+(101+1) +f(99)+1+(1+1)+f(1)