ACM入门教程(2 数学问题)ppt课件.ppt

1、2020/6/24,1,ACM 程序竞赛入门 开课号：85019 授课教师：王英姿,2020/6/24,2,第二讲,数学问题,2020/6/24,3,引例：本校OJ 1207 （相似题）杭电1018，求n！的位数 ,In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a numbe

2、r, you have to determine the number of digits in the factorial of the number.,2020/6/24,4,Input Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 m 107 on each line Output The output

3、 contains the number of digits in the factorial of the integers appearing in the input.,Sample Input 2 10 20,Sample Output 7 19,2020/6/24,5,如何求位数？,算出阶乘，循环求位数？ 阶乘怎么存储？ 一定要算出阶乘吗？ n!的位数： (int) log10(n!)+1 (int)(log10(1)+log10(2)+log10(3)+log10(n)+1,2020/6/24,6,代码怎么写？ 超时问题怎么解决？ 能不能降低计算量？ 有没有更简便的公式？,2020

4、/6/24,7,计算机程序设计艺术中给出了另一个公式 n! = sqrt(2*n) * (n/e)n) * (1 + 1/(12*n) + 1/(288*n*n) + O(1/n3) = acos(-1) e = exp(1) 两边对10取对数 忽略 log10(1 + 1/(12*n) + 1/(288*n*n) + O(1/n3) log10(1) = 0 得到公式 log10(n!) = log10(sqrt(2 * pi * n) + n * log10(n / e),2020/6/24,8,如果不知道高效的计算公式？,(int)(log10(1)+log10(2)+log10(3)+

5、log10(n) 对于每个输入的数都要按上述公式计算 如何避免重复计算？ 先算小数的位数，在此基础上再算大数。 （1） 每次找最小值？需要存储数据和位数的计算 （2）先把算出的log10存储？,2020/6/24,9,数学问题的特点：,题意容易理解； 数学关联性一般比较大； 语言的关联性相对较小；但有时需要相关策略来规避过高的复杂度。 要注意复杂度问题； 适合ACM/ICPC入门练习。 每次竞赛一般会有1-2个数学问题。,2020/6/24,10,常用单词： 1、integer 整数（不一定就是32位的） 2、positive 正的 3、negative (adj)负的; (n)负数 4、fa

6、ctorial (n)阶乘; (adj)因子的，阶乘的 5、digital (n)数字; (adj)数字的 6、multiple 倍数 7、multiplication 乘法运算,2020/6/24,11,常用单词： （ 图形相关） 1、vertex ( vertices ) 顶点 2、polygon 多边形 3、convex 凸的 4、concave 凹的 5、segment (线)段（n）;分割（v）,2020/6/24,12,数学问题 （分类分析）,2020/6/24,13,第一类,简单问题,2020/6/24,14,1288 电梯 ,不管在什么事情上，总是想方设法给自己带来方便。于是在

7、一幢古老楼房的电梯里就发生了争吵事件。大家都想在自己住的这一层停下（因为电梯在上升的过程中只能停下一次，之后就只能返回到地下车库了）。争吵给保安带来了麻烦，所以保安想请你编个程序。当人们每次进入电梯，统计一下人数，再统计一下到每层的人数就计算出电梯到哪一层停最合理（当人从高往低走时，走一层要花3点力量，而从低往高走时，走一层要花4点力量，当所有人们花的力量总和最小时，停那一层就是最合理的）。,2020/6/24,15,Input:每行的第一个数是n（1=n=50），表示这幢楼有几层，接下来有n个数，分别表示1到n层各层的人数。到各层的人数不超过100个。大家都是从地下车库坐电梯上来的。当n为0

8、，则结束。 Output:每行输出最合理的那一层，当有好几层都是合理的，那就都输出来，并且每个数据之间空一格。,Sample Input: 3 1 1 1 5 6 6 8 2 1 0,Sample Output: 2 3,2020/6/24,16,Elevator ,Problem Description The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the

9、elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop. For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator i

10、s on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.,2020/6/24,17,Input There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case

11、with N = 0 denotes the end of input. This test case is not to be processed. Output Print the total time on a single line for each test case. Sample Input 1 2 3 2 3 1 0 Sample Output 17 41,2020/6/24,18,第二类 大数问题,2020/6/24,19,一、大数加法 HDU1002： A + B Problem II,Input The first line of the input contains a

12、n integer T(1=T=2). Input ：Input consists of a sequence of lines, each containing an integer n. (n 1,000,000). Output：Print the word yes if 3 divide evenly into F(n). Print the word no if not.,Sample Input 0 1 2 3 4 5,Sample Output no no yes no no no,2020/6/24,27,题目分析：,判断某一项是否能被3 整除 是否需要把某一项的值求出来，进行

13、整除判断？ 能被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项整除.,2020/6/24,28,Hdoj_1021程序清单：,#include int main() long n; while(scanf(%ld, ,2020/6/24,29,这个问题主要在于找出规律； 程序编写很简单； 考查的是分析问题的能力。,2020/6/24,30,第四类 公式型,HDOJ_1071 Th

14、e Area,31,2020/6/24,32,抛物线公式：y=ax2+bx+c,已知三点 -a、b、c 系数,公式已知 - 如何求面积？,积分问题 ,2020/6/24,33,递推求解,还记得Fibonacci问题吧？ F(0)=F(1)=1; F(n)=F(n-1)+F(n-2);,2020/6/24,34,1182：母牛问题 ,Description: 假设单性繁殖成立，若一头母牛，从出生起第四个年头开始，每年生一头母牛，而生出的小母牛在之后的第四年也将具有生殖能力。按此规律，第n年时有多少头母牛？ Input: 输入数据中不多于50个整数（1n40）。 Output:对于每个n，输出其第

15、n年的母牛数，每个结果对应一行输出。,2020/6/24,35,如何得出递推公式？,列出前面几个数据： 1 1 1 2 3 4 6 假设规模小于N的情况已经得到解决 重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。 f(n）=f(n-1)+f(n-3) (n-3年存在的牛在n年均可以生出一头小牛）,2020/6/24,36,再来看难一点的问题,2020/6/24,37,2050：折线分割平面 ,2020/6/24,38,这个问题 其实属于递推问题， 你们比我更擅长，呵呵,2020/6/24,39,先看直线分割平面问题,经典结论：平面内有n条

16、直线，任何两条不平行，任何三条不过同一点；这n条直线可以把平面分成 n(n+1) /2 +1个部分。 可用数学归纳法证明。,2020/6/24,40,公式的推导,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+1,2020/6/24,41,回到折线问题：,一个折线可以看成两条直线相交，并去掉角的一边 ；可推出公式： f(n)=f(n-1)+(2n-1) +2n-2,2020/6/24,42,f(n)=f(n-1)+(2n-1) +2n-2 f(1)=2 F(n) = 2n+2n-

17、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*n2-n+1,2020/6/24,43,Ok, 内容已经不少了 来几个思考题,2020/6/24,44,思考(1)：1358 ,虽然题目采用故事性描述 本质上就是求相交圆的面积 纯数学问题,别问我，这类问题我不擅长.,2020/6/24,45,思考（2） HDOJ 1465: 不容易系列之一(递推求解),某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。,2020/6/24,

18、46,思考（3）HDOJ1030: Delta-wave ,The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the travellers route. Write the program to determine the length o