ACM入门教程(2-数学问题)

2024/5/81ACM程序竞赛入门

开课号：85019

授课教师：王英姿2024/5/82第二讲数学问题2024/5/83引例：本校OJ1207

〔相似题〕杭电1018，求n！的位数

Inmanyapplicationsverylargeintegersnumbersarerequired.Someoftheseapplicationsareusingkeysforsecuretransmissionofdata,encryption,etc.Inthisproblemyouaregivenanumber,youhavetodeterminethenumberofdigitsinthefactorialofthenumber.

2024/5/84InputInputconsistsofseverallinesofintegernumbers.Thefirstlinecontainsanintegern,whichisthenumberofcasestobetested,followedbynlines,oneinteger1≤m≤107oneachlineOutputTheoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput.SampleInput21020SampleOutput7192024/5/85如何求位数？算出阶乘，循环求位数？阶乘怎么存储？一定要算出阶乘吗？

n!的位数：

(int)log10(n!)+1(int)(log10(1)+log10(2)+log10(3)+…+log10(n))+12024/5/86代码怎么写？超时问题怎么解决？能不能降低计算量？有没有更简便的公式？2024/5/87《计算机程序设计艺术》中给出了另一个公式

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)2024/5/88如果不知道高效的计算公式？(int)(log10(1)+log10(2)+log10(3)+…+log10(n))对于每个输入的数都要按上述公式计算如何防止重复计算？先算小数的位数，在此根底上再算大数。〔1〕每次找最小值？需要存储数据和位数的计算〔2〕先把算出的log10存储？2024/5/89数学问题的特点：题意容易理解；数学关联性一般比较大；语言的关联性相对较小；但有时需要相关策略来躲避过高的复杂度。要注意复杂度问题；适合ACM/ICPC入门练习。每次竞赛一般会有1-2个数学问题。2024/5/810常用单词：1、integer整数〔不一定就是32位的〕2、positive正的3、negative(adj)负的;(n)负数4、factorial(n)阶乘;(adj)因子的，阶乘的5、digital(n)数字;(adj)数字的6、multiple倍数7、multiplication乘法运算2024/5/811常用单词：〔图形相关〕1、vertex(vertices)顶点2、polygon多边形3、convex凸的4、concave凹的5、segment(线)段〔n〕;分割〔v〕2024/5/812数学问题

〔分类分析〕2024/5/813第一类简单问题2024/5/8141288电梯

不管在什么事情上，总是想方设法给自己带来方便。于是在一幢古老楼房的电梯里就发生了争吵事件。大家都想在自己住的这一层停下〔因为电梯在上升的过程中只能停下一次，之后就只能返回到地下车库了〕。争吵给保安带来了麻烦，所以保安想请你编个程序。当人们每次进入电梯，统计一下人数，再统计一下到每层的人数就计算出电梯到哪一层停最合理〔当人从高往低走时，走一层要花3点力量，而从低往高走时，走一层要花4点力量，当所有人们花的力量总和最小时，停那一层就是最合理的〕。2024/5/815Input:每行的第一个数是n〔1<=n<=50〕，表示这幢楼有几层，接下来有n个数，分别表示1到n层各层的人数。到各层的人数不超过100个。大家都是从地下车库坐电梯上来的。当n为0，那么结束。Output:每行输出最合理的那一层，当有好几层都是合理的，那就都输出来，并且每个数据之间空一格。SampleInput:31115668210SampleOutput:232024/5/816Elevator

ProblemDescriptionThehighestbuildinginourcityhasonlyoneelevator.ArequestlistismadeupwithNpositivenumbers.Thenumbersdenoteatwhichfloorstheelevatorwillstop,inspecifiedorder.Itcosts6secondstomovetheelevatoruponefloor,and4secondstomovedownonefloor.Theelevatorwillstayfor5secondsateachstop.

Foragivenrequestlist,youaretocomputethetotaltimespenttofulfilltherequestsonthelist.Theelevatorisonthe0thflooratthebeginninganddoesnothavetoreturntothegroundfloorwhentherequestsarefulfilled.

2024/5/817InputTherearemultipletestcases.EachcasecontainsapositiveintegerN,followedbyNpositivenumbers.Allthenumbersintheinputarelessthan100.AtestcasewithN=0denotestheendofinput.Thistestcaseisnottobeprocessed.

OutputPrintthetotaltimeonasinglelineforeachtestcase.

SampleInput1232310

SampleOutput17412024/5/818第二类

大数问题2024/5/819一、大数加法HDU1002：

A+BProblemIIInputThefirstlineoftheinputcontainsanintegerT(1<=T<=20)whichmeansthenumberoftestcases.ThenTlinesfollow,eachlineconsistsoftwopositiveintegers,AandB.Noticethattheintegersareverylarge,thatmeansyoushouldnotprocessthembyusing32-bitinteger.Youmayassumethelengthofeachintegerwillnotexceed1000.

2024/5/820分析：准确的说，此问题不算是数学问题；由于数据特别大，用一般的整数类型不能存储，怎么办？字符串存储？怎么处理？按位加，进位？2024/5/821‘1’‘2’‘3’…‘5’‘6’‘7’‘8’‘\0’‘2’‘3’‘5’‘6’‘7’‘8’‘\0’…..‘3’‘5’‘6’‘\0’字符如何相加？(从最低位开始相加〕不等长怎么办？发生进位怎么办？2024/5/822第三类

注重分析的问题2024/5/823先看一个简单的题目:2024/5/8241331：取石子问题

Description:小明是个游戏迷，这不，今天他又和小刚一起玩“拿石子”的游戏。游戏规那么是2个人轮流拿石子，一次可以拿1颗或3颗，规定谁取到最后一颗石子就是谁赢。小明和小刚商量后决定每次都是小明先取。小明与小刚都是游戏高手，该赢的局绝不会输。在知道石子总数的情况下，小明想快速知道每次的输赢情况。2024/5/825分析：各取一次共有三种情况：

①共取走2颗石子

②共取走4颗石子

③共取走6颗石子设有石子S.方案①取了N1次，方案②取了N2次，方案③取了N3次后，还剩下K个石子。S=2*N1+4*N2+6*N3+KK的取值有三种情况：0，1，3。K=1,3那么先取方胜。反之，另一方胜。当S为偶数时，后取方胜，反之，先取方胜。

2024/5/826杭电OJ：1021FibonacciAgainProblemDescriptionThereareanotherkindofFibonaccinumbers:F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2)(n>=2).Input：Inputconsistsofasequenceoflines,eachcontaininganintegern.(n<1,000,000).Output：Printtheword"yes"if3divideevenlyintoF(n).

Printtheword"no"ifnot.

SampleInput012345SampleOutputnonoyesnonono2024/5/827题目分析：判断某一项为哪一项否能被3整除是否需要把某一项的值求出来，进行整除判断？能被3整除的整数的特点？关于能否被3整除，这样的项在排列上是否有规律？〔找出规律〕第0项除以3余1，第1项除以3余2，第2项整除，第3项除以3余2，第4项除以3余2，第5项除以3余1，第6项整除，第7项除以3余1，第8项除以3余1，第9项除以3余2，第7项整除…….2024/5/828Hdoj_1021程序清单：#include<stdio.h>intmain(){longn;while(scanf("%ld",&n)!=EOF) if(n%8==2||n%8==6) printf("yes\n"); else printf("no\n"); return0;}2024/5/829这个问题主要在于找出规律；程序编写很简单；考查的是分析问题的能力。2024/5/830第四类

公式型HDOJ_1071TheArea

2024/5/832抛物线公式：y=ax^2+bx+c三点-〉a、b、c系数公式-〉如何求面积？积分问题

2024/5/833递推求解……还记得Fibonacci问题吧？F(0)=F(1)=1;F(n)=F(n-1)+F(n-2);2024/5/8341182：母牛问题

Description:假设单性繁殖成立，假设一头母牛，从出生起第四个年头开始，每年生一头母牛，而生出的小母牛在之后的第四年也将具有生殖能力。按此规律，第n年时有多少头母牛？Input:输入数据中不多于50个整数〔1≤n≤40〕。Output:对于每个n，输出其第n年的母牛数，每个结果对应一行输出。2024/5/835如何得出递推公式？列出前面几个数据：1112346假设规模小于N的情况已经得到解决重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。f(n〕=f(n-1)+f(n-3)(n-3年存在的牛在n年均可以生出一头小牛〕2024/5/836再来看难一点的问题……2024/5/8372050：折线分割平面

2024/5/838

这个问题……

其实属于递推问题，

你们比我更擅长，呵呵……2024/5/839先看直线分割平面问题经典结论：平面内有n条直线，任何两条不平行，任何三条不过同一点；这n条直线可以把平面分成n(n+1)/2+1个局部。可用数学归纳法证明。2024/5/840公式的推导……F(1)=2;F(n)=F(n-1)+n;(第n条直线与n-1条相交，将增加n个区域〕F(n)=n+n-1+n-2+….+2+f(1)=n(n+1)/2+12024/5/841回到折线问题：一个折线可以看成两条直线相交，并去掉角的一边；可推出公式：

f(n)=f(n-1)+(2n-1)+2n-22024/5/842f(n)=f(n-1)+(2n-1)+2n-2f(1)=2F(n)=2n+2n-1+2n-2+2n-3+…..+4+3-2*(n-1)+f(1)=2n-1+2n-2+…..+4+3+2+1+1=2n*(2n-1)/2+1=2n(n-1)+1=2*n^2-n+12024/5/843Ok,内容已经不少了……

来几个思考题……2024/5/844思考(1)：1358

虽然题目采用故事性描述本质上就是求相交圆的面积纯数学问题别问我，这类问题我不擅长…..

2024/5/845思考〔2〕

HDOJ1465:不容易系列之一(递推求解)某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。2024/5/846思考〔3〕HDOJ1030:Delta-wave

ThetravellerneedstogofromthecellwithnumberMtothecellwithnumberN.Thetravellerisabletoenterthecellthroughcelledgesonly,hecannottravelfromcelltocellthroughvertices.Thenumbe