资源描述：
《北京大学ACM国际大学生程序设计竞赛课件3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、问题求解与程序设计 第三讲 称重问题李文新2004.2–2004.6内容提要作业总结-1008作业总结-1013何林冬令营报告–称球问题自学及讨论–征服者作业作业总结-1008题意Haab19个月前18个月每月20天第19个月5天0-19月名0-5月名Tzolkin13个月天数为20个轮转1mix2---3---…问题将Haab日期转换成Tzolkin日期源程序1008源程序作业总结-1013题意12枚硬币，其中一枚是假币，可能轻也可能重称三次，每次左右硬币数目相等，结果：轻重平问题求出假币，并给出
2、其轻重源程序1013源程序一类称球问题的解法长沙雅礼中学何林问题的提出给定N个球有个比标准球重的次品混入其中你有一架天平，用最少的次数找出这个次品。N=312312①是次品12②是次品12③是次品N=3时称1次就可以找出次品N=9123456789ABCAB次品在A中次品在B中AB通过一次称量，可以把次品可能存在的范围从9个，缩小到3个N=3的时候一次就能称出次品N=9时称2次次品在C中AB更一般的情况N=3k12k……12k……12k……ABC更一般的情况ABABAB次品在A中次品在B中次品在C中
3、范围缩小到原来的1/3更一般的情况n=3k+1,n=3k+2和n=3k类似，也是均分成三堆每次称量把范围大致缩小到原来的1/3因此：从n个球中找次品至多要称[log3n]次。（[]统一表示取上整）判定树[log3n]无疑是可行解。最优性为什么三分？因为天平只有三种可能：左偏、右偏、平衡判定树称(1,2)>=<132叶子代表结果非叶子代表一次称量每个非叶子节点都有三个孩子，表示天平左偏、右偏、平衡判定树比较(1,2,3)与(4,5,6)>=<比较(1)与(2)>13=<2比较(7)与(8)>79=<8
4、比较(4)与(5)>46=<5判定树的深度就是称量次数一个有意义的判定树至少n个叶子节点判定树N个叶子的三叉树的深度h>=[log3n][log3n]是最优解小结引进了有力工具：判定树。将主观的直觉严谨化。三分法是解决这类问题的根本着眼点。三分时必须充分的均匀ProblemConqueror’sbatalionTableofContentsTheproblemSolutionTheproblemCENTRALEUROPEANOLYMPIADININFORMATICS30June–6July2002D
5、ay1:conquerConqueror’sbattalionTimelimit:1sMemorylimit:16MBTheproblemInthewholehistoryofmankindonecanfindseveralcuriousbattles,likethefollowingoneinFrance,in1747...TheproblemTherewasafortressinBassignac-le-Haut,asmallvillagelyingontheleftbankofriverDor
6、dogne,justovertheChastangdam.Fromthedamuptothefortresstherewasawidestaircasemadeoutofredmarble.TheproblemOnedayinthemorning,theguardspottedalargebattalionApproachingthefortress,withadreadedleader–TheConqueror.TheproblemWhenTheConquerorreachedthefortres
7、s,hewasalreadyawaitedbyitscommandant.Thecommandantproposed:“Iseethatyouhavemanysoldiersbehindyou,standingonthestairs.Wecanplayasmall‘game’:TheproblemIneachround,youwilldivideyoursoldiersintotwogroupsinanarbitraryway.ThenIwilldecidewhichoneofthemstaysan
8、dwhichonegoeshome.Eachsoldierthatstayswillthenmoveuponestair.TheproblemIfatleastoneofyoursoldiersreachestheuppermoststair,youwillbethewinner,intheothercase,youwillbetheloser.TheproblemTheConquerorimmediatelylikedthisgame,soheagreedandst
