上海市控江中学上海市控江中学上海市控江中学上海市控江中学 王建德王建德王建德王建德6 6、20022002、20032003年年分分区区联联赛赛复复赛赛试试题解析题解析1 1、高精度运算、高精度运算2 2、图的运算、图的运算3 3、搜索算法、搜索算法4 4、构造算法、构造算法5 5、动态程序设计、动态程序设计题题型型题题目目与课内知识相关与课内知识相关自自由由落落体体、级级数数求求和和、乒乒乓乓球球、麦森数麦森数 字符串处理字符串处理字符近似查找字符近似查找贪心法贪心法均分纸牌、传染病控制均分纸牌、传染病控制 回溯法回溯法选选数数、字字串串变变换换、栈栈、神神经经网网络络、侦探推理侦探推理 动态程序设计方法动态程序设计方法过河卒、数字游戏、加分二叉树过河卒、数字游戏、加分二叉树 几何计算几何计算矩形覆盖矩形覆盖虽然虽然2002、2003年全国奥林匹克信息学复赛中含许多可年全国奥林匹克信息学复赛中含许多可“一题多解一题多解”的试题，但如果按照较优算法标准分类的话，大致的试题，但如果按照较优算法标准分类的话，大致可分为可分为特特特特 点点点点 1、凸现信息学知识和凸现信息学知识和学科学科知识整合的趋势知识整合的趋势。为了考核学生为了考核学生运用学科知识运用学科知识的能力，激发学生的的能力，激发学生的创造力，创造力，2002、2003年全国奥林匹克信息年全国奥林匹克信息联联赛赛(NOIP)中学科类中学科类的试题增加，并且首次出现了计的试题增加，并且首次出现了计算几何类的试题算几何类的试题( (矩形覆盖矩形覆盖矩形覆盖矩形覆盖) )。这说明信息学与。这说明信息学与学科学科的的依赖关系日益凸现，依赖关系日益凸现，学科基础好、尤其是学科基础好、尤其是数学素数学素质好的人虽然不一定会编程，但希望学习编程的质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数潜质和爱好，他们中愈来愈多的人也希望深造数学。学。各各门学科的交融和整合是奥林匹克信息学门学科的交融和整合是奥林匹克信息学联联赛赛活动发展的一个大趋势活动发展的一个大趋势（按照（按照2005年国家教改方案，数学年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识）。教材增加算法内容，信息科技教材掺入语言知识）。2、“构造法构造法”或贪心策略类试题的引或贪心策略类试题的引入，使得入，使得算法知识的不确定性和不稳定算法知识的不确定性和不稳定性增加。性增加。这正体现了科学的本质这正体现了科学的本质知识知识是不断推陈出新的。是不断推陈出新的。3、试题的综合性增加试题的综合性增加，并不一定随知，并不一定随知识的分类而发生变化，有时几乎找不识的分类而发生变化，有时几乎找不到一个到一个单一单一的的经典算法经典算法( (字串变换字串变换字串变换字串变换回溯法中有回溯法中有回溯法中有回溯法中有字符串处理字符串处理字符串处理字符串处理) )，也找不到一个也找不到一个纯粹纯粹的数据结的数据结构问题构问题（级数求和（级数求和（级数求和（级数求和需要为表达式的计算结果设计合适的需要为表达式的计算结果设计合适的需要为表达式的计算结果设计合适的需要为表达式的计算结果设计合适的数据类型）数据类型）数据类型）数据类型），关键是你从哪个角度去分析，关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；愈高，得胜的机率愈大；4、经常面对着不知道算法的试题，经常面对着不知道算法的试题，面对着谁都不知如何处置的情境面对着谁都不知如何处置的情境（经（经常出现许多选手在一题中得常出现许多选手在一题中得0 0分、优秀选手表现失常的情况分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的深入问题的空间并形成解决问题的意识、习惯和能力意识、习惯和能力。能不能能不能创造性创造性地应答没有遇到过的挑战地应答没有遇到过的挑战，成为培成为培训的基本要求和目标。训的基本要求和目标。1 1、培培养养问问题题意意识识和和问问题题能能力力。创创造造始始于于问问题题。“有有了了问问题题才才会会思思考考，有有了了思思考考才才有有解解决决问问题题的的方方法法，才才有有找找到到独独立立思思路路的的可可能能（陶陶行行知知）”。有有问问题题虽虽然然不不一一定定有有创创造造，但但没没有有问问题题一一定定没没有有创创造造（想想一一想想当当前前的的解解法法有有没没有有缺缺陷陷，有有没没有有更更好好的的算算法法，它它与与哪哪些些问问题题有有联联系系，与与哪哪些些知知识识相相关关联联，还还可可以以拓拓延延出出哪哪些些问题，要解决这些问题还需要哪些知识）问题，要解决这些问题还需要哪些知识）；启启启启示示示示2、处处理理好好前前沿沿性性与与基基础础性性、直直线线培培训训和和散散点点培培训训、循循序序渐渐进进与与跳跳跃跃式式的的矛矛盾盾。如如果果恪恪守守按按部部就就班班的的培培训训程程序序，不不谋谋求求跳跳跃跃式式学学习习，将将离离全全国国和和国国际际奥奥林林匹匹克克信信息息学学活活动动的的前前沿沿、离离世世界界程程序序设设计计知知识识的的前前沿沿愈愈来来愈愈远远。因因此此在在进进行行基基础础课课程程学学习习的的同同时时，必必须须有有追追逐逐前前沿沿的的选选择择性性学学习习。这这里里，有有时时候候心心理理的的障障碍碍比比科科学学上上的的障障碍碍更更难难跨跨越越，敢敢不不敢敢的的问问题题比比能能不不能能的的问问题题更更突突出出。其其实实在在学学习习中中或或多多或或少少地地都都有有必必要要的的跳跳跃跃，不不少少人人还还能能够够实实现现比比较较大大的的跳跃跳跃（ 爱笛生小学三年级退学、比尔爱笛生小学三年级退学、比尔. .盖茨大学三年级退学）盖茨大学三年级退学）v学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构v培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对对基基础础的的理理解解是是主主观观的的选选择择。例例如如中中国国、美美国国和和俄俄罗罗斯斯的的理理科科教教材材大大不不相相同同，有有的的同同年年级级同同学学科科的的教教材材相相差差三三分分之之二二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。3、参参与与活活动动的的学学生生应应由由竞竞争争关关系系和和独独立立关关系系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转转向向合合作作学学习习的的关关系系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）学生的心理调适：学生的心理调适：v我掌握的知识仅不过是沧海一粟我掌握的知识仅不过是沧海一粟(进取心进取心)；v固守错误的概念比一无所知更可怕固守错误的概念比一无所知更可怕（明智）（明智）；v三人之行必有我师三人之行必有我师（谦虚）（谦虚）；v知识生产社会化条件下人的基本素质之一知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如上千科学家进行长期甚至跨国的合作，例如制作制作windows，人类基因工程）人类基因工程）（现代意识）（现代意识）；前提条件：前提条件：水平相当的同质成员水平相当的同质成员或各有所长（包括数学知识、编或各有所长（包括数学知识、编程能力和思维方式等解题所需的程能力和思维方式等解题所需的各种因素）的异质成员是开展合各种因素）的异质成员是开展合作学习的组织基础；作学习的组织基础；合作学习的效应：合作学习的效应：v集思广益容易出好的算法；集思广益容易出好的算法；v群体设计的测试数据相对全面；群体设计的测试数据相对全面；v在群体活动中能比较客观的反映自己在群体活动中能比较客观的反映自己能力情况；能力情况；v每个学生在付出与给予中可提高合作每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相精神和编程能力，成功者往往是那些相容性好、容性好、乐于帮助他人，并且善于取乐于帮助他人，并且善于取他人之长的学生他人之长的学生（符文杰、张一飞等）。（符文杰、张一飞等）。4、选选手手面面对对从从未未遇遇到到过过的的挑挑战战应应调调整整好好心心态态，不不要要急急功功近近利利，要要只只管管耕耕耘耘、不不问问收收获获、潜潜心心钻钻研研、其其乐乐无无穷穷。那那怕怕是是一一两两次次失失误误，也也是是砥砥砺砺之之石石，可可从从中中汲汲取取有有益益的的经经验验和和教教训训。“不不是是一一番番寒彻骨，哪得梅花扑鼻香寒彻骨，哪得梅花扑鼻香”。题题5、均分纸牌、均分纸牌题题6、字串变换、字串变换题题7、自由落体、自由落体题题8、矩形覆盖矩形覆盖题题1、字符近似查找、字符近似查找题题2、级数求和、级数求和题题3、选数、选数题题4、过河卒、过河卒9、乒乓球、乒乓球10、数字游戏、数字游戏11、栈、栈12、麦森数、麦森数13、神经网络、神经网络14、侦探推理、侦探推理15、加分二叉树、加分二叉树16、传染病控制、传染病控制第一题：字符近似查找第一题：字符近似查找设有n个单词的字典表（1n100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）：i：该单词在字典表中的序号；Ei：在字典表中仅有一个字符不匹配的单词序号；Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号；N：其他情况当查找时有多个单词符合条件，仅要求第一个单词的序号即可。输入文件输入文件输入文件名为a.in，文件的格式如下：n（字典表的单词数）n行，每行一个单词待匹配单词输出文件输出文件输出文件名a.out，格式如下：iEiFi其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情况不存在，则输出N。输入输出样例输入输出样例输入1:5abcdeabcasdfasfdabcdaacdabcd输出输出1:4E5F1输入输入2:1ab输出输出2:0E0F0N我们将字典表中的单词分成3类：第1类：单词与待匹配单词多或少一个字符，其余字符匹配；第2类：单词仅有一个字符与待匹配单词不匹配；第3类：单词与待匹配单词完全匹配；设constnote:array1.3ofstring=(F,E,)；匹配情况的标志varwant:string；待匹配单词list:array1.100ofstring；字典表。其中listi为字典ians：array1.100ofinteger；单词的类别序列。其中ansi=1、匹配情况的计算、匹配情况的计算计算两个等长字串中不同字符的个数计算两个等长字串中不同字符的个数function find(a,b:string):integer；输入两个等长字串a,b，计算和返回不同字符的个数vari,tot:integer；begintot0；for i1 to length(a) do if aibi then inc(tot)；findtot；end； find n判别一个字串是否比另一个字串多一个字符（其余字符匹配）判别一个字串是否比另一个字串多一个字符（其余字符匹配）n我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则猜想不成立。nfunction function check(a,b:string):integercheck(a,b:string):integer； 输输入入字字串串a,ba,b。若若b b能能够够在在a a的的基基础础上添加一个字符得到的话，则返回上添加一个字符得到的话，则返回1 1；否则返回；否则返回00nvarvar i:integeri:integer；nbeginbeginncheck0check0；nfor i0 to length(a) do begin for i0 to length(a) do begin nacopy(a,1,i)+bi+1+copy(a,i+1,255)acopy(a,1,i)+bi+1+copy(a,i+1,255)； 在在aiai后插入后插入bi+1bi+1nif a=b if a=b 若插入后两串相同，则成功退出若插入后两串相同，则成功退出 nthen begin check1then begin check1；exitexit；endend；thenthenndelete(a,i+1,1)delete(a,i+1,1)； 删去删去a a中的插入字符中的插入字符 nendend；forfornendend；checkcheckn2 2、计算字典表中的每一类单词、计算字典表中的每一类单词首先，我们依次计算每一个单词的类别序号 在单词i与待匹配单词等长的情况下，若两串相同，则单词i的类别记为3；若两串仅有一个字符不同，则单词i的类别记为2； 若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0；然后根据ans序列在字典表中依次搜索类别3类别1的单词，输出对应的单词序号。如果在字典表中不存在上述3种类别的单词，则输出N。fillchar(ans,sizeof(ans),0)； 单词的类别序列初始化for i1 to n do begin 对字典中的每个单词进行分类 if length(listi)=length(want) 若单词i与待匹配单词等长 then begin kfind(listi,want)；计算单词i与待匹配单词的不同字符个数 if k=0 then ansi 3； 记下类别序号 if k=1 then ansi 2； end；then若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0iflength(listi)+1=length(want)thenansicheck(listi,want)；iflength(listi)=length(want)+1thenansicheck(want,listi)；end；forhavefalse；匹配情况存在的标志初始化fori3downto1dobegin依次输出每一类别的单词在字典表最先出现的序号k0；forj1tondoifansj=ithenbeginkj；break；end；thenhavehaveor(k0)；writeln(notei,k)；end；for第二题：级数求和第二题：级数求和已知：Sn=1+1/2+1/3+.+1/n。显然当n.非常大的时候，Sn可大于任何一个整数K。现给出一个整数K（1K15），要求计算出一个最小的n，使得SnK。输入输入键盘输入k输出输出屏幕输出n输入输出样例输入输出样例输入: 1输出: 2算法分析算法分析该题考核选手的并不是编程能力，而是选择变量类型的能力。由于该数列是递减的，而k的上限为15，因此项数很大，即便是longint也容纳不下。但未必非高精度运算不可。只要启动浮点数运算（$n+），将项数设为extended类型，便可以得出正确解。$n+ 启动浮点数运算vars,b,k:extended； 数列的和、项数、最接近sn(大于sn)的整数值begins0； 数列的和初始化b0； 项数初始化readln(k)； 读最接近sn(大于sn)的整数值kwhile s=k do 若目前数列的和小于k，则项数b+1，计算sb beginbb+1；ss+1/b； end；while 输出项数round(b)；end.main第三题：选数第三题：选数已知n个整数x1,x2,.xn,以及一个整数k(kn)。从n个整数中任选k个整数组合相加，可分别得到一系列的和。例如当n=4,k=3，4个整数分别为3，7，12，19时，可得全部的组合为：3+7+12=223+7+19=297+12+19=383+12+19=34。现在，要求你计算出和为素数的组合数有多少种。例如上例，只有一种组合的和为素数：（3+7+19=29）。输入输入输入文件名为c.in。文件格式n,k（1n20，ka，则说明a不可能分解出比primei大的素数了，a本身为素数。由于primei表的最大素数接近10000，其平方远大于xi的上限5000000，因此是一个比较可行的方法：function check(a:longint):boolean； 判断a是否是素数beginchecktrue； 素数标志初始化for i1 to tot do begin 搜索素数表 if primei*primeia then exit；若超出搜索范围的上限，则说明a是素数，返回true if a mod primei=0 then begin checkfalse；exit；end；thenend；forend； check 2 2、递归搜索方案数、递归搜索方案数 由于数列是随机和无序的，因此只能通过搜索的办法求解。设状态(left,now,all)：目前组合为all，还需要从xnowxn中选出left个数； 约束条件(leftn-now+1)：xnowxn中数的个数大于等于left；边 界 条 件 （ (left=0) and (now=n+1)） 和 目 标 状 态（check(all)=true）：从x1xn中选出k个数为边界。在这种情况下，若k个数的和为素数，则满足条件的种数+1。到达边界后，应回溯；搜索范围为两种选择：当前组合不选xnow,递归计算子状态(left,now+1,all)；在还有数需要选的情况下（left0），xnow选入组合，递归计算子状态(left-1,now+1,all+listnow)；由此得出子程序Procedure solve(left,now,all:longint)；递归计算选数情况beginif (leftn-now+1)then exit；若xnowxn中不足left个数，则回溯 if (left=0) and (now=n+1) 若从x1xn中选出了k个数 then begin if check(all) then inc(ans)；若k个数的和为素数，则满足条件的种数+1 exit； 回溯 end；then solve(left,now+1,all)；当前组合不选xnow,递归计算子状态if left0 在还有数需要选的情况下，xnow选入组合，递归计算子状态 then solve(left-1,now+1,all+listnow)；end； solve显然，递归调用solve(k,1,0)后得出的ans即为问题的解。过河卒过河卒如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图中的P1，P2.P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：CA，同时CB）。现在要求你计算出卒从A点能够到达B点的路径的条数。输输入：入：键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）输输出：出：屏幕输出一个整数（路径的条数）。输入输出样例：输入输出样例：输入：3322输出：01 1、计算对方马的控制点、计算对方马的控制点按按照照题题意意，对对方方的的马马所所在在的的点点和和所所有有跳跳跃跃一一步步可可达达的的点点称称为为对对方方马马的的控控制制点点，卒卒不不能能通通过过对对方方马马的的控控制制点点。在在卒卒出出发发之之前前，必必须须计计算算对对方方马马的的所所有有控控制制点点。显然，若（显然，若（0，0）或（）或（n,m）为控制点，则输出路径数为为控制点，则输出路径数为0。设。设constconst move:array1.8,1.2move:array1.8,1.2ofintegerofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)(-2,-1)； movek movek，1.21.2为马沿为马沿k k方向跳跃一步的水平增量和垂直增量方向跳跃一步的水平增量和垂直增量 varvar list:array-1.20,-1.20 list:array-1.20,-1.20 of of compcomp； 路路径径数数序序列列，其其中中listi,jlisti,j为为卒卒从从(0,0)(0,0)到到( (i,j)i,j)的路径数的路径数 can:array0.20,0.20 of can:array0.20,0.20 of booleanboolean； 点点( (i,j)i,j)允许卒通行的标志允许卒通行的标志 马的初始位置为（马的初始位置为（x,yx,y）。）。我们按照下述方式计算我们按照下述方式计算cancan序列：序列：canx,ycanx,y falsefalse； 对方马所在的点为控制点对方马所在的点为控制点 for ifor i1 to 8 do begin1 to 8 do begin从（从（x x，y y）出发，沿出发，沿8 8个跳马方向计算控制点个跳马方向计算控制点 j jx+movei,1x+movei,1； 计算计算i i方向的跳马位置方向的跳马位置( (j j，k)k) k ky+movei,2y+movei,2； if (j=0) and (k=0) and (j=n) and (k=0) and (k=0) and (j=n) and (k=m) 若（若（j,kj,k）在界内，则为控制点在界内，则为控制点 then canj,kthen canj,k falsefalse；endend；forforif (not can0,0)or(not cann,m) if (not can0,0)or(not cann,m) 若卒的起点和终点为控制点，则输出路径数若卒的起点和终点为控制点，则输出路径数00 then then writelnwriteln(0)(0) else begin else begin 计算和输出卒从（计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径数点的路径数listn,mlistn,m；endend；elseelse2 2、计计算算和和输输出出卒卒从从（0 0，0 0）走走到到（n,mn,m）点点的的路路径径条条数数 我我们们按按照照由由上上而而下下、由由左左而而右右的的顺顺序序，将将卒卒可可能能到到达达的的每每一一个个位位置置（i,ji,j）(0(0inin，0jm0jm) )设为阶段设为阶段, ,显然这样做，可以取消对状态的枚举。显然这样做，可以取消对状态的枚举。 首首先先，将将卒卒的的出出发发点点（0 0，0 0）的的路路径径数数设设为为1 1（list0,0list0,01 1），并并将将该该位位置置设设为为控控制制点点（can0,0can0,0 falsfals）。然然后后从从（0 0，0 0）出出发发，按按照照由由上上而而下下、由由左左而而右右的的顺顺序序计计算算卒卒经经过过每每一一个个可可行行点点的的路路径径数数。若若（i i，j j）为为可可行行点点，则则卒卒可可由由上上侧侧的的（i-1,ji-1,j）和和左左侧侧的的（i,j-1i,j-1）进进入入该该点点。将将这这两两点点的的路路径数加起来，即为从（径数加起来，即为从（0 0，0 0）走到（）走到（i i，j j ）的路径数，即的路径数，即 listi,j=listi-1,j+listi,j-1listi,j=listi-1,j+listi,j-1（i i，j j）非控制点非控制点依次类推，最后得出的依次类推，最后得出的listn,mlistn,m即为问题的解。由此得出算法：即为问题的解。由此得出算法： fillcharfillchar(list,(list,sizeofsizeof(list),0)(list),0)； 路径数序列初始化路径数序列初始化 list0,0list0,01 1； 卒从（卒从（0 0，0 0）出发的路径数为）出发的路径数为1 1，该位置不再允许卒通行，该位置不再允许卒通行 can0,0can0,0 falsefalse； for for i i0 0 to to n n dodo对对于于每每个个可可行行点点, ,小小兵兵要要么么从从左左侧侧、要要么么从从上上方方走走到到, ,由由此此计算从计算从(0,0)(0,0)到到( (i,j)i,j)的路径数的路径数 for jfor j0 to m do if cani,j0 to m do if cani,j then listi,j then listi,jlisti-1,j+listi,j-1listi-1,j+listi,j-1；输出卒从（输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数点的路径条数listn,mlistn,m；题一题一均分纸牌均分纸牌问问题题描描述述有N堆纸牌，编号分别为1，2，.N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在在编编号号为为1 1堆堆上上取取的的纸纸牌牌，只只能能移移到到编编号号为为2 2的的堆堆上上；在在编编号号为为N N的的堆堆上上取取的的纸纸牌牌，只只能能移移到到编编号号为为N-1N-1的的堆堆上上；其其他他堆堆上上取取的的纸纸牌牌，可可以以移移到到相相邻邻左左边边或或右右边边的的堆堆上上。现在要求找出一种移动方法，用用最最少少的的移移动动次次数数使使每每堆上纸牌数都一样多堆上纸牌数都一样多。例如N=4，4堆纸牌数分别为：98176移动3次可达到目的：从取4张牌放到（981310）从取3张牌放到（9111010）从取1张牌放到（10101010）。 输输 入入 ： N （N堆纸牌，1N100）A1，A2，.An(N堆纸牌，每堆纸牌初始数，1Ai10000) 输输 出出 ：所有堆均达到相等时的最少移动次数。输入输出样例输入输出样例输入：输入：498176输出：输出：3设list为纸牌序列，其中listi为第i堆纸牌的张数（1in），ave为均分后每堆纸牌的张数，即；ans为最少移动次数。我们按照由左而右的顺序移动纸牌。若第i堆纸牌的张数listi超出平均值，则移动一次(ans+1)，将超出部分留给下一堆，既第i+1堆纸牌的张数增加listi-ave；若第i堆纸牌的张数listi少于平均值，则移动一次(ans+1)，由下一堆补充不足部分，既第i+1堆纸牌的张数减少ave-listi；右邻堆取的牌问题是，在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(listi+1-(ave-listi)xuud-yy-yzA.out文件：文件：31 1、分析变换规则分析变换规则分析变换规则分析变换规则设规则序列为rule，其中第i条规则为rulei，1rulei，2；当前串为now，其中tmp为now的一个待匹配子串。由于匹配过程的由左而右进行的，因此设j为now的指针，即从now的第j个字符开始匹配rulei,1。now适用第i条规则的条件是vnow中的子串被第i条规则替换后的长度小于255，即length(now)+length(rulei,2)-length(rulei,1)255vrulei,1是now的一个子串（k=pos(rulei,1,tmp)0）在使用了第i条规则后，now变换为now=copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rulei,1),255)由于now中可能有多个子串被第i条规则替换，因此每替换一次后，为了方便地找出下一个替换位置，我们将当前被替换串前（包括被替换串）的子串删除。2 2、使用回溯法计算最少替换次数、使用回溯法计算最少替换次数、使用回溯法计算最少替换次数、使用回溯法计算最少替换次数由于原串a、目标串b和规则rule是随机输入的，因此不可能找出直接计算最少替换次数best的数学规律，只能采用回溯搜索的办法。设v状态（need,now）:替换次数为need，替换结果为now；v边界条件（needbest）和目标状态（now=b）：替换次数达到或超过目前得出的最小值为边界；已经替换出目标串为目标状态；v搜索范围i：尝试每一条规则,即1i规则数n；v约束条件（length(now)+length(rulei,2)-length(rulei,1)255）：now中的子串被第i条规则替换后的长度小于255；由此得出计算过程：proceduresolve(need；now)；从当前串now出发，递归第need次替换vari,k,j:integer；tmp:string；beginifneed=bestthenexit；若到达边界，则回溯ifnow=bthenbegin若达到目标状态，则记下替换次数，并回溯bestneed；exit；end；thenfori1tondo搜索每一条规则iflength(now)+length(rulei,2)-length(rulei,1)0do反复在tmp中寻找子串rulei,1beginsolve(need+1， copy(now,1,j+k-1)+rulei,2+copy(now， j+k+length(rulei，1)，255)；递归下一次替换delete(tmp,1,k)；将当前被替换串前（包括被替换串）的子串删除jj+k；右移匹配指针kpos(rulei,1,tmp)；继续尝试第i条规则end；whileend；thenend；solve由此得出主程序：读入初始串a和目标串；读入替换规则rule；best31；设定替换次数的上限solve(0,a)；回溯搜索最少的替换次数ifbest=30输出最少替换次数thenwriteln(best)elsewriteln(ERROR!)；、题三题三自由落体自由落体问问题题描描述述: 在高为H的天花板上有n个小球，体积不计，位置分别为0，1，2，n-1。在地面上有一个小车(长为L，高为K，距原点距离为S1)。已知小球下落距离计算公式为S=1/2*g*t2，其中g=10，t为下落时间。地面上的小车以速度V前进。如下图：小车与所有小球同时开始运动，当小球距小车的距离小车与所有小球同时开始运动，当小球距小车的距离0.000010.00001时，即认为时，即认为小球被小车接受小球被小车接受（小球落到地面后不能被接受）。请你计算出小车能接受到多少个小球。输入输入：H，S1，v，L，k，n（1H，S1，v，L，k，n100000）输出输出：小车能接受到的小球个数。 这是分区联赛最容易失这是分区联赛最容易失误的一道试题，关键是误的一道试题，关键是弄清小车行程的物理意弄清小车行程的物理意义和计算的精度误差！义和计算的精度误差！算法分析算法分析由题意可知，车顶与天花板的距离为h-k，小球由天花板落至车顶所花费的时间为t1=，由天花板落至地面的时间为t2=。小车与所有小球同时开始运动，当小球距小车的距离0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。显然，若n1n2，则小车接受的小球数为n1-n2+1；否则小车未接受任何一个小球。小车在行驶了t1*v-0.00001路程后接受了第一个小球，其编号为n1=minn-1,小车在行驶了t2*v+0.00001路程后小球落地，小车接受最后一个小球的编号为n2=max0，。为什么在为什么在n1n1的公式中加上的公式中加上L L？为什为什么在么在n2n2的公式中加上的公式中加上0.50.5？为什么为什么n1n1取下整、取下整、n2n2取上整？取上整？矩形覆盖矩形覆盖问问题题描描述述：在平面上有n个点(n100)，每个点用一对整数坐标表示。例如：当n=4时，4个点的坐标分别为：p1(1，1)，p2(2，2)，p3(6，3)，p4(7，0)这这些些点点可可以以用用 k k 个个矩矩形形( ( k4) k4) 全全部部覆覆盖盖，矩矩形形的的边边平平行行于于坐坐标标轴轴。如图一，当k=2时，可用如图二的两个矩形s1，s2覆盖，s1，s2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：v 覆盖一个点的矩形面积为覆盖一个点的矩形面积为0 0；v覆盖平行于坐标轴直线上点的矩形面积也为覆盖平行于坐标轴直线上点的矩形面积也为0 0；v各个矩形间必须完全分开（边线也不能重合）；各个矩形间必须完全分开（边线也不能重合）；本试题是高中组复赛中最难本试题是高中组复赛中最难的一道试题，对选手的几何的一道试题，对选手的几何基础和编程能力是一个比较基础和编程能力是一个比较严峻的考验。严峻的考验。 算法分析算法分析1、点和矩形的描述和关系、点和矩形的描述和关系平面上的点由坐标（x,y）表示。由于计算过程是按照由下而上、由左而右进行的，因此我们按照x坐标递增的顺序和y坐标递增的顺序将n个点存入a序列。矩形由2条平行于x轴的边界线和2条平行于y轴的边界线围成。为了计算最小矩形的方便，我们将空矩形的左边界设为、右边界为设-、下边界设为、上边界设为-。2、计算覆盖所有点的一个最小矩形、计算覆盖所有点的一个最小矩形设目前最小矩形的四条边界为maxx，maxy，minx，miny。如何按照面积最小的要求将a点加入矩形呢？显显然然需需要要调调整整边边界界线，使线，使a a点位于对应的边界线上。点位于对应的边界线上。初始时，我们设最小矩形为空，即左边界left为、右边界right为-、下边界top为、上边界bottom为-。然后由左而右，依次往矩形放入n个点，调整对应的边界线。最后得出的矩形为最小矩形，其面积为（右边界-左边界）*（上边界-下边界）3 3、计算覆盖所有点的两个面积和最小的独立矩形、计算覆盖所有点的两个面积和最小的独立矩形、计算覆盖所有点的两个面积和最小的独立矩形、计算覆盖所有点的两个面积和最小的独立矩形我们称彼此完全分开的矩形是独立的。两个覆盖所有点的独立矩形有两种形态：我们将覆盖x轴左方点集a1,1.j的最小独立矩形存入tac1,j；将覆盖x轴右方点集a1,j.n的最小独立矩形存入tdc1,j；将覆盖y轴下方点集a2,1.j的最小独立矩形存入tac2,j；将覆盖y轴上方点集a2,j.n的最小独立矩形存入tdc2,j（注意：当k=3时，对应的点集不包括被矩形1覆盖的点（1jn）。Tac1,j-1Tdc1,jTac2,j-1Tdc2,j为什么一定要考虑两个轴向为什么一定要考虑两个轴向, ,如果仅考虑一个轴向的话如果仅考虑一个轴向的话, ,有有什么反例什么反例? ?问题是面积和最小的两个独立矩形究竟取哪一个形态，区分两个矩形的分界线j为何值，我们无法确定。不得已，只能将所有可能的情况枚举出来。设varbest，now:longint；两个独立矩形的最小面积和、当前方案中两个独立矩形的面积和枚举过程如下：计算tac和tdc序列；bestmaxlongint；最小矩形面积初始化fori1to2dobegin依次分析x轴向和y轴向k=3时顺序寻找i轴向上第一个未被矩形1覆盖的点j；whilejndo枚举i轴向上所有可能的两个独立矩形，从中找出最佳方案begin记下i轴向上点j的坐标h；顺序寻找i轴向上最接近h点(k=3时，该点未被矩形1覆盖)的点j；if点j存在并且k=2，或者k=3时以点j为分界线的左矩形和右矩形与矩形1没有交集thenbeginnow(taci，j-1，1-taci，j-1，3)*(taci，j-1，2-taci，j-1，4)+(tdci，j，1-tdci，j，3)*(tdci，j，2-tdci，j，4)；则计算两个独立矩形的面积和ifnowbestthenbestnow；若面积和为目前最小，则记下end；thenend；whileend；forifbest=maxlongint若找不到的两个独立矩形then返回失败标志-1else返回两个矩形的最小面积和best；end；getans4 4、计算覆盖所有点的三个面积和最小的独立矩形、计算覆盖所有点的三个面积和最小的独立矩形、计算覆盖所有点的三个面积和最小的独立矩形、计算覆盖所有点的三个面积和最小的独立矩形我们先枚举第一个矩形，该矩形覆盖x轴向上的点1、点i、点j、点h（1in,ijn,jhn）,求出覆盖它们的最小矩形。该矩形的上边界、下边界、左边界和右边界分别记为bottom、top、left、right。显然其面积为(bottom-top)*(right-left)。我们将该矩形称为矩形1。那么，平面上还有哪些点未在矩形1内，这些点将被另外两个独立的矩形所覆盖。vv判断（判断（判断（判断（x,yx,y）是否在矩形是否在矩形是否在矩形是否在矩形1 1内的条件内的条件内的条件内的条件(xleft)and(xright)and(ybottom)and(ytop)vv判断矩形是否与矩形判断矩形是否与矩形判断矩形是否与矩形判断矩形是否与矩形1 1相交的条件相交的条件相交的条件相交的条件(min(x1,right)max(x2,left)and(min(y1,bottom)max(y2,top)我们在得出矩形1的基础上，直接调用上述算法计算与矩形1分开的另外两个独立矩形的面积和，加上矩形1的面积便是三个独立矩形的面积和。问题是矩形1究竟覆盖了哪些点才能得出最优解呢？我们无法得知。无奈之下，只能通过枚举法搜索所有的可能情况fori1tondo枚举x轴向上三个点（点i、点j、点h）的所有可能组合forjitondoforhjtondobegin计算覆盖点1、点i、点j、点h的最小矩形（矩形1）的四条边界right、bottom、left、top；now(bottom-top)*(right-left)；计算矩形1的面积计算未被矩形1覆盖的点集u；计算覆盖u且与矩形1不相交的两个独立矩形的最小面积和g；if(g0)and(g+now1)），则输出当前局的比分a：b。请注意，如果输入的字符为E，则标志比赛结束，11分制计算完毕；否则，继续读下一个字符，计算新一局的比分。然后，对当前输入行计算21分制下每一局比赛的比分。计算方法基本如上。有所不同的是，若华华得分a或者对方得分 b达 到 21分 且 双 方 的 分 数 差 值 大 于 1（ (a21)or(b21)and(abs(a-b)1)），则输出当前局的比分a：b。按照上述方法对每一输入行计算11分制和21分制的比赛结果，直至文件读完（eof(input)）为止。assign(input,inp); reset(input);输入文件读准备 assign(output,out);rewrite(output);输出文件写准备a:=0;b:=0;当前局双方的比分初始化whilenoteof(input)do若文件未读完，则循环beginwhilenoteoln(input)do若当前行处理完，则11分制的比赛结束beginread(ch);读一个字符casechof根据字符的种类分情形处理E:begin若比赛结束，则输出双方比分writeln(a,:,b);break;退出11分制的计算过程end;EW,L:begin华华或对方得一分ifch=Wtheninc(a)elseinc(b);if(a=11)or(b=11)and (abs(a-b)1) then若有一方得分达到11分且双方的分数差值大于1，则输出双方比分beginwriteln(a,:,b);a:=0;b:=0;新一局的比分初始化end;thenend;W,Lend;caseend;whilereadln;end;whilea:=0;b:=0;新一局的比分初始化writeln;reset(input);重新读输入行whilenoteof(input)do若文件未读完且比赛未结束，则循环beginwhilenoteoln(input)do若当前行处理完，则21分制的比赛结束beginread(ch);读一个字符casechof根据字符的种类分情形处理E:begin若比赛结束，则输出双方比分，退出21分制的计算过程writeln(a,:,b);break;end;EW,L:begin华华或对方得一分ifch=Wtheninc(a)elseinc(b);if(a=21)or(b=21)and(abs(a-b)1)若有一方得分达到21分且双方的分数差值大于1，则输出双方比分thenbeginwriteln(a,:,b);a:=0;b:=0;新一局的比分初始化end;thenend;W,Lend;caseend;whilereadln;end;whileclose(input);close(output);关闭输入文件和输出文件数字游戏（数字游戏（Game.pasGame.pas）丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如，对于下面这圈数字（n=4，m=2）：当 要 求 最 小 值 时 ， (2-1) mod 10)(4+3) mod10)=17=7，要求最大值时，为(2+4+3)mod10)(-1mod10)=99=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。【 输 入 格 式 】 输 入 文 件 第 一 行 有 两 个 整 数 ，n（1n50）和m（1m9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。【输出格式】输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。算法分析算法分析设圆周上的n个数字为a1、a2、an。按照模运算的规则（a1+a2+ak）mod10=(a1mod10+a2mod10+akmod10)mod10；gi，j为ai、ai+1、aj的数和对10的模，即gi，j=（ai+ai+1+aj）mod10显然gi，i=（aimod10+10）mod10gi，j=(gi,j-1+gj,j)mod10(1in，i+1jn)当m=1时，程序得到的最小值和最大值为g1,n；fmax1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后 再 相 乘 ， 最 终 得 到 最 大 数 。 显 然 ，fmax11,i,j=gi，j；fmin1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后 再 相 乘 ， 最 终 得 到 最 小 数 。 显 然 ，fmin11,i,j=gi，j；(1pm)问题是当ai、ai+1、aj划分成的部分数p大于1时，怎么办。我们采用动态程序设计的方法计算。设阶段p：划分成的部分数,2pm-1；状态（i，j）:将ai、ai+1、aj划分成p个部分，1in，ijn；决策k:将ai、ai+1、ak划分成p-1个部分，ak+1、aj为第p部分，ikj-1；显然，状态转移方程为fmin1p,i,j=fmin1p-1,i,k*gk+1,jfmax1p,i,j=fmax1p-1,i,k*gk+1,j2pm-1max=min=由于p-1阶段仅和p阶段发生联系，因此我们将p-1阶段的状态转移方程fmin1p-1,i,j设为fmin1i,j、fmax1p-1,i,j设为fmax1i,j，将p阶段的状态转移方程fmin1p,i,j设为fmini,j、fmax1p,i,j设为fmaxi,j。read(n,m);读数字个数和划分的部分数fillchar(fmax1,sizeof(fmax1),0);fillchar(fmin1,sizeof(fmin1),$FF);状态转移方程初始化fillchar(g,sizeof(g),0);fori:=1tondo依次读入每个数，一个数组成一部分beginread(gi,i);gi,i:=(gi,imodmask+mask)modmask;min1i,i:=gi,i;fmax1i,i:=gi,i;end;forfori:=1tondo计算一部分内的数和对10的模的所有可能情况forj:=i+1tondobegingi,j:=(gi,j-1+gj,j) modmask;fmax1i,j:=gi,j;fmin1i,j:=gi,j;end;forforp:=2tom-1do阶段：递推计算划分2部分m-1部分的结果值beginfillchar(fmax,sizeof(fmax),0);划分p部分的状态转移方程初始化fillchar(fmin,sizeof(fmin),$FF);fori:=1tondo状态：枚举被划分为p部分的数字区间forj:=itondofork:=itoj-1do决策：aiak被划分为p-1部分beginiffmax1i,k*gk+1,jfmaxi,j计算将ai、ai+1、aj划分成p个部分的状态转移方程thenfmaxi,j:=fmax1i,k*gk+1,j;if(fmin1i,k=0)and(fmin1i,k*gk+1,jfmini,j)or(fmini,j0)thenfmini,j:=fmin1i,k*gk+1,j;end;forfmin1:=fmin;fmax1:=fmax;end;formax:=0;min:=maxlongint;将a1、a2、an划分成m个部分的最大值和最小值初始化ifm=1计算n个数划分成一部分的最大值和最小值thenbeginmax:=g1,n;min:=g1,n;endthenelsefori:=1tondo将a1ai-1、aj+1an设为第m部分，计算最大值和最小值forj:=itondoif(i1)or(jn)thenbeginif(g1,i-1+gj+1,n)modmask*fmax1i,jmaxthenmax:=(g1,i-1+gj+1,n)modmask*fmax1i,j;if(fmin1i,j=0) and (g1,i-1+gj+1,n)modmask*fmin1i,jmin)thenmin:=(g1,i-1+gj+1,n)modmask*fmin1i,j;end;thenwriteln(min);writeln(max);输出最小值和最大值栈（栈（Stack.pasStack.pas）【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。【问题描述】宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2.将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）1113使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由123生成序列231的过程。（原始状态如上图所示）你的程序将对给定的n，计算并输出由操作数序列1，2，n经过操作可能得到的输出序列的总数。【输入格式】输入文件只含一个整数n（1n18）【输出格式】输出文件只有一行，即可能输出序列的总数目第一种解法第一种解法回溯法回溯法设total为输出序列的总数目；输出序列的尾指针为l,堆栈的栈首指针为tp，当前准备入栈的操作数为r。我们采用回溯法计算输出序列的总数目。状态（tp,l,r）：栈首指针，输出序列指针，当前准备入栈的操作数；边界条件和目标（r=n+1）：所有操作数入栈，即得到一个输出序列。此时，total+1，回溯；搜索范围：有两种操作v栈非空（tp0），则栈顶元素进入输出序列,递归子状态（tp-1,l+1,r）；v操作数序列的首元素入栈,递归子状态（tp+1,l,r+1）。proceduresearch（tp,l,r）;beginifr=n+1若得到一个输出序列，则输出序列的总数目+1，回溯thenbegintotal:=total+1;exit回溯end;theniftp0若栈非空，则栈顶元素进入输出序列,递归thensearch（tp-1,l+1,r）;search(tp+1,l,r+1);操作数序列的首元素入栈,递归end;search主程序调用search（0，0，1）后得出的total即为输出序列的总数目。第二种解法第二种解法计算计算Catalan数数对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态1，出栈设为状态0。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1n的顺序排列、入栈的操作数b大于等于出栈的操作数a(ab)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。在2n位二进制数中填入n个1的方案数为,不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2（n-m）-1位上有n-m个1和n-m-1个0。如若把后面这2（n-m）-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。显然，不符合要求的方案数为。由此得出输出序列的总数目=-=。=-=设fi，j为。我们按照下述方法计算Catalan数read(n);输入操作数的个数fillchar(f,sizeof(f),0);f1,1:=1;=1fori:=2to2*ndo递推beginfi,1:=i;forj:=2tondofi,j:=fi-1,j+fi-1,j-1;end;forwriteln(f2*n,ndiv(n+1);输出输出序列的总数目（即Catalan数）麦森数（麦森数（Mason.pasMason.pas）【问题描述】形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。任务：从文件中输入P（1000P3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）【 输 入 格 式 】 文 件 中 只 包 含 一 个 整 数P（1000P0do由低位向高位方向逐位分析p的每一个二进制位beginifpmod2=1then若p的当前二进制位为1，则连乘当前项，取乘积的后500位beginansans*l；end;thenp:=pdiv2;处理高一位计算计算ll2；end;whiledec(ans0);计算2p-1fori:=499downto0do按照50位数一行的格式输出2p-1的后500位数beginwrite(ansi);ifimod50=0thenwriteln;end;forNOIP2003提高组复赛试题提高组复赛试题神经网络神经网络【问题背景】人工神经网络（ArtificialNeuralNetwork）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。【问题描述】在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：神经元编号为1）图中，X1X3是信息输入渠道，Y1Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。如此在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。【输入格式】输入文件第一行是两个整数n（1n20）和p。接下来n行，每行两个整数，第i1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。【输出格式】输出文件包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零（大于零，处于兴奋状态）的输出层神经元状态，并且按照编号由小到大顺序输出！算法分析算法分析构造有权有向图构造有权有向图constflag=-10350634;非输入层的顶点标志值varn,i,j,m,x,y:integer;n为顶点数，m为边数g:array1.100,1.100oflongint;有向图,其中若gi,j=flag，则表明顶点i和顶点j间无边；否则gi,j为边（i,j）的权c,u,d:array1.100oflongint;ci、ui、di为顶点i的状态、阈值和出度。其中ci=flag，标志顶点i为非输入层的顶点exist:boolean;输出层中存在状态非零的顶点的标志read(n,m);读顶点数和边数fori:=1tondo有向图初始化forj:=1tondogi,j:=flag;fillchar(d,sizeof(d),0);出度序列初始化fori:=1tondo读入每个顶点的最初状态和阈值beginread(ci,ui);ifci=0thenci:=flag;标志非输入层的顶点end;forfori:=1tomdo读入每一条边的信息beginread(x,y);read(gx,y);读入第i条边的两个端顶点和权inc(dx);顶点x的出度+1end;for递归计算顶点递归计算顶点k的服从公式的服从公式根据顶点k的服从公式,我们依次枚举顶点k的每一个前驱顶点i(gikflag)。若顶点i处于非输入层（ci=flag），则递归计算ci。若前驱顶点I处于兴奋状态（ci0），则将ci*gi,k计入ck。由此得出计算过程proceduresearch(k:integer);递归计算顶点k的服从公式vari:integer;beginck:=-uk;顶点k的服从公式初始化fori:=1tondo枚举顶点k的每一个前驱顶点ifgikflagthenbeginifci=flagthensearch(i);若顶点k的前驱顶点i处于非输入层，则递归前驱顶点i的服从公式ifci0theninc(ck,ci*gi,k);若前驱顶点I处于兴奋状态，则累计顶点k的服从公式end;thenend;search主程序主程序fori:=1tondo递归计算每一个非输入层顶点的服从公式ifci=flagthensearch(i);exist:=false;输出层顶点的最后状态均为0fori:=1tondo枚举输出层中c处于兴奋状态的顶点，输出这些顶点的最后状态if(di=0)and(ci0)thenbeginwriteln(i,ci);exist:=true;输出层存在最后状态非0的顶点end;thenifnotexistthenwriteln(NULL);若输出层顶点的最后状态均为0，则输出NULL侦探推理侦探推理明明同学最近迷上了侦探漫画柯南并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！【输入格式】输入由若干行组成，第一行有二个整数，M（1M20）、N（1NM）和P（1P100）。M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。【输出格式】如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 CannotDetermine；如果程序判断出没有人可能成为罪犯，则输出Impossible。算法分析算法分析1、根据输入信息建立几张表、根据输入信息建立几张表name为名字表，其中namei为第i个同学的名字；sform为证言的来源，其中sformi为第i句证言中提供证言的同学序号；skind为证言的类型，其中skindi=sobj为证言的涉及的对象，其中sobji=（1ip）证言格式为“证言人名字：证明内容”。显然，输入的证言是否合法的条件是v证言人名字后存在一个：；v证言人名字在name表中存在；v证明对象在name表中存在；我们根据输入信息建立sform表、skind表和sobj表：readln(m,n,l);输入同学数、说谎的人数和证言的句数p:=0;sform表和skind表的指针初始化fori:=1tomdoreadln(namei);读每个同学的姓名fori:=1toldo逐句输入证言beginreadln(s);读第i句证言j:=pos(:,s);计算提供证言的同学姓名nam1和编号kifj=0thencontinue;name1:=copy(s,1,j-1);fork:=1tomdoifnamek=name1thenbreak;ifnamekname1thencontinue;inc(p);sfromp:=k;fork:=1tomdoifnamek=name1thenbreak;ifnamekname1thencontinue;inc(p);sfromp:=k;delete(s,1,j+1);whileslength(s)=dodelete(s,length(s),1);ifs=Iamguilty.将提供证言的同学编号k和证言类型记入sform表和skind表，日期或证明对象编号记入sobj表Thenskindp:=1;elseifs=Iamnotguilty.Thenskindp:=2;elseiflength(s)9thenifcopy(s,1,9)=Todayisthenbegindelete(s,1,9);skindp:=5;ifs=Monday.thensobjp:=1elseifs=Tuesday.thensobjp:=2elseifs=Wednesday.thensobjp:=3elseifs=Thursday.thensobjp:=4elseifs=Friday.thensobjp:=5elseifs=Saturday.thensobjp:=6elseifs=Sunday.thensobjp:=7elsedec(p);endthenelsebeginj:=pos(,s);计算证明对象的编号x，并记入sobj表ifj=0thencontinue;name1:=copy(s,1,j-1);forx:=1tomdoifnamex=name1thenbreak;ifnamexname1thencontinue;delete(s,1,j);ifs=isguilty.thenbeginskindp:=3;sobjp:=x;endthenelseifs=isnotguilty.thenbeginskindp:=4;sobjp:=x;end;thenend;elseend;for采用回溯法搜索罪犯采用回溯法搜索罪犯crime为罪犯的序号；week为当天的日期情况，其中weeki=f为诚信情况表，其中fi=；d为罪犯情况表，其中di=状状态态（k,remain）：k为待推理的同学序号；remain为目前允许说假话的人数边边界界km：所有同学已推理。在这种情况下，搜索所有证言，按照下述方法计算罪犯情况表d或日期情况表week。依次判断每一句证言，根据提供证言的同学的诚信情况来决定指认对象是否为罪犯或者当天的日期：v若第i句证言说得是“Iamguilty.”，则提供证言的同学是否为罪犯必须与他的诚信情况一致，即dsfromi不能为-fsfromi，否则矛盾（即当skindi=1时 ， 若 dsfromi=0或 者 dsfromi=fsfromi， 则dsfromi=fsfromi；v若第i句证言说得是“Iamnotguilty.”，则提供证言的同学是否为罪犯必须 与 他 的 诚 信 情 况 相 反 ， 即 当 skindi=2时 ， 若 dsfromi=0或 者dsfromi=-fsfromi，则dsfromi=-fsfromi；v若第i句证言说得是“XXisguilty.”，则定指认对象XX是否为罪犯必须与提供证言的同学的诚信情况一致，即当skindi=3时，若dsobji=0或者dsobji=fsfromi，则dsobji=fsfromi；v若第i句证言说得是“XXisnotguilty.”，则定指认对象XX是否为罪犯必须与提供证言的同学的诚信情况相反,即当skindi=4时，若dsobji=0或者dsobji=-fsfromi，则dsobji=-fsfromi）；v若第i句证言说得是“TodayisXX.”，则今天是否为星期xx必须与提供证言的同学的诚信情况一致，即当skindi=5时，若weeksobji=0或者weeksobji=fsfromi，则weeksobji:=fsfromi）；然后分析v若当天的日期不唯一（）或不确定的日期数为0，则回溯；v若确定罪犯的人数为一人（），且以前没有确定过罪犯或者当前确定的罪犯与以前确定的罪犯同属一人，则当前确定的罪犯成立；否则，输出罪犯不止一人的信息；v若不确定罪犯的人数为一人（）=1），该人是以前确定的罪犯，或者以前没有确定过罪犯，则该人确定是罪犯。否则输出罪犯不止一人的信息。搜索范围：搜索范围：同学k说假话和说真话两种情况v若剩余的人中必须有人说真话（remain0），则设定同学k说假话真话（fk=-1），递归子状态（k+1，remain-1）。procedure search(k,remain : integer);从同学k和允许说谎的人数remain出发，递归计算罪犯varic1,c0,f1,f0:integer;:beginifkmthen若所有同学已推理beginfillchar(d,sizeof(d),0);fillchar(week,sizeof(week),0);罪犯情况表和日期表初始化fori:=1topdo 枚举每一句证言caseskindiof根据第I句证言的类型分情形处理1:if(dsfromi=0)or(dsfromi=fsfromi)thendsfromi:=fsfromielseexit;判断“我是罪犯”的证言是否诚信2:if(dsfromi=0)or(dsfromi=-fsfromi)thendsfromi:=-fsfromielseexit;判断“我不是罪犯”的证言是否诚信3:if(dsobji=0)or(dsobji=fsfromi)thendsobji:=fsfromielseexit;判断“xx是罪犯”的证言是否诚信4:if(dsobji=0)or(dsobji=-fsfromi)thendsobji:=-fsfromielseexit;判断“xx不是罪犯”的证言是否诚信5: if (weeksobji=0) or (weeksobji=fsfromi) thenweeksobji:=fsfromielseexit;Todayisxx”的证言是否诚信end;casec1:=0;c0:=0;统计当天确定的日期数c1和不确定的日期数c2for i:=1 to 7 do if weeki=1 then inc(c1) else if weeki=0 theninc(c0);if(c11)or(c1+c0=0)thenexit;若确定的日期数大于1或不确定的日期数为0，则回溯c1:=0;c0:=0;统计确定是罪犯的人数c1和最后一个罪犯的编号f1fori:=1tomdoifdi=1thenbegininc(c1);f1:=i; endthenelseifdi=0统计未确定是罪犯的人数c0和最后一个未确定是罪犯的编号f0thenbegininc(c0);f0:=i; end;elseifc11thenexit 若确定是罪犯的人数大于一，则回溯elseifc1=1then 若仅确定一人为罪犯if(crime=f1)or(crime=0)thencrime:=f1若当前确定的罪犯与以前确定的罪犯同属一人，或者以前未确定过罪犯，则当前确定的罪犯成立；否则输出罪犯不止一人的信息elsegoexit(CannotDetermine)elseifc0=1then若当前未确定罪犯的人数为1人if(crime=f0)or(crime=0)thencrime:=f0若当前未确定罪犯的人与以前确定的罪犯同属一人，或者以前未确定过罪犯，则当前未确定罪犯的人确定为罪犯；否则输出罪犯不止一人的信息elsegoexit(CannotDetermine)elsegoexit(CannotDetermine);否则输出罪犯不止一人的信息exit;end;thenifremain0若剩余的人中必须有人说假话，则设定同学k说假话，递归子状态thenbeginfk:=-1;search(k+1,remain-1);end;thenend;search其中其中searchsearch过程中调用的子程序过程中调用的子程序goexitgoexit(s)(s)说明如下说明如下：proceduregoexit(s:string);输出s串并退出程序beginwriteln(s);close(input);close(output);关闭输入输出文件halt(0);退出程序end;goexit主程序主程序有了以上基础，不难得出主程序根据输入信息建立sform表、skind表和sobj表：crime:=0;罪犯编号初始化search(1,n);从同学1出发（允许n个人说假话）递归计算罪犯ifcrime0thenwriteln(namecrime)若罪犯存在，输出罪犯姓名elsewriteln(Impossible);否则输出无解信息close(input);close(output);关闭输入文件和输出文件加分二叉树加分二叉树【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分subtree的右子树的加分subtree的根的分数。若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree的前序遍历【输入格式】第1行：一个整数n（n30），为节点个数；第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。【输出格式】第1行：一个整数，为最高加分（结果不会超过4,000,000,000）；第2行：n个用空格隔开的整数，为该树的前序遍历。1、采采用用动动态态程程序序设设计计方方法法计计算算最最大大分值分值设fi,j顶点i顶点j所组成的子树的最大分值。若fi,j=-1，则表明最大分值尚未计算出。wayi,j顶点i顶点j所组成的子树达到最大分值时的根编号。i=j时，wayi,i:=I。由于问题没有明显的阶段特征，而是呈非线性的树形结构，因此我们采用后序遍历的顺序计算状态转移方程。functionsearch(l,r:integer):int64;递归计算fl,rvari:integer;now:int64;当前分值beginiflrthensearch:=1elsebeginiffl,r=flagthen若尚未计算出顶点l顶点r对应子树的最高分值fori:=ltordobegin枚举每一个可能的子根inow:=search(l,i-1)*search(i+1,r)+fi,i;计算以i为根的子树的分值ifnowfl,rthen若该分值为目前最高，则记入状态转移方程，并记下子根beginfl,r:=now;wayl,r:=i;end;thenend;forsearch:=fl,r;返回顶点l顶点r对应子树的最高分值end;elseend;search显然主程序可以通过递归调用search(1,n)计算最高分值。算法的时间复杂度为O(n3)2、输出加分二叉树的前序遍历、输出加分二叉树的前序遍历procedurewriteout(l,r:integer);前序遍历顶点l顶点r对应的子树beginiflrthenexit;iffirstwritethenfirstwrite:=falseelsewrite();顶点间空格分开write(wayl,r);输出子根writeout(l,wayl,r-1);前序遍历左子树writeout(wayl,r+1,r);前序遍历右子树end;writeout主程序主程序read(n);读顶点数fori:=1tondo状态转移方程初始化forj:=itondofi,j:=-1;fori:=1tondobeginread(temp);读顶点i的分值fi,i:=temp;wayi,i:=i;顶点i单独成一棵子树end;forwriteln(search(1,n);计算和输出最高加分firstwrite:=true;设立首顶点标志writeout(1,n);前序遍历二叉树writeln;传染病控制传染病控制【问题背景】近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究消楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。【问题描述】研究表明，这种传染病的传播具有两种很特殊的性质；第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断，则X就不会得病。第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。你的程序要针对给定的树，找出合适的切断顺序。【输入格式】输入格式的第一行是两个整数n（1n300）和p。接下来p行，每一行有两个整数i和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。其中节点1是已经被感染的患者。【输出格式】只有一行，输出总共被感染的人数。解法解法1贪心法贪心法在每个周期开始的时候，选择前一个周期感染病毒的节点的子节点中子孙节点个数最大的一个，断开该节点与父节点的边。这样的贪心算法对部分数据是正确的，但存在反例。例如下图。根的左子树是一条具有n1个节点的右链，它们分布在n1-1个周期；右子树有n2个节点的，这些节点在一个疾病传播周期内。按照贪心算法，自然是切断根与左儿子的边，这样做只能使一个患者避免感染。但按照使尽量少的人被感染的要求，应该切断根与右儿子的边，这样做可以使n2-1个患者避免感染。解法解法2搜索搜索1、输入边信息，构建有向树、输入边信息，构建有向树gli为顶点i的儿子数；gi，j为顶点i的第j个儿子序号。1in,1jgli；fi为顶点i的周期；ans为被感染的最少人数，now为当前被感染的人数；我们按照下述方式输入p条边的信息：read(n,m);读顶点数和边数fillchar(gl,sizeof(gl),0);顶点的度序列初始化fori:=1tomdobegin输入每一条边的信息read(x,y);读第I条边的两个端点inc(glx);gx,glx:=y;顶点x的度+1,x的新增边的另一端点为yinc(gly);gy,gly:=x;顶点y的度+1,y的新增边的另一端点为xend;for由于输入信息中并没有给出各条边的连接情况，因此必须从顶点1出发构造有向树。构造方法如下：proceduremaketree(k:integer);从根k出发，构造树vari,j,t:integer;beginfori:=1toglkdo枚举顶点k的每一个儿子begint:=gk,i;forj:=1togltdo删除顶点k的第I个儿子指向顶点k的有向边ifgt,j=kthenbreak;gt,j:=gt,glt;dec(glt);maketree(t);从顶点k的第I个儿子出发，继续递归end;forend;maketree在主程序中递归调用maketree（1），便可以得到有向树g。2、递归计算被感染的最少人数、递归计算被感染的最少人数我们采取搜索的办法，在每个周期开始的时候，枚举前一个周期感染病毒的节点的子节点，断开该节点与父节点的边。状态（now，f，k）：now为当前被感染的人数，f为每个顶点所在的周期，k为当前周期。K设为值参，now和f设为全局变量。边界条件nowans：若当前被感染的人数已超过最小值，则回溯；否则计算k周期内的每一个顶点的儿子数，累计被感染人数now搜索范围1in：搜索处于k+1周期内的每一个顶点（即fi=k+1），切断父顶点通向它的传播途径，递归k+1周期；proceduresearch(k:integer);搜索在第k个周期中被切断的传播途径vari,j:integer;found:boolean; 存在标志beginifnowansthenexit;若当前被感染的人数已超过最小值，则回溯found:=false;未发现被感染的顶点fori:=1tondo枚举在周期k被感染的顶点iffi=kthen若顶点I处于周期k，则枚举顶点I的每一个儿子forj:=1toglidobeginfgi,j:=k+1;顶点I的第j个儿子处于k+1周期inc(now);被感染的人数+1found:=true;发现处于周期k+1的顶点end;fordec(now);fori:=1tondoiffi=k+1通向顶点i的传播途径被切断thenbegini:=0;search(k+1);递 归 周 期 k+1fi:=k+1;end;theninc(now);恢复递归前的now和ffori:=1tondoiffi=k+1thenbeginfi:=0;dec(now);end;if(notfound)and(nowb)ab)依照由低位至高位（第1位至第la位）的顺序进行减法运算。在每一次位运算中，若出现不够减的情况（aibi），则向高位借位（dec(ai+1)，aiai+10）。在进行了la位的减法后，若最高位为零（ala=0），则a的长度-1。procedure minus(var a：atype；var la：integer；b：atype)；计算a=a-b，返回差a及其长度lavari：integer；begin for i1 to la do 逐位相减 begin if aibi 借位 then begin dec(ai+1)；aiai+10；end；then aiai-bi； 计算差的第i位 end；for while ala=0 do dec(la)； 计算差的实际长度end；minus3 3、乘法运算、乘法运算aa*c(aaa*c(a为为numtypenumtype类型，类型，c c为字节型为字节型) )按照乘法规则，从a的第1位开始逐位与c相乘。在第i位乘法运算中（1ila），a的i位与c的乘积必须加上i-1位的进位（i-1位的乘积除以10的整商），然后规整积的i-1位（取i-1位的乘积对10的余数）：procedure multiply(var a：numtype；c：byte)； var i：byte； begin a1 a1*c； 第1位初始化 for i2 to la do 逐位相乘 begin ai ai*c；ai ai+ai-1 div 10；ai-1 ai-1 mod 10 end；for while ala 10 do 积的最高位进位 begin lala+1；ala ala-1 div 10；ala-1 ala-1 mod 10 endwhileend； multiply 4 4、高精度除法、高精度除法 设a,b为除数和被除数，q和r为小数和余数序列，其中r0=0。按照除法规则逐位相除：若当前位hv的小数和余数与先前得出的某位i相同（(ri=rhv)and (qi=qhv)）,则说明除法成功。若i=0，则q1.qhv为小数；否则qi.qhv-1为循环节。上述过程一直进行到小数50位为止。readln(f,a,b);输入除数和被除数if b=0 then begin writeln(f0,Meaningless.); continue end;if a*b0计算和输出商的整数部分then begin write(-); a:=abs(a); b:=abs(b) end;write(f0,a div b);if a mod b=0 then exit；a:=a mod b; write(.);开始计算小数部分hv:=0; bn:=false;小数位数和循环节标志初始化r0:=0;第0位余数为0，除尽的比较标志while hv50 do begin计算小数和余数的当前位 inc(hv); qhv:=a*10 div b;rhv:=a*10 mod b;a:=rhv; i:=0;在小数和余数中寻找与当前位相同的位数i while (i=hv-1) and (rirhv) or (qiqhv) do inc(i);if i=hv-1若相同位存在或被除尽 then begin for j:=1 to i-1 do write(qj);输出循环节前的小数 if i0 then write(f0,);输出循环节 if i0 then for j:=i to hv-1 do write(qj) else for j:=1 to hv do write(qj);若第hv位小数和余数为0，则输出小数部分 if i0 then write();bn:=true; break成功标志 endend;if not bn then for i:=1 to 50 do write(qi);输出50位小数改善高精度运算的效率改善高精度运算的效率用一个整型数组来表示一个很大的数，数组中的用一个整型数组来表示一个很大的数，数组中的每一个数表示一位十进制数字。这种方法的缺点是，每一个数表示一位十进制数字。这种方法的缺点是，如果十进制数的位数很多，则对应数组的长度会很长，如果十进制数的位数很多，则对应数组的长度会很长，并增加了高精度计算的时间。改善高精度运算效率的并增加了高精度计算的时间。改善高精度运算效率的两种方法两种方法扩大进制数扩大进制数建立因子表建立因子表一、扩大进制数一、扩大进制数用一个用一个Longint记录记录4位数字是最佳的方案。那么这个数组就相当于一个位数字是最佳的方案。那么这个数组就相当于一个10000进制进制的数，其中每一个元素都是的数，其中每一个元素都是10000进制下的一位数。进制下的一位数。1、数据类型、数据类型typenumtype=array0.9999oflongint；整数数组类型，可存储整数数组类型，可存储40000位十进位十进制数制数vara，n:numtype；a和和n为为10000进制的整数数组进制的整数数组st：string；数串数串la，lninteger；整数数组整数数组a和和n的长度的长度2、整数数组的建立和输出、整数数组的建立和输出当输入数串当输入数串st后，我们从左而右扫描数串后，我们从左而右扫描数串st，以四个数码为一组，以四个数码为一组，将之对应的将之对应的10000进制数存入进制数存入n数组中。具体方法如下：数组中。具体方法如下：readln(st)；输入数串输入数串stklength(st)；取得数串取得数串st的长度的长度fori0tok-1dobegin把把st对应的整数保存到数组对应的整数保存到数组n中中j(k-i+3)div4-1；njnj*10+ord(sti+1)-48；end；forln(k+3)div4；当得出最后结果当得出最后结果a后，必须按照由次高位（后，必须按照由次高位（ala-2）到最底位到最底位（a0）的顺序，将每一位元素由的顺序，将每一位元素由10000进制数转换成进制数转换成10进制数，即进制数，即必须保证每个元素对应四位必须保证每个元素对应四位10进制数。例如进制数。例如ai=0015(0ila-2)，对应的对应的10进制数不能为进制数不能为15，否则会导致错误结果。我们按照如下方，否则会导致错误结果。我们按照如下方法输出法输出a对应的对应的10进制数：进制数：write(ala-1)；输出结果输出结果forila-2downto0dowrite(aidiv1000，(aidiv100)mod10，(aidiv10)mod10，aimod10)；3、介绍几个基本运算、介绍几个基本运算整数数组整数数组-1（nn-1，n为整数数组）为整数数组）我们从n0出发往左扫描，寻找第一个非零的元素（nj0，nj-1=nj-2=n0=0）。由于该位接受了底位的借位，因此减1，其后缀全为9999（nj=nj-1，nj-1=nj-2=n0=9999）。如果最高位为0（nln=0），则n的长度减1。j0；从n0出发往左扫描，寻找第一个非零的元素while(nj=0)doinc(j)；dec(nj)；由于该位接受了底位的借位，因此减1fork=0toj-1donk9999；其后缀全为9999if(j=ln-1)and(nj=0)thendec(ln)；如果最高位为0，则n的长度减1整数数组除以整数整数数组除以整数（aa/i，a为为整数数组，整数数组，i为整数为整数）我们按照由高位到底位的顺序，逐位相除。在除到第j位时，该位在接受了来自j+1位的余数（ajaj+(j+1位相除的余数)*10000）后与i相除。如果最高位为0（nln=0），则n的长度减1。l0；余数初始化forjla-1downto0dobegin按照由高位到底位的顺序，逐位相除inc(aj，l*10000)；接受了来自第j+1位的余数lajmodi；计算第j位的余数ajajdivi；计算商的第j位end；forwhile(ala-1=0)dodec(la)；计算商的有效位数两个整数数组相乘两个整数数组相乘（aa*n，a和和n为为整数数为为整数数组组）我们按照由高位到底位的顺序，将a数组的每一个元素与n相乘。当计算到aj*n时，根据乘法规则，aj-1，a0不变，aj为aj为aj与n0的乘积，aj+k加上aj*nk的乘积（k=ln-1，ln-2，1），然后按照由底位到高位的顺序处理进位。最后，如果ala-1*n有进位，则乘积a的有效位数为la+ln；否则a的有效位数为la+ln-1。forjla-1downto0dobegina1a*nforkln-1downto1doinc(a1j+k，aj*nk)；a1jaj*n0End;aa1；l0；进位初始化进位初始化forj0tola+ln-1dobegin按照由底位到高位的顺序处理进位按照由底位到高位的顺序处理进位inc(l，aj)；计算经过进位后的第计算经过进位后的第j位位ajlmod10000；将第将第j位规整为位规整为10000进制数进制数lldiv10000；计算进位计算进位end；forif(ala+ln-10)修改有效位数修改有效位数theninc(la，ln)elseinc(la，ln-1)；二、建立因子表二、建立因子表任何自然数都可以表示为n=p1k1*p2k2*ptkt的形式，p1，p2，pt为质因子。设num数组为自然数n，其中numi为因子i的次幂数(1ik)。显然，numk，numk-1，num2构成了一个自然数，该自然数可以用十进制整数数组ans存储。ans的计算过程如下ans01；将num转换为ansfori2tokdo枚举每一个因子forj1tonumidomultiply(ans，i)；连乘numi个因子imultiply的过程为高精度十进制运算中的乘法运算（ansans*I)有了自然数n的因子表num，可以十分方便地进行乘法或除法运算。例如整数x含有k个因子i，经过乘法或除法后，我们按照上述方法依次处理x的每一个因子，得出的num即为积或商procedure add(x， ob： longint)； ob=1， numnum*x； ob=-1，numnum/xvari：longint；Beginfori2toxdo搜索x的每一个因子iwhile(xmodi=0)do计算x含因子i的个数k。numi=begininc(numi，ob)；xxdivi；end；whileend；add显然，如果n1=x1*x2*xk，则可以通过连续调用add(x1，1)；add(x2，1)；add(xk，1)；得出n1对应的因子表num。如果n2=1/(x1,x2xk)，则可以通过连续调用add(x1，-1)；add(x2，-1)；add(xk，-1)；得出n2对应的因子表num。注意，初始时num数组清零。一、计算无向图的传递闭包一、计算无向图的传递闭包无向图的传递闭包主要用于计算图的连通性和图中满足条件的连通分支。借鉴传递闭包的思想，可计算每一对顶点间的最短路径。判别任两个顶点之间是否有路判别任两个顶点之间是否有路【例题】计算连通性问题【例题】计算连通性问题输入一张无向图，指出该图中哪些顶点对之间有路。输入：输入：n(顶点数，1n20)e(边数1e210)以下e行，每行为有边连接的一对顶点输出：输出：k行，每行两个数，为存在通路的顶点对序号i、j(ibest若k为目前最大，则记入best，i作为代表顶点记入bestithen begin bestk；bestii；end；if smax若s为目前最大，则记入max，i作为代表顶点记入maxkthen begin maxs；maxki；end； if k=n then break；若整个图为连通图，则退出 end；fordfs(besti)；从顶点besti出发，深度优先搜索含顶点数最多的连通分支dfs(maxk)；从顶点maxki出发，深度优先搜索顶点的权和最大的连通分支计算每一对顶点间的最短路径（计算每一对顶点间的最短路径（floydfloyd算法）算法）【例题】设计公共汽车线路【例题】设计公共汽车线路(1)现有一张城市地图，图中的顶点为城市，有向边代表两个城市间的连通关系，边上的权即为距离。现在的问题是，为每一对可达的城市间设计一条公共汽车线路，要求线路的长度在所有可能的方案里是最短的。输入：输入：n(城市数，1n20)e(有向边数1e210)以 下 e行 ， 每 行 为 边 （ i,j） 和 该 边 的 距 离 wij（1i,jn）输出：输出：k行，每行为一条公共汽车线路在枚举途径某中间顶点k的任两个顶点对i和j时，将顶点i和顶点j中间加入顶点k后是否连通的判断，改为顶点i途径顶点k至顶点j的路径是否为顶点i至顶点j的最短路径（1i，j，kn）。显然三重循环即可计算出任一对顶点间的最短路径。设n有向图的结点个数；path最短路径集合。其中pathi，j为vi至vj的最短路上vj的前趋结点序号(1i，jn)；adj最短路径矩阵。初始时为有向图的相邻矩阵用类似传递闭包的计算方法反复对adj矩阵进行运算，最后使得adj成为存储每一对顶点间的最短路径的矩阵Varadj：array1n，1nofreal；path：array1n，1nof0n；计算每一对顶点间最短路径的方法如下：adj矩阵的每一个元素初始化为；fori1tondo初始时adj为有向图的相邻矩阵，path存储边信息forj1tondoifwij0thenbeginadji，jwij；pathi，jj；endthenelsepathi，j0；fork1tondo枚举每一个中间顶点fori1tondo枚举每一个顶点对forj1tondoifadji，k+adjk，jadji，j若vi经由vk至vj的路径目前最优，则记下thenbeginadji，jadji，k+adjk，j；pathi，jpathk，j；end，then由矩阵path可推知任一结点对i、j之间的最短路径方案Procedureprint(i，j)；beginifi=jthen输出ielseififpathi，j=0then输出结点i与结点j之间不存在通路elsebeginprint(i，pathi，j)；递归i顶点至j顶点的前趋顶点间的最短路径输出j；end；elseend；print由此得出主程序距离矩阵w初始化为0；输入城市地图信息（顶点数、边数和距离矩阵w）；计算每一对顶点间最短路径的矩阵path；fori1tondo枚举每一个顶点对forj1tondoifpathi，j0若顶点i可达顶点j，则输出最短路径方案thenbeginprint（i，j）；writeln；end；then 二、二、 图的最小生成树图的最小生成树( (primprim算法算法) )对于一张图进行深度优先搜索或宽度优先搜索，可生成一棵深度优先搜索树或宽度优先搜索树。搜索的出发点不同，生成树的形态亦不同。在一张有权连通图中，如何寻找一棵各边权的总和为最小的生成树，就是本章节所要讨论的问题。【例题】设计公共汽车线路【例题】设计公共汽车线路(2)现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为公路造价。在分析了这张图后可以发现，任一对城市都是连通的。现在的问题是，要用公路把所有城市联系起来，如何设计可使得工程的总造价最少。输入：输入：n(城市数，1n20)e(有向边数1e210)以下e行，每行为边（i,j）和该边的距离wij（1i,jn）输出：输出：n-1行，每行为两个城市的序号，表明这两个城市间建一条公共汽车线路。设W带权连通图的相邻矩阵。t存储相邻矩阵W的下三角元素。其中t+j存 储 Wi， j(ji)。 t数 组 的 长 度 为 。 在 计 算 过 程 中 若 vi在 生 成 树 中 ， 则 t =1；若(i，j)边在生成树，则t+j取负。min当前待扩展边的最小权。我们从任意结点开始（不妨设为我们从任意结点开始（不妨设为v vn n）构造最小生成树：首先把这构造最小生成树：首先把这个结点包括进生成树里，然后在那些其一个端点已在生成树里、个结点包括进生成树里，然后在那些其一个端点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的一条边，并另一端点还未在生成树里的所有边中找出权最小的一条边，并把这条边、包括不在生成树的另一端点包括进生成树，把这条边、包括不在生成树的另一端点包括进生成树，。依。依次类推，直至将所有结点都包括进生成树为止。这种尽量找最次类推，直至将所有结点都包括进生成树为止。这种尽量找最小权的边扩展的策略即为贪心法。小权的边扩展的策略即为贪心法。readln(n)；输入城市数fori1todoti；fori1tondot0；所有结点未包括进生成树fori1to边数edo输入相邻矩阵的下三角元素begin读第i条边和该边的权wxy；ifxythentwxyelsetwxy；endfort1；vn进入最小生成树fork2tondo顺序构造最小生成树的n-1条边beginmin；fori1tondo搜索那些其一个端点已在生成树里、另一端点还未在生成树里的边ift=1若vi在生成树中thenbeginforj1tondoift=0若vj不在生成树中thenbeginifjithenl+j计算（i，j）元素在t中的位置elsel+i；if tlmin then 若el=的权目前最小，则记下begin mintl；pl；qj；end；thenend；thenend；thent1；tp-tp；vq和相连的权最小的边el加入最小生成树end；forfori2tondoforj1toi-1doift+jvm的距离值+Wmi），则要修改vi的距离（vi的距离值vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。设n图的结点数；adj有向图的相邻矩阵。其中dist最短路径集合。其中distipre在v0至vi的最短路径上，vi的前趋结点序号；distilengthv0至vI的最短路径长度，即vi的距离值；（1in）Constn=图的结点数；Typepath=record路径集合的结点类型length：real；距离值pre：0n；前趋结点序号end；varadj：array1n，1nofreal相邻矩阵dist：array1nofpath；路径集合计算单源最短路径的过程如下：fillchar(adj，sizeof(adj)，0)；建立相邻矩阵adjfori1tondoforj1tondoif（i，j）Ethenadji，jwijelseadji，j；fori1tondo路径集合初始化begindistilengthadjv0，i；ifdistilengththendistiprev0elsedistipre0；end；foradjv0，v01；源结点v0进入第一组repeatmin；u0；fori1tondo从第二组中找距离值最小的结点uif(adji，i=0)and(distilengthmin)then begin ui；mindistilength；end；thenifu0第二组中存在一个距离值最小的结点thenbeginadju，u1；结点u进入第一组fori1tondo修正第二组中u可达的结点距离值if(adji，i=0)and(distilengthdistulength+adju，i)thenbegindisti lengthdistu length+adju，i；distipreu；end；thenend；thenuntilu=0；算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi的最短路径：procedureprint(i：integer)；beginifi=v0then输出结点v0elsebeginprint(distipre)；输出结点i和v0至vi的最短路径长度distilength；end；elseend；print显然递归调用print1，printn后，可得知v0至所有结点的最短路径。由此得出主程序：输入城镇数n；输入出发城镇序号v0；输入城镇间的距离矩阵w；计算单源最短路径方案dist；fori1tondo枚举除v0外的其它城镇beginif(iv0)and(distilength)若城镇i与城镇v0间有通路，则输出它们之间的最短距离和路径方案thenbeginwrtiln(distilength)；print(i)；end；thenwrteln；end；for四、计算拓扑序列四、计算拓扑序列如何判断有向图中是否存在回路【例题】士兵排队【例题】士兵排队有n个士兵(1n26)，编号依次为A、B、C、。队列训练时，指挥官要把一些士兵从高到矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果（p1，p2AZ），记为p1p2。例如AB，BD，FD。士兵的身高关系下图所示对应的排队方案有三个：AFBD、FABD、ABFD。输入k行，每行为ab，表示ab输出排队方案分分析析：士兵的身高关系对应一张有向图，图中的顶点对应一个士兵，有向边表示士兵i高于士兵j。我们按照从高到矮将士兵排出一个线性的顺序关系，即为对有向图的顶点进行拓扑排序。拓拓扑扑序序列列的的定定义义：拓拓扑扑排排序序是是有有向向图图的的另另一一种种重重要要运运算算。给给出出有有向向图图G=(V，E)。若若顶顶点的线性序列点的线性序列v1，vn(viV，1in)满足如下条件：满足如下条件：vk至至vk+1有一条路径（有一条路径（kb，则ga，b1（即a向b引入一条有向边）；计算结点b的入度（即比士兵b高的人数）d(b)d(b)+1。显然最高士兵对应的结点入度为0：s；士兵名集合初始化while文件未输入完dobegin读ab信息；if(aAZ)and(bAZ)thenbeginss+a，b；计算士兵名集合ga，b1；构造有向边（a，b）dbdb+1；累计结点b的入度end；thenend；while然后通过下述方法计算士兵名字符集m和士兵人数km；fora=AtoZdoifasthenmm+a；klength(m)；接下来对有向图作拓扑排序。若图G中有回路，则排队方案不存在；否则拓扑序列n即为一个排队方案。拓扑排序的过程如下：n；拓扑序列n初始化为空fori：=1tokdo依次搜索每一个出列士兵beginj1；while(dmj0)and(jk)dojj+1；搜索第i个入度为0的结点序号jifjkthen若入度为0的结点不存在，则队列不存在最高的士兵，无解退出thenbegin输出失败信息；halt；end；thennn+mj入度为0的结点j进入拓扑序列namj；da；forj：=1tokdo删去结点jifga，mj0thendmjdmj-1；end；for输出拓扑序列n；五、五、 计算关键路径计算关键路径【例题】计算能影响整个计划完成时间的关键活动【例题】计算能影响整个计划完成时间的关键活动工厂的工程计划用一张有向图表示，有向图的结点表示事件，有向边表示活动，边上的权标明一项活动需要的时间。结点所表示的事件实际上就是它入边代表的活动均已完成，出边代表的活动可以开始这样一种状态。例如上图含12项活动、9个事件。其中事件v1表示开始时活动a1、a2、a3并行实施；事件v5代表活动a4、a5已经完成，活动a7、a8可以开始。V9表示整个计划完成。活动依事件的顺序要求进行。例如活动a4、a5、a6只有当事件v2、v3、v4分别发生后才能进行，而它们的完成又标志事件v5、v6的发生。当活动a10、a11、a12完成后，整个计划完成。上述有向图存在唯一的入度为0的开始结点v1，表明整个计划从该事件开始；存在唯一的出度为0的完成结点vn，表明该事件完成后，整个计划结束。现在的问题是，整个计划完成至少需要多少时间，为提前完成计划应该加快哪些活动的速度。输输入入：n(事件数，1n100)e(活动数，1e4000)。以下为e行，每行为连接两个事件的序号以及活动需要的时间输输出出：完成整个计划的最少时间。以下k行，每行为一个关键活动（i，j）和目前花费的时间wij，加快该活动的速度能提前完成计划关键路径的由来关键路径的由来如果有向图的结点表示活动，有向边表示活动间的优先关系，那么我们通过拓扑排序将图中的结点排成一个满足活动先后顺序要求的线性序列。如果有向有权图满足下述条件存在唯一的入度为0的结点和唯一的出度为0的结点；可通过拓扑排序将图中的结点排成一个满足活动先后顺序要求的线性序列（即有向图没有回路）则称该有向有权图为AOV网（活动结点网络）。利用AOV网可以估算出整个计划完成至少需要多少时间，为提前完成计划应该加快哪些活动的速度等问题。解决这些问题有一种有效的方法求关键路径方法。由于AOV网中的活动可以并行进行，因此完成整个计划的最少时间是从开始结点v1到完成结点vn的最长路径长度（路径上各边权的和）。具有最大长度的路径称作关键路径。在上图中v1v2v5v8v9是一条关键路径，长度为18。换句话说，整个计划至少需要18个时间单位完成。关键路径上的活动又称关键活动。如果不能按期完成这些活动会贻误整个计划。找出关键活动后就可以适当调度，集中力量于关键活动，以保证计划如期或提前完成。关键路径的计算关键路径的计算为了找出关键活动，我们先定义几个变量：nAOV网的结点数；mAOV网的有向边数；eeivi事件可能发生的最早时间，即从开始结点v1至结点vi的最长路径长度；lei在保证完成结点vn所代表的事件在een时刻发生的前提下，事件vi允许发生的最晚时间，即lei=ee(n)-vi至vn最长路径长度；ek活动ak（对应边）可能的最早开始时间，即等于事件vi的可能的最早发生时间eei；lk活动ak(对应边)允许的最晚完成时间，即等于事件vj允许最晚发生时间lej；(1i，jn，1km)显然活动ak的最大可利用时间是lk-ek。若最大可利用时间等于ak边所带的权wk(即为计划时间)，则ak是关键活动。ak延期，则整个计划将顺延。若最大可利用时间大于wk，则ak不是关键活动，ak的完成时间允许超过wk。只要不超过最大可利用时间，无妨于整个计划完成的进度。我们可以采取以下步骤，计算上面定义的几个变量值，从而找到关键活动：计算能影响整个计划完成时间的关键活动计算能影响整个计划完成时间的关键活动在找出关键活动后，只要将所有的非关键活动从AOV网中去掉，这时从开始结点至完成结点的所有路径都是关键路径。AOV网中的关键路径可能不止一条。并并不不是是加加快快任任一一关关键键活活动动就就可可以以缩缩短短整整个个计计划划的的完完成成时时间间。只只有有加加快快那那些包括在所有关键路径上的关键活动才能达到目的的。些包括在所有关键路径上的关键活动才能达到目的的。设a为关键路径组成的01矩阵，a0为辅助矩阵；b为关键活动序列，其中bk.x、bk.y和bk.l分别为第k项关键活动的两个顶点序号和花费；nopath为v1至vn间有路可走的标志；首先计算关键活动序列b和关键活动组成的有向图a。然后逐一地在a图中去除一条关键活动边，看一看是否存在v1至vn的路径。如果v1至vn间无路可走,则说明这个关键活动为影响整个计划完成的关键活动。判别过程采用深度优先搜索proceduredfs(i:integer)；深度优先搜索a0图中由顶点i出发的所有可能路径。若存在一条到达顶点n的路径，则nopath设为false；否则为truebeginfitrue；ifi=nthenbeginnopathfalse；exit；endthenforj1tondobeginif(not(fj)and(a0i,j=1)thendfs(j)；end；forend；dfs由此得出算法活动的时间矩阵w初始化为0；输入带权有向图的信息（顶点数n、活动数e和活动的时间矩阵w）；if图中的所有顶点不能排成一个拓扑序列then失败退出；fillchar(ee，sizeof(ee)，0)；fori1ton-1doforj1tondo计算各个事件的最早发生时间表eeif(i,j)E)and(eejeei+wij)theneejeei+wij；输出完成整个计划的最少时间een；fori1tondoleieen；所有事件的最晚发生时间初始化k0；关键活动数初始化forin-1downto1do计算各个事件的最晚发生时间表leforj1tondoif(wij0)and(leilej-wij)thenleieej-wij；fillchar(a,sizeof(a),0)；由关键活动组成的有向图a初始化fori1ton-1do计算关键活动和由关键活动组成的有向图aforj1tondoif(wij0)and(lej-eei=wij)thenbeginkk+1；bk.xi；bk.yj；bk.lwij；ai,j1；end；thenfort1tokdo枚举每一个关键活动Begina0a；a0bt.x，bt.y0；在有向图a中去除第t个关键活动fillchar(f，sizeof(f)，false)；nopathtrue；访问标志和成功标志初始化dfs(1)；通过深度优先搜索判断v1与vn间是否有路ifnopaththen输出关键活动（bt.x，bt.y）和目前花费bt.l；end；for由上可见，影响整个计划完成的关键活动为所有关键路径共用的边，这些公共边称之为“桥”。寻找“桥”的方法很多，我们给出的方法仅是其中的一种，虽然思路比较简单，但时间效率并不高（O(k*n2)）。关于更高效的算法，可参阅有关图论的书籍。枚举法枚举法枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：可预先确定每个状态的元素个数n；状态元素a1，a2，an的可能值为一个连续的值域。设ai1状 态 元 素 ai的 最 小 值 ； aik状 态 元 素 ai的 最 大 值 (1in)， 即 a11a1a1k，a21a2a2k，ai1aiaik，an1anankfora1a11toa1kdofoa2a21toa2kdoforaiai1toaikdoforanan1toankdoif状态(a1，ai，an)满足检验条件then输出问题的解；枚举法的优点：枚举法的优点：由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。一、一、“直译直译”的枚举算法的枚举算法跳远跳远在水平面上整齐的放着n个正三角形，相邻两个三角形的底边之间无空隙，如左图所示。一个小孩子想站在某个三角形i的顶端，跳到三角形j的顶端上(ij)。他总是朝着斜向45度的方向起跳，且初始水平速度v不超过一个给定值v0。在跳跃过程中，由于受到重力作用（忽略空气阻力），小孩子将沿着抛物线行进，水平运动方程为x = x0 + vt，竖直运动方程为y = y0 + vt 0.5gt2，运动轨迹是一条上凸的抛物线。取g=10.0，(x0， y0)是起跳点坐标。请编程求出他从每个位置起跳能到达的最远三角形的编号。注意：跳跃过程中不许碰到非起点和终点的其他三角形。输入输入第一行为两个正整数n，v0(3n10， 1v0100)，表示三角形的个数和最大水平初速度。第二行有n个正整数li(1li20)，表示从左到右各个三角形的边长。输出输出输出仅一行，包括n-1个数，表示从三角形1，2，3n-1的顶点出发能到达的最右的三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0。状态：起跳点i和i点后的点j。每个状态元素的取值范围：1in-1，i+1jn 约束条件的分析：判断小孩能否从i点跳到j点的方法如下：设起点和终点间的水平距离为l、垂直距离为h。则由物理知识（已在题目中给出）有：t = l / vh = vt 5t2 = l 5* 。因此，v = sqrt(5*l*l/ (l - h)。当然，这个v不一定符合要求，它需要满足两个条件。 它不能大于极限速度v0，即必须有v v0 跳跃过程中不得碰到其他三角形。如何判断顶点k是否在抛物线下呢？我们可以算出到达时间t0 = dx / v（其中dx为起点到顶点k的水平坐标增量），然后算出该时刻的竖直坐标增量vt0 0.5t02。如果此增量大于起点到顶点k的竖直坐标增量，则抛物线在上方。只有起点和终点之间任何一个三角形的顶点不在抛物线下方，则跳远不能完成。我们在枚举过程中不断将小孩所能跳到的点j调整为best。 枚举结束后，best即为试题要求的最远点。var len ： array1 . 20 of longint； x， y ： array1 . 20 of double；三角形顶端顶点的坐标序列 l， h， t， v， v0 ： double； ok ： boolean；跳跃成功标志 i， j， k， n， best ： integer；begin read(n， v0)；输入三角形的个数和最大水平初速度 for i 1 to n do read(leni)；入从左到右各个三角形的边长 x1 len1 / 2；计算每一个三角形顶端顶点的坐标 y1 len1 * sqrt(3) / 2； for i 2 to n do begin xi xi - 1 + leni - 1 / 2 + leni / 2； yi leni * sqrt(3) / 2； end；forfor i 1 to n - 1 do依次计算每一个三角形所能到达的最远点 begin best 0；从三角形i出发能到达的最右的三角形编号初始化 for j i + 1 to n do依次枚举右方的每一个三角形 begin l xj - xi；计算三角形i与三角形j的两个顶端顶点的水平距离和垂直距离 h yj - yi； if l v0 then break；若大于极限速度v0，则无法从三角形i起跳 ok true； for k i + 1 to j - 1 do判断跳跃过程中是否碰到其他三角形begin t (xk - xi) / v；计算到达三角形k的时间 if (v * t - 5 * t * t) - (yk - yi) best then bestsum；这个算法相当粗糙，枚举状态的费用为O（n9）2 2、从减少重复计算入手从减少重复计算入手记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。forx11tondo枚举所有可能的水平面forx21tondofory11tondofory21tondoforz11tondo枚举上平面的z轴坐标beginsum0； 长方体的体积初始化forz21tondo枚举下底面的z轴坐标考察状态（x1，y1，z1，x2，y2，z2）； end；for考察过程改为 forxx1tox2do计算长方体的体积foryy1toy2dosumsum+mapx，y，z2； if sumbest then bestsum； 调整最优解由于利用了计算出的结果，整个算法的时间复杂度降为O（n8）。3 3、提取恰当的信息、提取恰当的信息上述考察实际上求出z轴坐标为z2的平面中矩形（x1，y1，x2，y2）的数和。我们将这个数和记为value(a) value(A) =value(ABCD)+value(B)-value(BC)-value(BD)这就启发我们用另一种方法表示立方体的信息：设recx，y，z表示z轴坐标为z的水平面中矩形（1，1，x，y）的数和。z轴坐标为z的水平面中左上角为（x1，y1）、右下角为（x2，y2）的矩阵的数和为recx2，y2，z+ recx1，y1，z-recx2，y1，z-recx1，y2，zRec数组可以在输入数据的同时计算fillchar(rec，size(rec)，0)；rec数组初始化forz1tondo逐层输入信息forx1tondo逐行输入z平面的信息beginfory1tondo逐列输入z平面上x行的信息begin read(mapx，y，z)； 输入z平面上（x,y）中的数 if (x=1)and(y=1) 计算z平面上以（1，1）为左上角、（x,y）为右下角的矩形的数和then rec1，1，zmap1，1，zelse if y=1 then recx，y，zrecx-1，n，z+mapx，y，z else recx，y，zrecx，y-1，z+mapx，y，z； end；for readln； end；for这样，考察过程就可以改为 sumsum+recx2，y2，z2+recx1，y1，z2-recx2，y1，z2-recx1，y2，z2； if sumbest then bestsum；时间复杂度降为O（n6）。如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的z轴坐标即可。设total(z)以z轴坐标为z的平面为下底面的长方体的最大数和total(z)=forx11tondo枚举所有可能的子平面forx21tondofory11tondofory21tondobegintotal0；长方体b（该长方体的平面以（x1,y1）为左上角、（x2,y2）为右下上角）的最大数和初始化 forz1tondo枚举长方体b下底面的z轴坐标begintotalmaxtotal，0+recx2，y2，z+recx1-1，y1-1，z-recx2，y1-1，z-recx-1-1，y2，z；计算以z为下底面的长方体b的最大数和iftotalbestthenbesttotal； 调整最优解end；for end；for这一改进使得考察的状态整数降为n5，回溯法回溯法回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。procedurerun（当前状态）；vari：integer；beginif当前状态为边界thenbeginif当前状态为最佳目标状态then记下最优结果；exit；回溯end；thenfori算符最小值to算符最大值dobegin算符i作用于当前状态，扩展出一个子状态；if(子状态满足约束条件)and(子状态满足最优性要求)thenrun(子状态)；end；forend；run我们在应用回溯法求所有路径的算法框架解题时，应考虑如下几个重要因素：定定义义状状态态：即如何描述问题求解过程中每一步的状况。为了精简程序，增加可读性，我们一般将参与子结点扩展运算的变量组合成当前状态列入值参，以便回溯时能恢复递归前的状态，重新计算下一条路径；边边界界条条件件：即在什么情况下程序不再递归下去。如果是求满足某个特定条件的一条最佳路径，则当前状态到达边界时并非一定意味着此时就是最佳目标状态。因此还须增加判别最优目标状态的条件；搜搜索索范范围围：在当前状态不满足边界条件的情况下，应如何设计算符值的范围。换句话说，如何设定for语句中循环变量的初值和终值。约约束束条条件件和和最最优优性性要要求求：当前扩展出一个子结点后应满足什么条件方可继续递归下去；如果是求满足某个特定条件的一条最佳路径，那么在扩展出某个子状态后是否继续递归搜索下去，不仅取决于子状态是否满足约束条件，而且还取决于子状态是否满足最优性要求。参参与与递递归归运运算算的的参参数数：将参与递归运算的参数设为递归子程序的值参或局部变量。若这些参数的存储量大（例如数组）且初始值需由主程序传入，为避免内存溢出，则必须将其设为全局变量，且回溯前需恢复其递归前的值。构造字串构造字串 生成长度为n的字串，其字符从26个英文字母的前p(p26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时 a b C b a满足条件 a b C b C不满足条件输入：输入：n，p输出输出：所有满足条件的字串分析分析状状态态：待扩展的字母序号at。实际上字串s亦参与了递归运算，但是由于该变量的存储量太大，因此我们将s设为全局变量； 边界条件和目标状态：边界条件和目标状态：产生了一个满足条件的字串，即at=n+1； 搜索范围：搜索范围：第at位置可填的字母集a. chr(ord(a)+p-1)； 约束条件：约束条件：当前字串没有相邻子串相等的情况var n，p：integer；字串长度和可选字母的个数 tl：longint； 满足条件的字串数 ed：char； 可选字母集中的最大字母 s：string； 满足条件的字串procedure solve(at：integer)；递归扩展第at个字母 var ch：char； i：integer； begin if at=n+1 若产生了一个满足条件的字串，则输出，满足条件的字串数+1 then begin writeln(f，s)； inc(tl)；exit回溯 end；then for cha to ed do 搜索每一个可填字母 begin ss+ch；i1；检查当前字串是否符合条件 while(i=atdiv2)and(copy(s，length(s)-i+1， i)copy(s， length(s)-2*i+1， i) do inc(i)； if iat div 2 then solve(at+1)；若当前字串符合条件，则递归扩展下一个字母 delete(s，length(s)，1)恢复填前的字串 endforend；solvebegin readln(n，p)；输入字串长度和前缀长短 edchr(ord(a)+p-1)；计算可选字母集中的最大字母 s； tl0；满足条件的字串初始化为空，字串数为0 solve(1)；从第1个字母开始递归计算所有满足条件的字串 writeln(Total：，tl)；输出满足条件的字串数 end.main回溯法的优化回溯法的优化1、1、递归前对尚待搜索的信息进行预处理递归前对尚待搜索的信息进行预处理如果搜索对象是通过某种运算直接得出其结果的，那么搜索前一般需进行预处理通过相应运算将所有搜索对象的计算结果置入常量表，搜索过程中只要将当前搜索对象的结果值从常量表取出即可。这样可以显著改善搜索效率。否则，在搜索过程中每遇到这些对象都要计算，则会产生大量的重复运算。2、记忆化搜索、记忆化搜索如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索的基本思想。序关系计数问题序关系计数问题用关系和=将3个数a、b和C依次排列有13种不同的关系：abC，ab=C，aCb，a=bC，a=b=C，a=Cb，baC，ba=C，bCa，b=Ca，Cab，Ca=b，Cb1p1），则则马马只只能能跳跳到到形形似似（p*sp*s，p*tp*t）的的格格子上，其他的格子都到达到不了。子上，其他的格子都到达到不了。 第第2 2种种情情况况：若若n+mn+m是是偶偶数数，类类似似于于1*1*n n马马的的情情况况，马马只只能能在在同同色色的的格格子子内内跳跳动动，不不能遍历棋盘。能遍历棋盘。 第第3 3种种情情况况：若若n+mn+m为为奇奇数数且且n n，m m互互质质。不不妨妨设设n n为为奇奇数数，那那么么m m为为偶偶数数。因因为为1*1*n n马马的的问问题题已已经经被被彻彻底底解解决决，所所以以很很自自然然的的想想将将n*mn*m经经过过一一系系列列变变换换转转化化成成1*1*n n马马的的问问题题。我们可以看到马的跳法本质上是我们可以看到马的跳法本质上是4 4种（另种（另4 4种可以看成是以下种可以看成是以下4 4种跳法反跳一步）：种跳法反跳一步）： （m m，n n） （m m，-n-n） （n n，m m） （n n，-m-m）马经过跳马经过跳p p次次、q q次次、r r次次、s s次次后后水平方向的位移为（水平方向的位移为（p+qp+q）*m+*m+（r+sr+s）*n *n 竖直方向的位移为（竖直方向的位移为（p-qp-q）*n+*n+（r-sr-s）*m*m为了利用为了利用1*1*n n马的结论，解不定方程（马的结论，解不定方程（p+qp+q）*m+*m+（r+sr+s）*n=1*n=1。nn，m m互质。互质。该方程一定有解（该方程一定有解（p p0 0，q q0 0，r r0 0，s s0 0）。）。又又m m是偶数是偶数n n是奇数。是奇数。（r r0 0+s+s0 0）是奇数。是奇数。马马要要遍遍历历整整个个棋棋盘盘，其其竖竖直直和和水水平平方方向向前前进进的的步步数数之之和和（p p0 0+q+q0 0）*m+*m+（r r0 0+s+s0 0）*n+*n+（p p0 0- -q q0 0）*n+*n+（r r0 0-s-s0 0）*m*m为奇数为奇数,（p p0 0-q-q0 0）是偶数。是偶数。（p p0 0-q-q0 0）*n+*n+（r r0 0-s-s0 0）*m*m是偶数。是偶数。也也就就是是马马通通过过一一系系列列的的跳跳动动所所得得到到的的效效果果相相当当于于1*1*lenlen的的马马跳跳一一步步的的效效果果（lenlen= =（p p0 0-q-q0 0）*n+*n+（r r0 0-s-s0 0）*m*m）。根根据据前前面面的的结结论论，1*1*lenlen的的马马可可以以遍遍历历整整个个棋棋盘盘，所所以以当当n+mn+m为为奇奇数数且且n n，m m互质时，互质时，n*mn*m的马可以遍历整个棋盘。算法的时间复杂度为的马可以遍历整个棋盘。算法的时间复杂度为W(1)W(1)，空间需求为空间需求为W(1)W(1)。varn，m，temp：longint； n，m为广义马的类型function gcd(a，b：longint)：longint；计算n和m的最大公约数begin if b=0 then gcda else gcdgcd(b，a mod b)；end； gcd beginreadln(n，m)； 读广义马的类型if(n+m)mod2=0 若n+m偶数，则无解then writeln(ImPOSSIbLE) else begin if nm，若不满足，则交换n，m tempn；nm； mtemp； end；thenif gcd(n，m)=1若n，m互质，则输出成功信息；否则输出失败信息 then writeln(YES) else writeln(ImPOSSIbLE)；end；elseend.main Dr. Steven最近在研究一种叫作X数列的整数数列。X数列有两个独特的性质：它的首项是0，任意相邻两项的差是1或者-1。Dr. Steven正在研究X数列的长度与它的各项之和之间的关系。你是他的一名学生，也参加了这个课题。为了研究的方便，他希望你能够编一个程序：从输入文件中读入X数列的长度、X数列中所有项的和，找一个满足要求的X数列，并把结果写到输出文件中。输入：输入：输入文件Sum.in的第一行是一个整数n(1n10 000)，表示X数列中的项数。第二行是一个整数S（|S| 50 000 000），表示X数列中所有项的和。输出：输出： 把找到的满足要求的X数列输出到文件Sum.out中，每一项占一行，第k项输出在第k行，共n行。如果不存在这样的X数列，则输出“nO”。X X数列的和（数列的和（Sum of X-SequenceSum of X-Sequence）长长度度为为n n的的X X数数列列共共有有2 2n-1n-1个个，要要全全部部枚枚举举一一遍遍是是不不现现实实的的。所所以以，一一定定有有更更好好的的方方法法。这这就就需需要要我我们们对对题题目目作作进进一一步步的的研研究究。只只要要做做适适当当的的变变换换，其其中中的的奥奥秘秘就就会会浮浮出出水水面。面。我们假设存在这样的一个数列我们假设存在这样的一个数列 a ai i 满足题目要求，讨论满足题目要求，讨论S S应满足的条件。应满足的条件。令令 b bi i= =a ai i+1+1- -a ai i， 则则 由由 题题 目目 知知 ， b bi i=1=1或或 -1-1。 且且 a a1 1=0=0， a a2 2=b=b1 1， a a3 3=b=b1 1+b+b2 2， ，a an n=b=b1 1+b+b2 2+b bn n-1-1。所所以以S=aS=a1 1+a+a2 2+ +a+an n=0+b=0+b1 1+(b+(b1 1+b+b2 2)+)+(b+(b1 1+b+b2 2+ + +b bn n-1-1)=(n-)=(n-1)b1)b1 1+(n-2)b+(n-2)b2 2+ +2*+2*b bn n-2-2+ +b bn n-1-1 （1 1）易知易知| |S|S| (n-1)+(n-2)+1=(n-1)*n/2(n-1)+(n-2)+1=(n-1)*n/2。1+2+1+2+(n-1)=(n-1)*n/2 +(n-1)=(n-1)*n/2 （2 2）由由(2)(2)式式-(1)-(1)式式得得：( (n-1)*n/2-S=(n-1)*(1- n-1)*n/2-S=(n-1)*(1- b b1 1)+(n-2)*(1- )+(n-2)*(1- b b2 2)+)+2*(1- +2*(1- b bn n- -2 2)+(1- )+(1- b bn n-1-1) )因因为为1-1-b bk k=0=0或或2 2，所所以以上上式式右右端端为为偶偶数数。要要使使等等式式成成立立，则则其其左左端端也也为为偶偶数数，即即S S与与( (n-1)*n/2n-1)*n/2同奇偶。同奇偶。再再把把等等式式两两边边同同除除以以2 2，令令c ci i=(1-b=(1-bi i)/2)/2（易易知知c ci i=0=0或或1 1），得得(n-1)*n/2-S/2=(n-1) n-1)*n/2-S/2=(n-1) c c1 1+(n-2) c+(n-2) c2 2+ 2*+ 2*c cn n-2-2+ + c cn n-1-1令令T=(n-1)*n/2-S/2T=(n-1)*n/2-S/2所所以以原原问问题题转转化化为为一一个个简简单单的的数数学学问问题题：T能能否否表表示示成成1，2，（n-1）中中若干个不重复的数之和。若干个不重复的数之和。这这个个问问题题不不难难解解决决。当当0 0 T T (n-1)*n/2(n-1)*n/2时时，T T能能够够表表示示成成1 1，2 2，（n-1n-1）中中若若干干个个不不重重复复的数之和。问题转化的必要性是显然的。接着用数学归纳法来证明它的充分性。证：的数之和。问题转化的必要性是显然的。接着用数学归纳法来证明它的充分性。证：(1)(1)当当n=1n=1时，时，0 0 T T 0 0，0=00=0。当当n=2n=2时，时，0 0 T T 1 1，0=00=0，1=11=1。当当n=3n=3时，时，0 0 T T 3 3，0=00=0，1=11=1，2=22=2，3=1+23=1+2。均成立。均成立。(2)(2)当当n=kn=k（k k 3 3）时，归纳假设成立。则当时，归纳假设成立。则当n=k+1n=k+1时：时：若若0 0 TkTt) 判断S是否在-(n-1)*n/2， (n-1)*n/2的范围内，且S是否与(n-1)*n/2同奇偶 then writeln(nO) else begin t(t-s)div2；令T=(n-1)*n/2-S/2 a0；首项为0 writeln(a)； for in-1 downto 1 do begin 逐项计算 if t=i c=1，即aj=aj-1-1 then begin dec(t，i)；dec(a) endthenelse inc(a)；c=0，即aj=aj-1+1 writeln(a) 输出数列中的一项 end；forend；elseend.main2 2、统计分析法、统计分析法：我们在一时得不到事物的特征机理的情况下，通过某种方法测试得到一些数据（即问题的部分解），再利用数理统计知识对数据进行处理，从而得到最终的数学模型极值问题极值问题m，n为整数，且满足下列两个条件：m，n1，2，3，k(1k109)；(n2-mn-m2)2=1。由键盘输入k，求一组满足上述两个条件的m，n并且使m2+n2的值最大。K2348163264N2338132155M122581334如果我们的猜想正确，那么当(n，m)是方程(n2-mn-m2)2=1的一组解时，根据斐波拉契数列关系，(n+m，n)也一定是方程的一组解。若(n+m)2-(m+n)n-n2)2=1成立，则=(n2+(m+n)n-(n+m)2)2=1=(n2+mn+n2-n2-2mn-m2)2=1=(n2-mn-m2)2=1成立以上各步可逆，所以当(n，m)是方程(n2-mn-m2)2=1的一组解时，(n+m，n)一定是方程的另一组解。varm，n，next，k:longint；beginwrite(k=)；readln(k)；读入读入n和和m的上限的上限kif(k1000000000)thenhalt；如果如果k不在要求范围内，就终止不在要求范围内，就终止m1；n1；nextm+n；确定斐波拉契数列的头三项确定斐波拉契数列的头三项whilenextythenbegincy；yx；xc；end； 按照递增顺序排列x和y if x=y div 1.618 then writeln(0)若x和y接近黄金分割数，则失败；否则胜利 else writeln(1)； 最短路径问题最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiSx为城市x到城市E的最短路径长度（x表示任意一个城市）；mapi，j表示i，j两个城市间的距离，若mapi，j=0，则两个城市不通；思路：由后往前依次推出每个思路：由后往前依次推出每个DisDis值，直到推出值，直到推出DisDisa a为止。为止。所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市i和城市j不连通或者disi+mapi，jdisj”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Disimapi，jDisj，则说明城市j至城市E的最短路径长度应该比Disj更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系diskx=dis4E=0 k=4，3，0，其中diskx指k阶段的城市x。由此得出程序disE0；fork3 downto 0 do for x取遍k阶段的所有城市dobegindisx；fory取遍k+1阶段的所有城市doifdisy+mapx,y0)and(mapk，b0)Then如果a与k，k与b均可达if(mapa，b=0)or(mapa，bmapa，k+mapk，b)Then如果a、b不可达，或者a、b之间的路径不如a-k-b这条路径短，则改变mapa，b的值 mapa，bmapa，k+mapk，b；注：mapa，b为从a到b的最短路的距离，如果a，b不可达，则mapa，b=0。这个解题方法实质上就是一个动态程序设计方法。它是以最短路中间结点的取值来划分阶段的,第k个阶段为所有最短路的中间结点k时的情况。而第k个阶段只与前(k-1)个阶段有关系，所以，这个问题同时满足“无后效性”与“最优子问题”这两个性质，采用动态程序设计方法是正确的。双重动态程序设计是在floyd-Warshall算法的基础是提出来的。城市交通城市交通某城市有n（1n50）个街区，某些街区由公共汽车线路相连，如在下图中，街区1，2有一条公共汽车线路相连，且由街区1至街区2的时间为34分钟。由于街区与街区之间的距离较近，与等车时间相比可忽略不记，所以这个时间为两趟公共汽车的间隔时间，即平均的等车时间。由街区1至街区5的最快走法为1-3-5，总时间为44分钟。现在市政府为了提高城市交通质量，决定加开m(1m10)条公共汽车线路。若在某两个街区a，b之间加开线路（前提是a、b之间必须已有线路），则从a到b的旅行时间缩小为原来的一半（距离未变，只是等车的时间缩短了一半）。例如，若在1，2之间加开一条线路，则时间变为17分钟，加开两条线路，时间变为8.5分钟，以此类推。所有的线路都是环路，即如果由1至2的时间变为17分钟，则由2至1的时间也变为17分钟。求加开某些线路，能使由城市1至城市n的时间最少。例如，在上图中，如果m=2，则改变1-3，3-5的线路，总的时间可以减少为22分钟。输入：输入：第一行为城市数n与加开线路数m；第二行至第n+1行，每行为n个实数，第i+1行第j列表示由城市i到城市j的时间。如果时间为0，则城市i不可能到城市j。注意：输入数据中，从城市1到城市n至少有一条路线。输出：输出：第一行为由城市1到城市n的最小时间X（保留小数点后两位）；第二行至第m+1行为更改的线路。每行由两个整数（x，y）构成。表示将城市x与城市y之间增加一条线路。1、将道路a-b上增加的m条边可以分为如下两个问题（如果k是最短路上的一点）求a-k增加t条边；求k-b增加m-t条边。t可以取从0至m的任意值。问题a-b增加m条边的最优解取决与这两个子问题的最优解。2、在求m条边的过程中，始终只与增加t条边与增加m-t条边的子问题发生联系。系。以上两个特点即为“无后效性”与“最优子问题”。所以，“城市交通”问题可采用动态程序设计方法。设vala，b，m的值为增加m条线路后城市a到城市b的最短路长。其中vala，b，0的值为原交通图中边城市a至城市b的最短路，可以直接使用floyd算法计算；vala，b，m=minvala，k，t+valk，b，m-t(其中t为从0到m中的一个数，k为a到b中间的一点)直接使用floyd算法计算vala，b，0（1an，1bn）；forg1tomdo按照新增加的边数g划分阶段begin对任一对城市（i，j）来说，(i，j)的边权减半；vali，j，g=(i，j)的边权；fork1tondo枚举中间城市fori1tondo枚举经由城市k的所有城市对（ikj）forj1tondobeginvali，j，g=；计算状态转移方程vali，j，g=minvali，j，g，vali，k，0+valk，j，gvalk，j，g0，valk，j，0+vali，k，gvali，k，g0；End；forend；for说明：这个问题的val数组的初始值与上一个floyd算法不一样，初始值均为maxint。这个算法的时间复杂度为W(n3*m2)，约为W(n5)多进程的最优化决策问题多进程的最优化决策问题怎样对多个并行的、可划分阶段的进程进行最优化决策，关键是如何存储状态。多进程问题的状态数目十分庞大，每一个状态的存储量大，且又是求多条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。方格取数方格取数设有n*n的方格图（），我们将其中的某些方格中填入正整数，而其他的方格中则放入数字。如下图所示（见样例）：某人从图的左上角的点出发，可以向下行走，也可以向右走，直到到达右下角的点。在走过的路上，它可以取走方格中的数（取走后的方格中将变为数字）。此人从点到点共走两次，试找出条这样的路径，使得取得的数之和最大。输入：输入的第一行为一个整数（表示的方格图），接下来的每行右三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的表示输入结束。输出：只需输出一个整数，表示条路径上取得的最大的和1、状态的设计、状态的设计 对于本题来说，状态的选定和存储对整个问题的处理起了决定性的作用。我们从（1，1）出发，每走一步作为一个阶段，则可以分成2*n-1个阶段： 第一个阶段，两条路径从（1，1）出发； 第二个阶段，两条路径可达（2，1）和（1，2）； 第三个阶段，两条路径可达的位置集合为（3，1）、（2，2）和（1，3）； 第2*n-1个阶段，两条路径汇聚（n，n）；在第k(1k2*n-1)个阶段，两条路径的终端坐标（x1，y1）（x2，y2）位于对应的右下对角线上。如下图所示：如果我们将两条路径走第i步的所有可能位置定义为当前阶段的状态的话，面对的问题就是如何存储状态了。方格取数问题的状态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。为此，我们取位置中的x坐标（x1，x2）作状态，其中（1x1k）and（x11n）and（1x2k）and（x21n）直接由x坐标计算对应的y坐标：（y1=k+1-x1）and（y11n）and（y2=k+1-x2）and（y21n2、状态转移方程、状态转移方程设两条路径在k阶段的状态为（x1，x2）。由（y1=k+1-x1）（y11.n）得出第一条路径的坐标为（x1，y1）；由（y2=k+1-x2）（y21.n）得出第二条路径的坐标为（x2，y2）。假设在k-1阶段，两条路径的状态为（x1，x2）且（x1，x2）位于（x1，x2）状态的左邻或下邻位置。因此我们设两条路径的延伸方向为d1和d2：di=0，表明第i条路径由（xi，yi）向右延伸至（xi，yi）；di=1，表明第i条路径由（xi，yi）向下延伸至（xi，yi）（1i2）。显然（x1= x2）（d1= d2），表明两条路径重合，同时取走了（x1，y1）和（x1，y1）中的数，这种取法当然不可能得到最大数和的。分析两种可能：若x1=x2，则两条路径会合于x1状态，可取走（x1，y1）中的数(如下图)； x1(x2)x1=x2 x2(x1)若x1x2，则在k阶段，第一条路径由x1状态延伸至x1状态，第二条路径由x2状态延伸至x2状态，两条路径可分别取走（x1，y1）和（x2，y2）中的数(如下图)；设 fk，x1，x2在第k阶段，两条路径分别行至x1状态和x2状态的最大数和。显然k=1k=1时，时，f1f1，1 1，1=01=0；k2k2时时，fkfk，x x1 1，x x2 2=maxfk-1=maxfk-1， x x1 1，x x2 2+(x+(x1 1，y y1 1) )的的数数字字x x1 1=x=x2 2，fk-1fk-1， x x1 1，x x2 2+(x+(x1 1，y y1 1) )的数字的数字+(+(x x2 2，y y2 2) )的数字的数字x x1 1xx2 2 1k2*n-11k2*n-1， x x1 1可可 达达 x x1 1的的 状状 态态 集集 合合 ， x x2 2可可 达达 x x2 2的的 状状 态态 集集 合合 ，（x x1 1xx2 2）(d1 1dd2 2) )；上述状态转移方程符合最优子结构和重叠子问题的特性，因此适用于动态程序设计方法求解。由于第k个阶段的状态转移方程仅与第k-1个阶段的状态发生联系，因此不妨设 f0第k-1个阶段的状态转移方程； f1第k个阶段的状态转移方程；初始时，f01，1=0。经过2*n-1个阶段后得出的f0n，n即为问题的解。3、多进程决策的动态程序设计多进程决策的动态程序设计 由于方格取数问题是对两条路径进行最优化决策的，因此称这类动态程序设计为分阶段、多进程的最优化决策过程。设阶段i：准备走第i步（1i2*n-1）；状态（x1，x2）： 第i-1步的状态号（1x1，x2i-1。x1，x21.n）决策（d1，d2）：第一条路径由x1状态出发沿d1方向延伸、第二条路径由x2状态 出发沿d2方向延伸，可使得两条路径的数和最大（0d1，d21。方向0表示右移，方向1表示下移）；fillchar(f0，sizeof(f0)，0)；行走前的状态转移方程初始化f01，10；for i2 to n+n-1 do阶段：准备走第i步 begin fillchar(f1，sizeof(f1)，0)； 走第i步的状态转移方程初始化 for x11 to i-1 do枚举两条路径在第i-1步时的状态x1和x2 for x21 to i-1 do begin 计算y1和y2； if (x1，y1)和(x2，y2)在界内 then for d10 to 1 do 决策：计算两条路径的最佳延伸方向 for d20 to 1 do begin 第1条路径沿d1方向延伸至(x1，y1）； 第2条路径沿d2方向延伸至(x2，y2)； if (x1，y1)和(x2，y2)在界内)(d1d2)(x1x2) 计算第i步的状态转移方程then f1x1，x2maxf0x1，x2+mapx1，y1x1=x2，f0x1，x2+mapx1，y1+mapx2，y2x1x2 end；for end；for f0f1；记下第i步的状态转移方程end；for输出两条路径取得的最大数和f0n，n动态程序设计方法的优化动态程序设计方法的优化 下面，我们来分析一个具体实例，并给出多种解法。对于这些解法，我们将指出好的算法好在哪里，差一点的算法差在哪里，通过不同算法的比较，让读者更深刻的领会优化动态程序设计方法的基本思维方式是“不做已经做过的工作”。理想收入问题理想收入问题理想收入是指在股票交易中，以1元为本金可能获得的最高收入，并且在理想收入中允许有非整数股票买卖。已知股票在第i天每股价格是Vi元，1im，求m天后的理想收入。 1、解法解法1 1很容易想到用动态程序设计方法解这道题目。因为要使得第i天获得理想收入，则前一次卖出股票的收入必须最高，否则第i天所持的股票数不可能最多。而要使得第i天所持的股票数最多，则必须检查第i-1天、第i-2天、第1天卖出股票的理想收入。理想收入问题具备了最优子结构和无后效性的特征。设阶段i：将所持的股票全部卖出的日期（1im）状态j：前一次卖出股票的日期（0ji-1）决策k：第j天后买入股票的日期（jki-1）fi表示在第i天收盘时能达到的最高收入，则状态转移方为公式1的含义是：在第i天收盘时能达到的最高收入，是将第j天收盘后的收入，全部用于买入第k天的股票，再在第i天将所持的股票全部卖出所得的收入。采用公式1，可以得到算法1，其时间复杂度是W(m3)，空间复杂度是W(m)。算法算法1：f01；V01；以1元为本金设定f和v的初始值f1.m0；fori1tomdo阶段：枚举最后卖出全部股票的日期iforj0toi-1do状态：枚举前一次卖出股票的日期状态：枚举前一次卖出股票的日期jforkjtoi-1do决策：枚举决策：枚举第第j天天第第i-1天间买入股票的日期天间买入股票的日期kfimaxfi，fj/Vk*Vi；计算状态转移方程计算状态转移方程2 2、解法、解法22改变状态表示的含义改变状态表示的含义改变动态程序设计中状态表示的含义，是优化动态程序设计的常用方法。例如此题，我们可以采用两种不同的状态表示方法优化算法2-1。方法1：设Pi表示前i天能获得的最多股票数，可列出如下状态转移方程：这是因为前i天所能获得的最多股票数，或者是前i-1天获得的最多股票数，或者是在第j天将前j天所能获得的最多的股票全部卖出，再买入第i天的股票。显然，前i-1天能获得的最多股票数乘以第i天的股价，就是第i天能达到的最大收入。方法2：设Qi表示前i天能达到的最大收入，可列出如下状态转移方程：就是说前i天所能达到的最大收入，或者是前i-1天所能达到的的最大收入，或者是在第j天买入股票，再在第i天卖出，所能获得的最大收入。 上述两种方法的时间复杂度都是W(m2)。算法1中，采用了二重循环来确定fj/Vk的最大值。但在确定fi-1所能达到最大值的时候，我们实际上已经求出当0jki-1时，fj/Vk所能达到的最大值。如果能充分利用这一信息，就可以更快地确定fi所能达到的最大值。如下图所示，要确定粗线下部的最大值，只需比较虚线下部的最大值和灰色部分的最大值即可。3 3、解法、解法33粗略利用信息粗略利用信息得到如下递推关系式：从公式4中可以看出，在确定maxfVi时，较充分的利用了确定maxfVi-1时产生的结果。采用公式4可得算法2，它的时间复杂度为W(m2)，空间复杂度是W(m)。算法算法2 2：f0 1； V0 1；以1元为本金设定f和v的初始值maxfV0 0； 交易前没有股票for i1 to m do begin 计算每一天所持的最多股票数 maxfVmaxfViimaxfVmaxfVi-1i-1； 将第将第i-1i-1天所持的最多股票数设为天所持的最多股票数设为maxfVmaxfVii的初始值的初始值 for j0 to i-1 dofor j0 to i-1 do枚举前枚举前i-1i-1天购买股票的方案，将最多股票数设为天购买股票的方案，将最多股票数设为maxfVmaxfVii maxfV maxfVimaximaxmaxfVmaxfVii，fj/Vi-1fj/Vi-1； fi fimaxfVmaxfVi*Vii*Vi； 在第在第i i天将天将maxfVmaxfVii张股票全部抛出张股票全部抛出 end；for将公式4化简，有4 4、解法、解法33充分利用信息充分利用信息算法2的粗体部分的功能是确定maxfVi所能达到的最大值。由于Vi-1不变，因此fj/Vi-1达到最大值，当且仅当fj达到最大值，其中0jmaxf then maxff;若抛出第i-1天的股票可获得最大的收益，则确定第i-1天将股票抛出 if maxf/Vi-1maxfV then maxfVmaxf/Vi-1；若购买第i-1天的股票可获得最多的股票数，则确定第i-1天购买股票 fmaxfV*Vi 计算抛出第i天股票的收益end；for公式4中的maxfi可以看作是前i-1天能达到的最大收入。虽然这种状态表示方法和公式3中Qi是类似的，但算法的时间复杂度却从W(m2)降到了W(m)，空间复杂度也从W(m)降到了W(1)。这样，我们通过充分利用已知信息，达到了改变状态表示难以达到的优化效果。动动态态程程序序设设计计方方法法之之所所以以效效率率高高，是是因因为为它它把把已已经经做做过过的的工工作作结结果果存存储储起起来来，每每次次需需要要的的时时候候，直直接接读读入入即即可可，不不做做已已经经做做过过的的工工作作。当当然然，对对于于同同一一个个问问题题，由由于于各各人人看看问问题题的的角角度度不不同同，对对阶阶段段、状状态态和和状状态态转转移移方方式式的的理理解解可可能能不不一一样样，因因此此有有些些状状态态转转移移方方程程仍仍存存在在冗冗余余运运算算。是是否否充充分分利利用用信信息息是是提提高高时时间间效效率率的的关关键键。此此外外，充充分分利利用用信信息息并并不不一一定定要要以以牺牺牲牲空空间间为为代代价价，只只要要方方法法得得当当，同同样样可可以以优优化化算算法的空间复杂度。法的空间复杂度。谢谢！谢谢！