问题求解与程序设计
第二讲
对局问题
李文新
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。 所有 给定时间是非负的并且小于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 <stdio.h>
# include <math.h> void main(){
int p,e,i,d,j,no=1;
scanf("%d %d %d %d\ n",&p,&e,&i,&d); while(p!=-1 && e!=-1 && i!=-1 && d!=-1){
for(j=d+1; j<=21252; j++) if ((j-p)%23 == 0) break; for( ; j<=21252; j=j+23) if ((j-e)%28 == 0) break; for( ; j<=21252; j=j+23*28) if ((j-i)%33 == 0) break;
printf("Case %d: the next triple peak occurs in %d days.\ n",no,j-d); scanf("%d %d %d %d\ n",&p,&e,&i,&d);
no++; }
}
放硬币问题
在一个圆形桌面上，甲、乙轮流放5分硬币，不许 重叠，甲先放，首先放不下硬币的一方为负。甲 如何取胜呢？
放硬币问题
事实上，甲只要先在圆桌中心放下一枚硬币， 此后无论乙怎么放，甲总在其关于中心对称 处放一枚，最终甲必然获胜。
甲 乙
取火柴问题
一堆火柴有N根，A，B两人轮流取出。每次可 以取1根或2根，问先取者能否有必胜策略？
取火柴问题
• 一般解答：
分情况讨论：N=3k 后手胜和 N！=3k 先手胜(k 为正整数)
• 推广：
每次可以取1..n根火柴(n为正整数，且1<=n<N) 则 N=k(n+1) 后手胜，N！=k(n+1)先手胜(k为正 整数)
取石子问题 – n堆
! 甲乙两人面对若干堆石子，其中每一堆石子 的数目可以任意确定。例如图1所示的初始局 面：共n=3堆，其中第一堆的石子数a1=3， 第二堆石子数a2=3，第三堆石子数a3=1。两 人轮流按下列规则取走一些石子，游戏的规 则如下：
• 每一步应取走至少一枚石子；
• 每一步只能从某一堆中取走部分或全部石子；
• 如果谁无法按规则取子，谁就是输家。
取石子问题– n堆
第一堆：a1=3 第二堆：a2=3 第三堆：a3=1
图 1 游戏的一个初始局面
取石子问题– n堆
! 对于游戏A来说，任意的一个初始局面S=(a1, a2, …, an)，我们把这里的ai都看成是二进制 数。令#S=a1 a2 … an。若#S≠0，则 先行者（甲）有必胜策略；否则#S=0，这时 后行者（乙）有必胜策略。
取石子问题– n堆
! 例如1：
第一排，a1=7
第二排，a2=3
第三排，a3=3
1 2 3 4 5 6 7
取石子问题– 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粒 甲取2粒 甲取3粒
乙取1粒 乙取2粒 乙取1粒 乙取2粒 乙取1粒 甲取1粒 甲取2粒 甲取1粒 甲取1粒
乙取1粒
（4, 3）
（3, 2） （2, 2） （1, 1）
（2, 2） （1, 1）
（1, 1）
（0, 0）
（0, 0） （0, 0）
（1, 1）
（0, 0）
（0, 0） （0, 0）
自 顶 而 下 构 造
取石子问题– 1堆
"如果一个状态没有子状态，是结局，则根据题目条件判定胜负
（4, 3）
（3, 2） （2, 2） （1, 1）
（2, 2） （1, 1）
（1, 1）
（0, 0）
（0, 0） （0, 0）
（1, 1）
（0, 0）
（0, 0） （0, 0）
败
败 败 败
败 败
注：这里的胜败指的均是先手胜败。
取石子问题– 1堆
"如果一个状态至少有一个子状态是先手败，则该状态是先手胜
胜
胜 胜
胜
胜
胜
（4, 3）
（3, 2） （2, 2） （1, 1）
（2, 2） （1, 1）
（1, 1）
（0, 0）
（0, 0） （0, 0）
（1, 1）
（0, 0）
（0, 0） （0, 0）
败
败 败 败
败 败
注：这里的胜败指的均是先手胜败。
取石子问题– 1堆
"如果一个状态的所有子状态都是先手胜，则该状态是先手败
胜
败
胜
胜 胜
胜
胜
胜
（4, 3）
（3, 2） （2, 2） （1, 1）
（2, 2） （1, 1）
（1, 1）
（0, 0）
（0, 0） （0, 0）
（1, 1）
（0, 0）
（0, 0） （0, 0）
败
败 败 败
败 败
注：这里的胜败指的均是先手胜败。
取石子问题– 1堆
5 …… 2 3 8 甲必败：
4 6 7 …… 甲必胜：
取石子问题– 1堆
甲必败： 甲必胜：
2 3 4
5 6 7
8 ……
……
Fibonacci 数列
取石子问题– 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)时，显然成立。
（二）若F1至Fi成立，则Fi+1成立。 设先手取K粒石子。
（1）若K≥Fi-1 后手得状态(N-K,2K) 后手获胜，先手败 2K≥2Fi-1≥Fi-1+Fi-2= Fi> N-K 由性质1，后手获胜。
Fi-1 Fi
Fi+1 (N-K,2K) K
取石子问题
证 明：
（2）若K < Fi-1
根据假设（Fi-1,K）K < Fi-1 必败，所以后手可以使先手 面临(Fi，X)状态。
Fi-1 Fi
Fi+1 (Fi,X) K
由性质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}且N>2，先手必胜。 平衡状态: Fibonacci数
决策规律: 找最大Fibonacci数
F F’
N F’’
小结
! 上周作业总结
! 放硬币问题
! 取火柴问题
! 取石子问题 - n堆
! 取石子问题 – 1堆
! 作业 – 装箱问题
作业
! 1008
! 1013
