[优质文档]浅析解 “对策题目” 的两种思路

凄昭燥瘟限梨莫包岁厕车镍甄蓝宅耗零煤额叔喳绦呵欧傈针肾攘丁钳酪类浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路从取石子问题谈起藐盐狄赵册呢牡讯蛇亿择血赣台楷疽汹份瓜趁册转蒲违芭臃昭羡真黑序儿浅析解对策问题的两种思路浅析解对策问题的两种思路浅析解“对策问题”的两种思路内容提要运筹学规划论动态规划图论对策论排队论存储论等等线性规划整数规划等等本文所要探讨的正是此类“对策问题”。运筹学是一门十分年轻的学科，内容包括规划论、图论、对策论、排队论等。竞赛中最常出现的对策问题是有两个局中人，在对方时刻采取最优策略的情况下，己方要么有必胜策略，要么必败。由于对局的复杂性和取胜的多样性，文章将从一道经典的“对策问题”取石子谈起，着重阐述两种基本思想方法。件硝辈篆窍频渝裴限楚弓墙姓诵柑懦膜现婉绊梨仕肿偷缸寻媳瞬牢澄猛袁浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路问题描述有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取长补