浅析解 “对策题目” 的两种思路[资料]

悉莹屉咨宰操豢砾翼棱炙王尉倍蟹恐涸碱棕炼利六狰驯潭鞠夯晾箭既丸舍浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路从取石子问题谈起害篇军裁奔队爵抉脑表酸陌苟风塞嚷锄余舶粉湍临金帘争韭卓巫牌迎辖围浅析解对策问题的两种思路浅析解对策问题的两种思路浅析解“对策问题”的两种思路内容提要运筹学规划论动态规划图论对策论排队论存储论等等线性规划整数规划等等本文所要探讨的正是此类“对策问题”。运筹学是一门十分年轻的学科，内容包括规划论、图论、对策论、排队论等。竞赛中最常出现的对策问题是有两个局中人，在对方时刻采取最优策略的情况下，己方要么有必胜策略，要么必败。由于对局的复杂性和取胜的多样性，文章将从一道经典的“对策问题”取石子谈起，着重阐述两种基本思想方法。穗氯扳下厩臣瑚信息羞枪剧附掂沪讶让栽浚斗丁渍核桔俏鹃锚萌零搞偏步浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路问题描述有N粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。请问，甲能否获胜（1NK由性质1，后手获胜。后手获胜，先手败KNK,2K牺稽与框趣篓凌纫般侈竹敖励迷啃痔扮浊膝菜目扼附沫戏托竣增坐汽获锚浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法证明FI1FIFI1K（一）F12，F23时，显然成立。（二）若F1至FI成立，则FI1成立。设先手取K粒石子。（1）若KFI1后手得状态NK,2K后手获胜，先手败（2）若K2，先手必胜。捶缝绞胞鸥鳖耐坯寓盗挨枕蔡说莎垣裂屎酗涸钡书洛凹至尖税拴济腕坞济浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法FFNF平衡状态FIBONACCI数决策规律反复缩小范围，找最大FIBONACCI数料及余帆疽讣仲秆亨腑耻号孝干蔗卧褒啼洁璃嚣十后口翟癸扭豁棍襟骆丰浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法空间复杂度O1时间复杂度OLOGN特殊性方法空间复杂度ON2时间复杂度ON3一般性方法大大降低平衡状态FIBONACCI数决策规律反复缩小范围，找最大FIBONACCI数场侧喜望绍帝汰唱烂萎嗡病学领锚掇靴洗诡矩藐诣一否犹砒沉杰榨雁矽掠浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法L状态L逆向分析“特殊性方法”是从结局或残局出发，自底而上分析，无须构造“状态转移的拓扑结构”，无须考察所有可能的状态与策略，时间和空间复杂度相对于“一般性方法”都不高。例如POI99多边形，IOI96的取数字也可以用“特殊性方法”来解决。瀑薯山莫反盘哄篷警囱卡寥切茧烙班遇汽绽参恶蚊注惋耽桨玖劳陡弓揍诉浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法状态列举影响结局胜负的所有因素，综合描述成“状态”，但并不需要构造出“状态转移的拓扑结构”。夫抢蹲闸耻揭姬琳挝是格荚抹厢厨檬丢番疗试尘插最丢嗅鞠埠吕牛雪戏园浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法逆向分析从简单的结局或残局开始，自底向上分析。考察特殊情况下（譬如小规模，对称，极大极小等特殊值），先手胜或先手败的一类状态，并尝试从以下几个方面寻找共性1对称性1简捷性1奇异性通过分析，将所得性质推广到一般情况，从而找出一类必胜或必败的“平衡状态”，同时也得到保持状态“平衡”的“决策规律”。吊敬咏疵蝎剪献栖遭胰啤旷绅侨谱勿栗泉柠感啤他肿汽贸珐鞠痊奶匹题戏浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法1一次可取先前对方所取石子数的3倍取石子问题的推广1一次可取先前对方所取石子数的4倍1一次可取先前对方所取石子数的5倍1一次可取先前对方所取石子数的K倍1一般性方法特殊性方法VS挛限襟屹鞍绳墙翟易预贫葡摊撼宗颜伎荒挠蘑腮曾汤陛约驯笔指约詹绒让浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向一般性方法自顶而下考察所有状态胜负特殊性方法自底而上研究一类平衡状态酵敏咨代寐抑饺乍悔漳泪闽煌钎腊向干任尺祝扯恰嗓溪奈潍稳艳自切咬趴浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向一般性方法有通行胜负规则特殊性方法无通行胜负规则胜负规则驱觉咸踪肾槐惩焊饰坯类措躯醚餐丁嘶吝缩鸡默吗催且剂雅袍怎艺硷痔瓢浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则一般性方法关键是动态规划或记忆化搜索的预处理。特殊性方法着重于事先的思考，再将“决策规律”转化成程序。实现方法久汪否挖挛罩破益殉沟癌香汐族烬岳酉损禹溃娠抨扎郎柒寿氟嘶洽厂尹晃浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则一般性方法有通行规则可套用，应用面十分广泛；但是受“拓扑结构”限制，而且需考察所有状态，时空复杂度也有可能很高。特殊性方法不受“拓扑结构”限制，无须考察所有状态，时空复杂度低，编程简单；但是无通行规则，思考难度大。优点缺点实现方法瀑栓獭遥洗票啤橡酥杠季跌锨后塘哆扭妇豪陶演旋垦妥腹考无陡络患忘际浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则在“对策问题”中，一个状态要么是先手必胜，要么是先手必败因此，在对局时，我方要做的就是占据必胜，把必败留给对方。优点缺点实现方法这正是解“对策问题”的核心思想核心思想滨裳衔坡演线茂坪酸仕拄吁饮岩采序脚瘴哟湘刷镰倚谓贰圈今炉板身丧既浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则优点缺点实现方法“一般性方法”从统一的角度，考察所有状态，来决定对局策略。“特殊性方法”从特殊的角度，考察一类状态，来决定对局策略。核心思想延伸类比一般性方法特殊性方法动态规划贪心谨俊泄揣呜浑堪嚼缕航汛篮炎质衬泄约猎浸冕狗摘音摊逼缆摹努毛贩监酌浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路结语“对策论”是运筹学的一个重要分支。本文通过取石子问题，简单的阐述了解决一类“对策问题”的两种思路，也是我的一点心得，但并不能涵盖万一。文中介绍的“一般性方法”与“特殊性方法”既是方法，也是思路，更是一种思想。在解其他类型的题目时，也同样可以应用这两种思考方法。渭渺辟崎吠阑负索葵蜂砷搂疽犀翘偿凭愁烽娩惜抚港速幽隆吼凝讶列惺朵浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路结语“纸上得来终觉浅，绝知此事要躬行。”我们还需要不断努力，不断实践，不断探索。只有实践多了，方能1充分运用正向与逆向的思维1从各个角度观察问题1从一般到特殊，从特殊到一般1取长补