文档介绍:该【1的数目 】是由【和合】上传分享,文档一共【13】页,该文档可以免费在线阅读,需要了解更多关于【1的数目 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。:.
写书评,赢取《编程之美--微软技术面试心得》
1的数目
给定一个十进制正整数N,写下从1开始,到N的所有整数,
然后数一下其中出现的所有“1”的个数。
例如:
N=2,写下1,2。这样只出现了1个“1”。
N=12,我们会写下1,2,3,4,5,6,7,8,9,10,11,12。这样,1
的个数是5。
问题是:
(fN),返回1到N之间出现的“1”的个数,比如(f12)
=5。
,满足条件“f(N)=N”的最大的N是多少?
:.
写书评,赢取《编程之美--微软技术面试心得》
分析与解法
【问题1的解法一】
这个问题看上去并不是一个困难的问题,因为不需要太多的
思考,我想大家都能找到一个最简单的方法来计算f(N),那就
是从1开始遍历到N,将其中每一个数中含有“1”的个数加起来,
自然就得到了从1到N所有“1”的个数的和。写成程序如下:
代码清单2-9
ULONGLONGCount1InAInteger(ULONGLONGn)
{
ULONGLONGiNum=0;
while(n!=0)
{
iNum+=(n%10==1)?1:0;
n/=10;
}
returniNum;
}
ULONGLONGf(ULONGLONGn)
{
ULONGLONGiCount=0;
for(ULONGLONGi=1;i<=n;i++)
{
iCount+=Count1InAInteger(i);
}
:.
写书评,赢取《编程之美--微软技术面试心得》
returniCount;
}
这个方法很简单,只要学过一点编程知识的人都能想到,实
现也很简单,容易理解。但是这个算法的致命问题是效率,它的
时间复杂度是
O(N)×计算一个整数数字里面“1”的个数的复杂度=O(N*
log2N)
如果给定的N比较大,则需要很长的运算时间才能得到计算
结果。比如在笔者的机器上,如果给定N=100000000,则算出f
(N)大概需要40秒的时间,计算时间会随着N的增大而线性增
长。
看起来要计算从1到N的数字中所有1的和,至少也得遍历
1到N之间所有的数字才能得到。那么能不能找到快一点的方法
来解决这个问题呢?要提高效率,必须摈弃这种遍历1到N所有
数字来计算f(N)的方法,而应采用另外的思路来解决这个问题。
【问题1的解法二】
仔细分析这个问题,给定了N,似乎就可以通过分析“小于N
的数在每一位上可能出现1的次数”之和来得到这个结果。让我们
来分析一下对于一个特定的N,如何得到一个规律来分析在每一
位上所有出现1的可能性,并求和得到最后的f(N)。
先从一些简单的情况开始观察,看看能不能总结出什么规律。
:.
写书评,赢取《编程之美--微软技术面试心得》
先看1位数的情况。
如果N=3,那么从1到3的所有数字:1、2、3,只有个位
数字上可能出现1,而且只出现1次,进一步可以发现如果N是
个位数,如果N>=1,那么f(N)都等于1,如果N=0,则f(N)
为0。
再看2位数的情况。
如果N=13,那么从1到13的所有数字:1、2、3、4、5、6、
7、8、9、10、11、12、13,个位和十位的数字上都可能有1,我
们可以将它们分开来考虑,个位出现1的次数有两次:1和11,
十位出现1的次数有4次:10、11、12和13,所以f(N)=2+4=6。
要注意的是11这个数字在十位和个位都出现了1,但是11恰好在
个位为1和十位为1中被计算了两次,所以不用特殊处理,是对
的。再考虑N=23的情况,它和N=13有点不同,十位出现1的次
数为10次,从10到19,个位出现1的次数为1、11和21,所以
f(N)=3+10=13。通过对两位数进行分析,我们发现,个位数出
现1的次数不仅和个位数字有关,还和十位数有关:如果N的个
位数大于等于1,则个位出现1的次数为十位数的数字加1;如果
N的个位数为0,则个位出现1的次数等于十位数的数字。而十位
数上出现1的次数不仅和十位数有关,还和个位数有关:如果十
位数字等于1,则十位数上出现1的次数为个位数的数字加1;如
果十位数大于1,则十位数上出现1的次数为10。
f(13)=个位出现1的个数+十位出现1的个数=2+4=6;
f(23)=个位出现1的个数+十位出现1的个数=3+10=13;
f(33)=个位出现1的个数+十位出现1的个数=4+10=14;
…
f(93)=个位出现1的个数+十位出现1的个数=10+10=
20;
接着分析3位数。
:.
写书评,赢取《编程之美--微软技术面试心得》
如果N=123:
个位出现1的个数为13:1,11,21,…,91,101,111,121
十位出现1的个数为20:10~19,110~119
百位出现1的个数为24:100~123
f(23)=个位出现1的个数+十位出现1的个数+百位出
现1的次数=13+20+24=57;
同理我们可以再分析4位数、5位数。读者朋友们可以写一写,
总结一下各种情况有什么不同。
根据上面的一些尝试,下面我们推导出一般情况下,从N得
到f(N)的计算方法:
假设N=abcde,这里a、b、c、d、e分别是十进制数N的各
个数位上的数字。如果要计算百位上出现1的次数,它将会受到
三个因素的影响:百位上的数字,百位以下(低位)的数字,百
位(更高位)以上的数字。
如果百位上的数字为0,则可以知道,百位上可能出现1的次
数由更高位决定,比如12013,则可以知道百位出现1的情况可能
是100~199,1100~1199,2100~2199,…,11100~11199,
一共有1200个。也就是由更高位数字(12)决定,并且等于更高
位数字(12)×当前位数(100)。
:.
写书评,赢取《编程之美--微软技术面试心得》
如果百位上的数字为1,则可以知道,百位上可能出现1的次
数不仅受更高位影响,还受低位影响,也就是由更高位和低位共同
决定。例如对于12113,受更高位影响,百位出现1的情况是100~
199,1100~1199,2100~2199,…,11100~11199,一共1200
个,和上面第一种情况一样,等于更高位数字(12)×当前位数(100)。
但是它还受低位影响,百位出现1的情况是12100~12113,一共
114个,等于低位数字(123)+1。
如果百位上数字大于1(即为2~9),则百位上可能出现1
的次数也仅由更高位决定,比如12213,则百位出现1的可能性
为:100~199,1100~1199,2100~2199,…,11100~11199,
12100~12199,一共有1300个,并且等于更高位数字+1(12+1)
×当前位数(100)。
通过上面的归纳和总结,我们可以写出如下的更高效算法来
计算f(N):
代码清单2-10
LONGLONGSum1s(ULONGLONGn)
{
ULONGLONGiCount=0;
ULONGLONGiFactor=1;
ULONGLONGiLowerNum=0;
ULONGLONGiCurrNum=0;
:.
写书评,赢取《编程之美--微软技术面试心得》
ULONGLONGiHigherNum=0;
while(n/iFactor!=0)
{
iLowerNum=n-(n/iFactor)*iFactor;
iCurrNum=(n/iFactor)%10;
iHigherNum=n/(iFactor*10);
switch(iCurrNum)
{
case0:
iCount+=iHigherNum*iFactor;
break;
case1:
iCount+=iHigherNum*iFactor+iLowerNum
+1;
break;
default:
iCount+=(iHigherNum+1)*iFactor;
break;
}
iFactor*=10;
}
returniCount;
}
这个方法只要分析N就可以得到f(N),避开了从1到N的
遍历,输入长度为Len的数字N的时间复杂度为O(Len),即为
O(ln(n)/ln(10)+1)。在笔者的计算机上,计算N=100000000,
:.
写书评,赢取《编程之美--微软技术面试心得》
相对于第一种方法的40秒时间,这种算法不到1毫秒就可以返回
结果,速度至少提高了40000倍。
:.
写书评,赢取《编程之美--微软技术面试心得》
【问题2的解法】
要确定最大的数N,满足f(N)=N。我们通过简单的分析可
以知道(仿照上面给出的方法来分析):
9以下为:1个;
99以下为:1×10+10×1=20个;
999以下为:1×100+10×20=300
个;
9999以下为:
1×1000+10×300=4000个;
…
999999999以下为:900000000
个;
9999999999以下为:**********
个。
n-1n-1
容易从上面的式子归纳出:f(10)=n*10。通过这个递
推式,很容易看到,当n=9时候,f(n)的开始值大于n,所以
我们可以猜想,当n大于某一个数N时,f(n)会始终比n大,
也就是说,最大满足条件在0~N之间,亦即N是最大满足条件f
(n)=n的一个上界。如果能估计出这个N,那么只要让n从N
往0递减,每个分别检查是否有f(n)=n,第一个满足条件的数
:.
写书评,赢取《编程之美--微软技术面试心得》
就是我们要求的整数。
因此,问题转化为如何证明上界N确实存在,并估计出这个
上界N。
证明满足条件f(n)=n的数存在一个上界
首先,用类似数学归纳法的思路来推理这个问题。很容易得
到下面这些结论(读者朋友可以自己试着列举验证一下):
当n增加10时,f(n)至少增加1;
当n增加100时,f(n)至少增加20;
当n增加1000时,f(n)至少增加300;
当n增加10000时,f(n)至少增加4000;
……
kk-1
当n增加10时,f(n)至少增加k*10。
k-1k
首先,当k>=10时,k*10>10,所以f(n)的增加量大于
n的增加量。
10-11010-1
其次,f(10)=10>10。如果存在N,当n=N时,f(N)
10-1
-N>10成立时,此时不管n增加多少,f(n)的值将始终大于n。
10-1
具体来说,设n的增加量为m:当m小于10时,由于f
10-110-1
(N)-N>10,因此有f(N+m)>f(N)>N+10>N+m,
10-1
即f(n)的值仍然比n的值大;当m大于等于10时,f(n)
:.
写书评,赢取《编程之美--微软技术面试心得》
的增量始终比n的增量大,即f(N+m)-f(N)>(N+m)-N,
10-1
也就是f(N+m)>f(N)+m>N+10+m>N+m,即f(n)
的值仍然比n的值大。
10-1
因此,对于满足f(N)-N>10成立的N一定是所求该数
的一个上界。
求出上界N
10-110-1K-1K-1
又由于f(10)=n*10,不妨设N=10,有f(10)
K-110-1K-1K-110-1
-(10)>10,即K*10-(10)>10,易得K>=11时
11-1
候均满足。所以,当K=11时,N=10即为最小一个上界。
计算这个最大数n
11-1
令N=10=99999999999,让n从N往0递减,每个分别检
查是否有f(n)=n,第一满足条件的就是我们要求的整数。很容
易解出n=1111111110是满足f(n)=n的最大整数。
扩展问题
对于其他进制表达方式,也可以试一试,看看有什么规律。
例如二进制:
f(1)=1
f(10)=10(因为01,10有两个1)
f(11)=100(因为01,10,11有四个1)
:.
写书评,赢取《编程之美--微软技术面试心得》
读者朋友可以模仿我们的分析方法,给出相应的解答。
:.