ACM入门教程-数学问题.ppt

1、ACM 程序设计竞赛入门,浙江工业大学 田贤忠 ,2020/8/10,1,2020/8/10,2,第二讲,数学问题,2020/8/10,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 number, yo

2、u have to determine the number of digits in the factorial of the number.,2020/8/10,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 cont

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

4、,7,如果不知道高效的计算公式？,(int)(log10(1)+log10(2)+log10(3)+log10(n) 对于每个输入的数都要按上述公式计算 如何避免重复计算？ 先算小数的位数，在此基础上再算大数。 （1） 每次找最小值？需要存储数据和位数的计算 （2）先把算出的log10存储？,2020/8/10,8,计算机程序设计艺术中给出了另一个公式 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/

5、(288*n*n) + O(1/n3) log10(1) = 0 得到公式 log10(n!) = log10(sqrt(2 * pi * n) + n * log10(n / e),2020/8/10,9,数学问题的特点：,题意容易理解； 数学关联性一般比较大； 语言的关联性相对较小；但有时需要相关策略来规避过高的复杂度。 要注意复杂度问题； 适合ACM/ICPC入门练习。 每次竞赛一般会有1-2个数学问题。,2020/8/10,10,常用单词： 1、integer 整数（不一定就是32位的） 2、positive 正的 3、negative (adj)负的; (n)负数 4、factori

6、al (n)阶乘; (adj)因子的，阶乘的 5、digital (n)数字; (adj)数字的 6、multiple 倍数 7、multiplication 乘法运算,2020/8/10,11,常用单词： （ 图形相关） 1、vertex ( vertices ) 顶点 2、polygon 多边形 3、convex 凸的 4、concave 凹的 5、segment (线)段（n）;分割（v）,2020/8/10,12,数学问题（分类分析）,2020/8/10,13,第一类,简单问题,HDOJ1004: Let the Balloon Rise,HDOJ1004: Let the Ballo

7、on Rise,题目描述： 输入： 第一行输入气球的个数n，以下n行输入n个气球的颜色，n为0时结束。 输出： 哪种颜色的气球数目最多,2020/8/10,15,HDOJ1004: Let the Balloon Rise,Sample Input 5 green red blue red red 3 pink orange pink 0,Sample output red pink,2020/8/10,16,2020/8/10,17,题目评述：,1. 一个让你看到后兴奋的题目,2. 只要懂点C或者C+，就可解决该问题。,2020/8/10,18,1004题目分析：,该题算法思想比较简单，就是

8、对输入的字符串进行比较和统计。值得注意的一点是： 如果用C语言来写，要注意可能会把第一个数字后的“回车符”误认为是第一个串，字符串的比较也要用函数和循环语句。 而C+则在处理字符串方面较为方便。,2020/8/10,19,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 elevator will

9、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 is on the 0th fl

10、oor at the beginning and does not have to return to the ground floor when the requests are fulfilled.,2020/8/10,20,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 with N = 0 deno

11、tes 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 0Sample Output 17 41,const int UP = 6; const int DOWN = 4; const int STOP = 5; int nCase,floor; while(cin nCase ,2020/8/10,21,2020/8/10,22,第二类 大数问题,20

12、20/8/10,23,一、大数加法 HDU1002： A + B Problem II,Input The first line of the input contains an integer T(1=T=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them

13、 by using 32-bit integer. You may assume the length of each integer will not exceed 1000.,2020/8/10,24,分析：,准确的说，此问题不算是数学问题； 由于数据特别大，用一般的整数类型不能存储，怎么办？ 字符串存储？ 怎么处理？按位加，进位？,2020/8/10,25,字符如何相加 ？(从最低位开始相加） 不等长怎么办？ 发生进位怎么办？,本校OJ1217大数乘,时空限定 5S，32M 基本描述 给定一些大数，请计算其积。 输入描述 输入数据中含有一些整数对（对数1000），若某对整数（整数位数20

14、0）的值为0 0，则表示输入结束。 输出描述 每对整数对应一个乘法计算结果，输出该结果，每个结果输出完后应回车。,样本输入 2 3 12 34 0 0 样本输出 6 276,A大数乘,分析： 存放： string 考虑 正负性， 位数（可能会超过200位很多）。 正负性 可以通过判断两个数的正负性来解决， 做乘法的数字运算时，应先将负号去掉。 注意： 倒序,string multi(const string ,A大数乘,调用： for(string a,b; cinab ,2020/8/10,30,第三类 注重分析的问题,2020/8/10,31,先看一个简单的题目:,2020/8/10,32

15、,1331：取石子问题,Description: 小明是个游戏迷，这不，今天他又和小刚一起玩“拿石子”的游戏。游戏规则是2个人轮流拿石子，一次可以拿1颗或3颗，规定谁取到最后一颗石子就是谁赢。小明和小刚商量后决定每次都是小明先取。小明与小刚都是游戏高手，该赢的局绝不会输。在知道石子总数的情况下，小明想快速知道每次的输赢情况。,2020/8/10,33,分析：,各取一次共有三种情况： 共取走2颗石子 共取走4颗石子 共取走6颗石子 设有石子S.方案取了N1次，方案取了N2次，方案取了N3次后，还剩下K个石子。 S=2*N1+4*N2+6*N3+K K的取值有三种情况：0，1，3。 K=1,3则先

16、取方胜。反之，另一方胜。 当S为偶数时，后取方胜，反之，先取方胜。,2020/8/10,34,杭电OJ：1021 Fibonacci Again,Problem Description There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n=2). Input ：Input consists of a sequence of lines, each containing an integer n. (n 1,000,000). Output：Print the wor

17、d 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/8/10,35,题目分析：,判断某一项是否能被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项

18、除以3余2，第7项整除.,2020/8/10,36,Hdoj_1021程序清单：,#include int main() long n; while(scanf(%ld, ,2020/8/10,37,这个问题主要在于找出规律； 程序编写很简单； 考查的是分析问题的能力。,2020/8/10,38,第四类 公式型,HDOJ_1071 The Area,2020/8/10,40,抛物线公式：y=ax2+bx+c,已知三点 -a、b、c 系数,公式已知 - 如何求面积？,积分问题 ,2020/8/10,41,递推求解,还记得Fibonacci问题吧？ F(0)=F(1)=1; F(n)=F(n-1)

19、+F(n-2);,2020/8/10,42,1182：母牛问题,Description: 假设单性繁殖成立，若一头母牛，从出生起第四个年头开始，每年生一头母牛，而生出的小母牛在之后的第四年也将具有生殖能力。按此规律，第n年时有多少头母牛？ Input: 输入数据中不多于50个整数（1n40）。 Output:对于每个n，输出其第n年的母牛数，每个结果对应一行输出。,2020/8/10,43,如何得出递推公式？,列出前面几个数据： 1 1 1 2 3 4 6 假设规模小于N的情况已经得到解决 重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。

20、f(n）=f(n-1)+f(n-3) (n-3年存在的牛在n年均可以生出一头小牛）,2020/8/10,44,再来看难一点的问题,2020/8/10,45,2050：折线分割平面,2020/8/10,46,这个问题其实属于递推问题，你们比我更擅长，呵呵,2020/8/10,47,先看直线分割平面问题,经典结论：平面内有n条直线，任何两条不平行，任何三条不过同一点；这n条直线可以把平面分成 n(n+1) /2 +1个部分。 可用数学归纳法证明。,2020/8/10,48,公式的推导,F(1)=2; F(n) = F(n-1)+n; (第n条直线与n-1条相交，将增加n个区域） F(n)=n+n-

21、1+n-2+.+2+f(1) =n(n+1)/2+1,2020/8/10,49,回到折线问题：,一个折线可以看成两条直线相交，并去掉角的一边 ；可推出公式： f(n)=f(n-1)+(2n-1) +2n-2,2020/8/10,50,f(n)=f(n-1)+(2n-1) +2n-2 f(1)=2 F(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*n2-n+1 注意：两直线直接带入公式： n(n+1) /2 +1,2020/8/10,51,Ok

22、, 内容已经不少了来几个思考题,2020/8/10,52,思考（1） HDOJ 1465: 不容易系列之一(递推求解),某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。,分析,总和就是 (n-1)*(f(n-1)+f(n-2),2020/8/10,53,#includeint main()int n;_int64 i,a21=0; a2=1;a3=2;for(i=4;i=20;i+)ai=(i-1)*(ai-1+ai-2);while(scanf(%d, ,2020/8/10,54,2020/8/10,55,思考（2）HDOJ1030: Delta

23、-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

24、program to determine the length of the shortest route connecting cells with numbers N and M.,题目大意：,Input Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s). Output Output should contain the length of the shortest route. Sample Input 6 12 Sample Output 3,分析：,2020/8/10,57,分析：,1.每一行数的数目为 2n-1 (一定为奇数), n=1,2,3. 2.每一行的数的范围(n-1)2+1 , n2 3.奇数行中以奇数开头，奇数结尾偶数行中以偶数开头，偶数结尾 4.第n行中与下一行的连接数为n，第一个有，第二个没有.最后一个有 5.在奇数行中，数字为奇数则可到达下一行，为偶数则不行,2020/8/10,58,分析：,M，N分两种情况，先保证MN 1.M和N在同一行,则直接Step