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

* * * 先看一个简单的题目: * * 1331：取石子问题/ProblemList.aspx Description: 小明是个游戏迷，这不，今天他又和小刚一起玩“拿石子”的游戏。游戏规则是2个人轮流拿石子，一次可以拿1颗或3颗，规定谁取到最后一颗石子就是谁赢。小明和小刚商量后决定每次都是小明先取。小明与小刚都是游戏高手，该赢的局绝不会输。在知道石子总数的情况下，小明想快速知道每次的输赢情况。 * * 分析： 各取一次共有三种情况： ①共取走2颗石子 ②共取走4颗石子 ③共取走6颗石子 设有石子S.方案①取了N1次，方案②取了N2次，方案③取了N3次后，还剩下K个石子。 S=2*N1+4*N2+6*N3+K K的取值有三种情况：0，1，3。 K=1,3则先取方胜。反之，另一方胜。 当S为偶数时，后取方胜，反之，先取方胜。  * * 杭电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 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 * * 题目分析： 判断某一项是否能被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项整除……. * * Hdoj_1021程序清单： #includestdio.h int main() { long n; while(scanf(%ld,n) != EOF) if (n%8==2 || n%8==6) printf(yes\n); else printf(no\n); return 0; } * * 这个问题主要在于找出规律； 程序编写很简单； 考查的是分析问题的能力。 * * 第四类 公式型 HDOJ_1071 The Area * * 抛物线公式：y=ax^2+bx+c 已知三点 -〉a、b、c 系数 公式已知 - 〉如何求面积？ 积分问题 ? * * 递推求解…… 还记得Fibonacci问题吧？ F(0)=F(1)=1; F(n)=F(n-1)+F(n-2); * * 1182：母牛问题/ShowProblem.aspx?ShowID=1182 Description: 假设单性繁殖成立，若一头母牛，从出生起第四个年头开始，每年生一头母牛，而生出的小母牛在之后的第四年也将具有生殖能力。按此规律，第n年时有多少头母牛？ Input: 输入数据中不多于50个整数（1≤n≤40）。 Output:对于每个n，输出其第n年的母牛数，每个结果对应一行输出。 * * 如何得出递推公式？ 列出前面几个数据： 1 1 1 2 3 4 6 假设规模小于N的情况已经得到解决 重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。 f(n）=f(n-1)+f(n-3) (n-3年存在的牛在n年均可以生出一头小牛） * * 再来看难一点的问题…… * * 2050：折线分割平面/showproblem.php?pid=2050 * * 这个问题……其实属于递推问题，你们比我更擅长，呵呵…… * * 先看直线分割平面问题 经典结论：平面内有n条直线，任何两条不平行，任何三条不过同一点；这n条直线可以把平面分成 n(n+1) /2 +1个部分。 可用数学归纳法证明。 * * 公式的推导…… F(1)=2;