pkuACM课件2章节幻灯片.pptVIP

取石子问题– 1堆 猜 想： 设{F}为Fibonacci数列（F1=2，F2=3，FK=FK-1+FK-2） 初始时有N粒石子，若N∈{F}则先手必败，否则先手必胜。 取石子问题– 1堆 性质1：若K≥N，则状态（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)时，显然成立。 Fi-1 Fi Fi+1 （二）若F1至Fi成立，则Fi+1成立。 设先手取K粒石子。 （1）若K≥Fi-1 后手得状态(N-K,2K) 2K≥2Fi-1≥Fi-1+Fi-2= Fi N-K 由性质1，后手获胜。 后手获胜，先手败 K (N-K,2K) 取石子问题 证 明： Fi-1 Fi Fi+1 K （2）若K Fi-1 根据假设（Fi-1,K）K Fi-1 必败，所以后手可以使先手面临(Fi，X)状态。 (Fi,X) 由性质3： X≤2Fi-1/3 ×2 = 4Fi-1/3 ≤ Fi-1+ ? Fi-1 ≤ Fi-1+ Fi-2 ≤ Fi 因此(Fi,X)是必败 取石子问题 结论2：状态(N，N-1） N不属于{F}且N2，先手必胜。 F F’ N F’’ 平衡状态: Fibonacci数 决策规律: 找最大Fibonacci数 小结 上周作业总结 放硬币问题 取火柴问题 取石子问题 - n堆 取石子问题 – 1堆 作业 – 装箱问题 作业 1008 1013 问题求解与程序设计第二讲 对局问题 李文新 2004.2 – 2004.6 内容提要 上周作业总结 放硬币问题 取火柴问题 取石子问题 - n堆 取石子问题 – 1堆 作业 – 装箱问题 1005题 弗雷德先生想在路易斯安娜州买一块地造房子。在调查中他了解到由于密西西比河的侵蚀，路易斯安娜州正在以每年50平方英里的速度变小。因为弗雷德先生希望在他的新房子里生活直至终老，所以他想知道他的房子是否会被侵蚀掉。 1005题 经过进一步研究，弗雷德发现将要被侵蚀得陆地呈半圆形。半圆是一个以（0，0）点为中心的圆的一半，半圆的直边是X轴。X轴以下的部分在水中。在第一年的开始，圆的面积是0。（半圆如下图所示）。 1005 – 问题 1005 –问题分析 1）分析问题寻求算法 因为河水呈半圆形扩散，每年扩散50平方英里，所以当给定一点的坐标时，可以用它与原点的距离作为半径，计算以此为半径的半圆的面积，在用这一面积除以50，向上取整，得到的就是要求的年数。即使用如下公式计算： 1005 – 源代码 #include?stdio.h //将输入输出的库函数包含#include?math.h //将用到的库函数包含进来void?main() { //程序开始???? float?x,y; //用来存放读入的坐标值?? int?year; //用于保存计算出来的年数???? scanf(“%f?%f”,x,y); //从键盘读入坐标值???? year?=?(int)ceil((x*x+y*y)*3.1415926/2/50); //套用公式计算年数??? printf(“第?%d年年末\n”,??year);? //将算出来的年数输出到屏幕上} //程序结束 1006题 人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。 1006题 输入 输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并