北京大学acm国际大学生程序设计竞赛2ppt课件

问题求解与程序设计 第二讲 对局问题,李文新 2004.2 2004.6,内容提要,上周作业总结 放硬币问题 取火柴问题 取石子问题 - n堆 取石子问题 1堆 作业 装箱问题,1005题,弗雷德先生想在路易斯安娜州买一块地造房子。在调查中他了解到由于密西西比河的侵蚀，路易斯安娜州正在以每年50平方英里的速度变小。因为弗雷德先生希望在他的新房子里生活直至终老，所以他想知道他的房子是否会被侵蚀掉。,1005题,经过进一步研究，弗雷德发现将要被侵蚀得陆地呈半圆形。半圆是一个以（0，0）点为中心的圆的一半，半圆的直边是X轴。X轴以下的部分在水中。在第一年的开始，圆的面积是0。（半圆如下图所示）。,1005 问题,1005 问题分析,1）分析问题寻求算法 因为河水呈半圆形扩散，每年扩散50平方英里，所以当给定一点的坐标时，可以用它与原点的距离作为半径，计算以此为半径的半圆的面积，在用这一面积除以50，向上取整，得到的就是要求的年数。即使用如下公式计算：,1005 源代码,#include /将输入输出的库函数包含 #include /将用到的库函数包含进来 void main() /程序开始 float x,y; /用来存放读入的坐标值 int year; /用于保存计算出来的年数 scanf(“%f %f”, /将算出来的年数输出到屏幕上 /程序结束,1006题,人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。,1006题,输入 输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252 。 输出 从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。,1006题,问题分析 令所求的时间为当年的第x天，则x具有如下性质： 1) 21252 = x d 2) (x-p)%23=0 3) (x-e)%28=0 4) (x-i)%33=0,1006题,一个最简单直观的做法就是枚举从d+1 到 21252 之间所有的数字，寻找第一个满足条件2）3）4）的数字，注意输出时间减去d.。,1006题,可以做的进一步改进是从d+1开始逐一枚举寻找满足条件2）的数字a，从a开始每步加23寻找满足条件2）3）的数字b，从b开始每步加23*28寻找满足条件2）3）4）的数字x。x就是我们要找的数字，输出时输出x-d。,1006题,程序设计 / 读入p, e, i, d / j从d+1 循环到21252， 如果 (j-p)%23=0，跳出循环 / j从上次跳出循环的值循环到21252， 如果 (j-e)%28=0，跳出循环 / j从上次跳出循环的值循环到21252， 如果 (j-i)%33=0，跳出循环 / 输出j-d,1006题,#include #include void main() int p,e,i,d,j,no=1; scanf(“%d %d %d %dn“, ,放硬币问题,在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？,放硬币问题,事实上，甲只要先在圆桌中心放下一枚硬币，此后无论乙怎么放，甲总在其关于中心对称处放一枚，最终甲必然获胜。,取火柴问题,一堆火柴有N根，A，B两人轮流取出。每次可以取1根或2根，问先取者能否有必胜策略？,取火柴问题,一般解答： 分情况讨论：N=3k 后手胜和 N！=3k 先手胜(k为正整数) 推广： 每次可以取1n根火柴(n为正整数，且1=nN) 则 N=k(n+1) 后手胜，N！=k(n+1)先手胜(k为正整数),取石子问题 n堆,甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下： 每一步应取走至少一枚石子； 每一步只能从某一堆中取走部分或全部石子； 如果谁无法按规则取子，谁就是输家。,取石子问题 n堆,图 1 游戏的一个初始局面,取石子问题 n堆,对于游戏A来说，任意的一个初始局面S=(a1, a2, , an)，我们把这里的ai都看成是二进制数。令#S=a1 a2 an。若#S0，则先行者（甲）有必胜策略；否则#S=0，这时后行者（乙）有必胜策略。,取石子问题 n堆,例如1：,取石子问题 n堆,1 1 1 0 1 1 0 1 1 - 1 1 1 先手必胜,取石子问题 n堆,例2： 第一排 1 01 第二排 2 10 第三排 3 11 - 00后手必胜,取石子问题 1堆,问 题 描 述 有N粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。 请问，甲能否获胜？（1 N 100）,取石子问题 1堆,用一个简单例子分析：假设有N = 4粒石子，则一开始甲最多能取3粒，用（4，3）来表示初始状态。,状态转移的拓扑结构,取石子问题 1堆,1如果一个状态没有子状态，是结局，则根据题目条件判定胜负,取石子问题 1堆,1如果一个状态至少有一个子状态是先手败，则该状态是先手胜,取石子问题 1堆,胜,败,1如果一个状态的所有子状态都是先手胜，则该状态是先手败,取石子问题 1堆,甲必败：,甲必胜：,2,3,4,5,6,7,8,取石子问题 1堆,Fibonacci 数列,取石子问题 1堆,猜 想： 设F为Fibonacci数列（F1=2，F2=3，FK=FK-1+FK-2） 初始时有N粒石子，若NF则先手必败，否则先手必胜。,取石子问题 1堆,性质1：若KN，则状态（N,K）先手必胜。,性质2：若状态（N,N-1）先手必败，则状态（N,K）K N 先手必败。,性质3：若状态（N,K）K N，则最后一次取走的石子数目不超过2N/3。,取石子问题 1堆,结论1：状态(Fi，A） A Fi 先手必败。,证 明：,（一）F1(=2)，F2(=3)时，显然成立。,（二）若F1至Fi成立，则Fi+1成立。,设先手取K粒石子。,（1）若KFi-1 后手得状态(N-K,2K),2K2Fi-1Fi-1+Fi-2= Fi N-K 由性质1，后手获胜。,后手获胜，先手败,取石子问题,证 明：,（2）若K Fi-1,根据假设（Fi-1,K）K Fi-1 必败，所以后手可以使先手面临(Fi，X)状态。,由性质3： X2Fi-1/3 2 = 4Fi-1/3 Fi-1+ Fi-1