ACM入门教程-数学问题

《ACM入门教程-数学问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计竞赛入门浙江工业大学田贤忠txz@zjut.edu.cn2021/10/712021/10/72第二讲数学问题2021/10/73引例：本校OJ1207http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1207（相似题）杭电1018，求n！的位数http://acm.hdu.edu.cn/showproblem.php?pid=1018Inmanyapplicationsverylargeintegersnumbersarerequired.

2、Someoftheseapplicationsareusingkeysforsecuretransmissionofdata,encryption,etc.Inthisproblemyouaregivenanumber,youhavetodeterminethenumberofdigitsinthefactorialofthenumber.2021/10/74InputInputconsistsofseverallinesofintegernumbers.Thefirstlinecontainsan

3、integern,whichisthenumberofcasestobetested,followedbynlines,oneinteger1≤m≤107oneachlineOutputTheoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput.SampleInput21020SampleOutput7192021/10/75如何求位数？算出阶乘，循环求位数？阶乘怎么存储？一定要算出阶乘吗？n!的位

4、数：(int)log10(n!)+1(int)(log10(1)+log10(2)+log10(3)+…+log10(n))+12021/10/76代码怎么写？超时问题怎么解决？能不能降低计算量？有没有更简便的公式？2021/10/77如果不知道高效的计算公式？(int)(log10(1)+log10(2)+log10(3)+…+log10(n))对于每个输入的数都要按上述公式计算如何避免重复计算？先算小数的位数，在此基础上再算大数。（1）每次找最小值？需要存储数据和位数的计算（2）先把算出的log

5、10存储？2021/10/78《计算机程序设计艺术》中给出了另一个公式n!=sqrt(2*π*n)*((n/e)^n)*(1+1/(12*n)+1/(288*n*n)+O(1/n^3))π=acos(-1)e=exp(1)两边对10取对数忽略log10(1+1/(12*n)+1/(288*n*n)+O(1/n^3))≈log10(1)=0得到公式log10(n!)=log10(sqrt(2*pi*n))+n*log10(n/e)2021/10/79数学问题的特点：题意容易理解；数学关联性一般比较大；

6、语言的关联性相对较小；但有时需要相关策略来规避过高的复杂度。要注意复杂度问题；适合ACM/ICPC入门练习。每次竞赛一般会有1-2个数学问题。2021/10/710常用单词：1、integer整数（不一定就是32位的）2、positive正的3、negative(adj)负的;(n)负数4、factorial(n)阶乘;(adj)因子的，阶乘的5、digital(n)数字;(adj)数字的6、multiple倍数7、multiplication乘法运算2021/10/711常用单词：（图形相关）1、

7、vertex(vertices)顶点2、polygon多边形3、convex凸的4、concave凹的5、segment(线)段（n）;分割（v）2021/10/712数学问题（分类分析）2021/10/713第一类简单问题HDOJ1004:LettheBalloonRiseHDOJ1004:LettheBalloonRise题目描述：输入：第一行输入气球的个数n，以下n行输入n个气球的颜色，n为0时结束。输出：哪种颜色的气球数目最多2021/10/715HDOJ1004:LettheBalloo

8、nRiseSampleInput5greenredblueredred3pinkorangepink0Sampleoutputredpink2021/10/7162021/10/717题目评述：1.一个让你看到后兴奋的题目…2.只要懂点C或者C++，就可解决该问题。2021/10/7181004题目分析：该题算法思想比较简单，就是对输入的字符串进行比较和统计。值得注意的一点是：如果用C语言来写，要注意可能会把第一个数字后的“回车符”误认为是第一个串，字符串的比较也要用