1 / 13
文档名称:

1的数目.pdf

格式:pdf   大小:257KB   页数:13页
下载后只包含 1 个 PDF 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

1的数目.pdf

上传人:和合 2023/3/25 文件大小:257 KB

下载得到文件列表

1的数目.pdf

相关文档

文档介绍

文档介绍:该【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)
:.
写书评,赢取《编程之美--微软技术面试心得》
读者朋友可以模仿我们的分析方法,给出相应的解答。
:.

最近更新

全球十大最常用语言 7页

公司财务工作业绩总结6篇 15页

从认知角度看旅游文化的翻译的任务书 1页

创业计划书模板(完整版) 6页

从目的论视角探析广西壮族民俗汉英翻译的中期.. 2页

动物性食品卫生学答案 7页

胃十二直肠疾病 30页

印刷制作工艺 25页

医院疫情防控应急预案 15页

布线作业安全操作规程 27页

合肥市城市近期商业网点专项规划 16页

四川省广安市岳池县2022-2023学年九年级上学期.. 8页

人行重庆营业管理部货币物流业务流程再造的中.. 2页

人的视觉运动知识的认知神经机制的中期报告 1页

学习管理英语3的心得体会 7页

肿瘤基因治疗的新进展 20页

小学经费使用情况自查报告(小学体育经费支出情.. 9页

人力资本与经济增长的关系研究——以浙江省为.. 2页

工程地质的个人实习报告3篇 12页

京津风沙源治理工程评价系统的研建——社会经.. 2页

产柚苷酶高产菌株的筛选、鉴定及产酶特性研究.. 1页

产品材料工艺定额系统开发的任务书 2页

教师培训总结范文500字(通用20篇) 17页

新人教版九年级上册语文课外古诗词理解性默写.. 11页

安全监察科科长安全生产责任制 25页

最新部编人教版小学语文四年级上册作业本语文.. 7页

江苏省昆山、太仓市2020学年八年级道德与法治.. 8页

井下油水分离同井注采工艺技术可行性研究的任.. 2页

安全生产管理实施细则 28页

物业电工年终工作总结10篇 31页