信息学奥赛教程指导.ppt

《信息学奥赛教程指导.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛教程指导.ppt（228页珍藏版）》请在三一文库上搜索。

1、上海市控江中学 王建德 6、2002、2003年分区联赛复赛试 题解析 1、高精度运算 2、图的运算 3、搜索算法 4、构造算法 5、动态程序设计 题 型题 目 与课内知识相关自由落体、级数求和、乒乓球、 麦森数 字符串处理字符近似查找 贪心法均分纸牌、传染病控制 回溯法选数、字串变换、栈、神经网络 、侦探推理 动态程序设计方法过河卒、数字游戏、加分二叉树 几何计算矩形覆盖 虽然2002、2003年全国奥林匹克信息学复赛中含许多可“ 一题多解” 的试题，但如果按照较优算法标准分类的话，大致可 分为 特特 点点 1、凸现信息学知识和学科知识整合的趋势 。为了考核学生运用学科知识的能力，激发学 生

2、的创造力，2002、2003年全国奥林匹克信息 联赛(NOIP)中学科类的试题增加，并且首次出 现了计算几何类的试题( (矩形覆盖矩形覆盖) )。这说明信息学与 学科的依赖关系日益凸现，学科基础好、尤其 是数学素质好的人虽然不一定会编程，但希望 学习编程的人愈来愈多；编程解题能力强的人 势必有数学的潜质和爱好，他们中愈来愈多的 人也希望深造数学。各门学科的交融和整合是 奥林匹克信息学联赛活动发展的一个大趋势（按照 2005年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识 ）。 2、“构造法” 或贪心策略类试题的引入 ，使得算法知识的不确定性和不稳定性 增加。这正体现了科学的本质知

3、识是 不断推陈出新的。 3、试题的综合性增加，并不一定随知 识的分类而发生变化，有时几乎找不 到一个单一的经典算法( (字串变换字串变换回溯法中有回溯法中有 字符串处理字符串处理) )，也找不到一个纯粹的数据结 构问题（级数求和（级数求和需要为表达式的计算结果设计合适的需要为表达式的计算结果设计合适的 数据类型）数据类型），关键是你从哪个角度去分析 ，也就是说能不能综合所学的知识， 应用自如地解决问题。选手的综合素 质愈高，得胜的机率愈大； 4、经常面对着不知道算法的试题， 面对着谁都不知如何处置的情境（经（经 常出现许多选手在一题中得常出现许多选手在一题中得0 0分、优秀选手表现失常的情况分

4、、优秀选手表现失常的情况 ），因此必须使学生正确地理解问题 、深入问题的空间并形成解决问题 的意识、习惯和能力。能不能创造 性地应答没有遇到过的挑战，成为 培训的基本要求和目标。 1、培养问题意识和问题能力。创造始 于问题。“有了问题才会思考，有了思考 才有解决问题的方法，才有找到独立思 路的可能（陶行知）”。有问题虽然不一 定有创造，但没有问题一定没有创造（想（想 一想当前的解法有没有缺陷，有没有更好的算法，它与哪些一想当前的解法有没有缺陷，有没有更好的算法，它与哪些 问题有联系，与哪些知识相关联，还可以拓延出哪些问题，问题有联系，与哪些知识相关联，还可以拓延出哪些问题， 要解决这些问题还需

5、要哪些知识）要解决这些问题还需要哪些知识）； 启启 示示 2、处理好前沿性与基础性、直线培训和 散点培训、循序渐进与跳跃式的矛盾。 如果恪守按部就班的培训程序，不谋求跳跃式 学习，将离全国和国际奥林匹克信息学活动的 前沿、离世界程序设计知识的前沿愈来愈远。 因此在进行基础课程学习的同时，必须有追逐 前沿的选择性学习。这里，有时候心理的障碍 比科学上的障碍更难跨越，敢不敢的问题比能 不能的问题更突出。其实在学习中或多或少地 都有必要的跳跃，不少人还能够实现比较大的 跳跃（ 爱笛生小学三年级退学、比尔爱笛生小学三年级退学、比尔. .盖茨大学三年级退学）盖茨大学三年级退学） v学生必须学会从浩如烟海

6、的信息中选择最有 价值的知识，构建个性化（符合自己能力结构 和兴趣结构）和竞争需要的知识结构 v培训内容要有选择性，因为除了出题者，谁 也说不清楚在未来竞赛中究竟什么知识是必要 的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材 大不相同，有的同年级同学科的教材相差三分之二）大不相同，有的同年级同学科的教材相差三分之二），因此不可 能把所有重要的东西都选择好了给学生，而是 应该将直线培训与散点培训相结合，选择部分 重要的东西交给学生，让他们自己去探索若干 知识点之间的联系，补充自己认为需要补充的 知识。 3、参与活动的学生

7、应由竞 争关系和独立关系（你做你的（你做你的 ，我干我的，程序和算法互相保密，彼，我干我的，程序和算法互相保密，彼 此津津乐道于对方的失败和自己的成功此津津乐道于对方的失败和自己的成功 ）转向合作学习的关系（通过（通过 研讨算法、集中编程、互测数据等互相研讨算法、集中编程、互测数据等互相 合作的方式完成学习任务）合作的方式完成学习任务） 学生的心理调适： v我掌握的知识仅不过是沧海一粟(进取心)； v固守错误的概念比一无所知更可怕（明智）； v三人之行必有我师（谦虚）； v知识生产社会化条件下人的基本素质之一 是合作精神（现在的重大科学发明需要成百 上千科学家进行长期甚至跨国的合作，例如 制作

8、windows，人类基因工程）（现代意识）； 前提条件：水平相当的同质成员 或各有所长（包括数学知识、编 程能力和思维方式等解题所需的 各种因素）的异质成员是开展合 作学习的组织基础； 合作学习的效应： v集思广益容易出好的算法； v群体设计的测试数据相对全面； v在群体活动中能比较客观的反映自己 能力情况； v每个学生在付出与给予中可提高合作 精神和编程能力，成功者往往是那些相 容性好、 乐于帮助他人，并且善于取 他人之长的学生（符文杰、张一飞等）。 4、选手面对从未遇到过的 挑战应调整好心态，不要急 功近利，要只管耕耘、不问收获、 潜心钻研、其乐无穷。那怕是一两 次失误，也是砥砺之石，可从

9、中汲 取有益的经验和教训。“不是一番寒 彻骨，哪得梅花扑鼻香”。 题题5 5、均分纸牌、均分纸牌 题题6 6、字串变换、字串变换 题题7 7、自由落体、自由落体 题题8 8、 矩形覆盖矩形覆盖 题题 1 1、字符近似查找、字符近似查找 题题2 2、级数求和、级数求和 题题3 3、选数、选数 题题4 4、过河卒、过河卒 9 9、乒乓球、乒乓球 1010、数字游戏、数字游戏 1111、栈、栈 1212、麦森数、麦森数 1313、神经网络、神经网络 1414、侦探推理、侦探推理 1515、加分二叉树、加分二叉树 1616、传染病控制、传染病控制 第一题：字符近似查找 设有n个单词的字典表（1n100

10、）。计算某单词在字典表中的四种匹 配情况（字典表中的单词和待匹配单词的长度上限为255）： i：该单词在字典表中的序号； Ei：在字典表中仅有一个字符不匹配的单词序号； Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号； N：其他情况 当查找时有多个单词符合条件，仅要求第一个单词的序号即可。 输入文件 输入文件名为a.in，文件的格式如下： n（字典表的单词数） n行，每行一个单词 待匹配单词 输出文件 输出文件名a.out，格式如下： i Ei Fi 其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词 ，则对应的i=0。若上述三种情况不存在，则输出N。 输入

11、输出样例 输入1: 5 abcde abc asdfasfd abcd aacd abcd 输出1: 4 E5 F1 输入2: 1 a b 输出2: 0 E0 F0 N 我们将字典表中的单词分成3类： 第1类：单词与待匹配单词多或少一个字符，其余字符匹配； 第2类：单词仅有一个字符与待匹配单词不匹配； 第3类：单词与待匹配单词完全匹配； 设 const note :array13 of string=(F,E,)； 匹配情况的标志 var want:string； 待匹配单词 list:array1100 of string； 字典表。其中listi为字典i ans ：array1100 of

12、 integer；单词的类别序列。其中 ansi= 1、匹配情况的计算 计算两个等长字串中不同字符的个数 function find(a,b:string):integer；输入两个等 长字串a,b，计算和返回不同字符的个数 vari,tot:integer； begin tot0； for i1 to length(a) do if ai0)； writeln(notei,k)； end；for 第二题：级数求和 已知：Sn=1+1/2+1/3+.+1/n。显然当n.非常大 的时候，Sn可大于任何一个整数K。现给出一个整数K （1K15），要求计算出一个最小的n，使得SnK 。 输入 键盘输

13、入k 输出 屏幕输出n 输入输出样例 输入: 1 输出: 2 算法分析 该题考核选手的并不是编程能力，而是选择变量类型的能力。由于该数 列是递减的，而k的上限为15，因此项数很大，即便是longint也容纳不 下。但未必非高精度运算不可。只要启动浮点数运算（$n+），将项 数设为extended类型，便可以得出正确解。 $n+ 启动浮点数运算 var s,b,k:extended； 数列的和、项数、最接近sn(大于sn)的整数值 begin s0； 数列的和初始化 b0； 项数初始化 readln(k)； 读最接近sn(大于sn)的整数值k while sa，则说明a不可能分解出比primei

14、大的素数了 ，a本身为素数。由于primei表的最大素数接近10000，其平方远大 于xi的上限5000000，因此是一个比较可行的方法： function check(a:longint):boolean； 判断a是否是素数 begin checktrue； 素数标志初始化 for i1 to tot do begin 搜索素数表 if primei*primeia then exit；若超出搜索范围的上限，则 说明a是素数，返回true if a mod primei=0 then begin checkfalse；exit；end；then end；for end； check 2、递归

15、搜索方案数 由于数列是随机和无序的，因此只能通过搜索的办法求解。 设 状态(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），xno

16、w选入组合，递归计 算子状态(left-1,now+1,all+listnow)； 由此得出子程序 Procedure solve(left,now,all:longint)；递归计算选数情况 begin if (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)；当前组合不选xn

17、ow,递归计算子状态 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）

18、(n,m 为不超过20的整数,并由键盘输入)，同样马的位置坐标 是需要给出的（约定：CA，同时CB）。现在要求你 计算出卒从A 点能够到达B点的路径的条数。 输 入： 键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y） 输 出： 屏幕输出一个整数（路径的条数）。 输入输出样例： 输入：3 3 2 2 输出：0 1、计算对方马的控制点 按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点 ，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制 点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设 const move:array18,12ofintege

19、r=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(- 2,1),(-2,-1)； movek，12为马沿k方向跳跃一步的水平增量和垂直增量 var list:array-120,-120 of comp；路径数序列，其中listi,j为卒从(0,0)到 (i,j)的路径数 can:array020,020 of boolean； 点(i,j)允许卒通行的标志 马的初始位置为（x,y）。我们按照下述方式计算can序列： canx,y false； 对方马所在的点为控制点 for i1 to 8 do begin从（x，y）出发，沿8个跳马方向计算控制点 jx

20、+movei,1； 计算i方向的跳马位置(j，k) ky+movei,2； if (j=0) and (k=0) and (jxu ud-y y-yz A.out文件： 3 1 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(rule

21、i,1)255 vrulei,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的数学规律，只能采用回溯搜索的办 法。设

22、 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； 由此得出计算过程： procedure solve(need；now)；从当前串now出发，递归第need 次替换 var i,k,j:integer； tmp:string； be

23、gin if need=best then exit； 若到达边界，则回溯 if now=b then begin若达到目标状态，则记下替换次数，并回溯 bestneed； exit； end；then for i1 to n do 搜索每一条规则 if length(now)+length(rulei,2)-length(rulei,1)0 do 反复在tmp 中寻找子串rulei,1 begin solve(need+1，copy(now,1,j+k-1)+rulei,2+copy(now， j+k+length(rulei，1)，255)； 递归下一次替换 delete(tmp,1,k)

24、；将当前被替换串前（包括被替换串）的子串删除 jj+k； 右移匹配指针 kpos(rulei,1,tmp)； 继续尝试第i条规则 end；while end；then end； solve 由此得出主程序： 读入初始串a和目标串； 读入替换规则rule； best31； 设定替换次数的上限 solve(0,a)； 回溯搜索最少的替换次数 if best1)），则输出 当前局的比分a：b。请注意，如果输入的字符为E，则 标志比赛结束，11分制计算完毕；否则，继续读下一个 字符，计算新一局的比分。然后，对当前输入行计算21 分制下每一局比赛的比分。计算方法基本如上。有所不 同的是，若华华得分a或者

25、对方得分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(ou tput);输出文件写准备 a:=0;b:=0; 当前局双方的比 分初始化 while not eof (input) do若文 件未读完，则循环 begin while not eoln(input) do若 当前行

26、处理完，则11分制的比 赛结束 begin read(ch);读一个字符 case ch of根据字符的种 类分情形处理 E: begin若比赛结束，则输出 双方比分 writeln(a,:,b); break;退出11分制的计算 过程 end; E W,L: begin华华或对方得一 分 if ch=Wthen inc(a) else inc(b); if(a=11)or(b=11) and (abs(a-b)1) then若有 一方得分达到11分且双方的分 数差值大于1，则输出双方比 分 begin writeln(a,:,b); a:=0;b:=0;新一局的比分初始化 end;then

27、end; W,L end;case end;while readln; end; while a:=0; b:=0; 新一局的比分初始化 writeln; reset(input);重新读输入行 while not eof(input) do若文件未读完且比赛未结束，则循环 begin while not eoln(input) do若当前行处理完，则21分制的比赛结 束 begin read(ch);读一个字符 case ch of根据字符的种类分情形处理 E: begin若比赛结束，则输出双方比分，退出21分制的计算 过程 writeln(a,:,b); break; end; E W,L

28、: begin华华或对方得一分 if ch=Wthen inc(a) else inc(b); if (a=21)or(b=21) and (abs(a-b)1) 若有一方得分达 到21分且双方的分数差值大于1，则输出双方比分 then begin writeln(a,:,b); a:=0;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln; end;while close(input); close(output);关闭输入文件和输出文件 数字游戏（Game.pas） 丁丁最近沉迷于一个数字游戏之中。这个游戏 看似简单，但丁丁

29、在研究了许多天之后却发觉 原来在简单的规则下想要赢得这个游戏并不那 么容易。游戏是这样的，在你面前有一圈整数 （一共n个），你要按顺序将其分为m个部分， 各部分内的数字相加，相加所得的m个结果对 10取模后再相乘，最终得到一个数k。游戏的要 求是使你所得的k最大或者最小。例如，对于下 面这圈数字（n=4，m=2）： 当要求最小值时，(2-1) mod 10)(4+3) mod 10)=17=7，要求最大值时，为(2+4+3) mod 10)(-1 mod 10)=99=81。特别值得注意的是，无论是负数还 是正数，对10取模的结果均为非负值。 丁丁请你编写程序帮他赢得这个游戏。 【输入格式】输

30、入文件第一行有两个整数，n（1n50 ）和m（1m9）。以下n行每行有个整数，其绝对值 不大于104，按顺序给出圈中的数字，首尾相接。 【输出格式】输出文件有两行，各包含一个非负整数 。第一行是你程序得到的最小值，第二行是最大值。 算法分析 设圆周上的n个数字为a1、a2、an。按照模运算的 规则（a1+a2+ +ak）mod 10=(a1 mod 10+a2 mod 10+ ak mod 10)mod 10；gi，j为ai、ai+1 、aj的数和对10的模，即 gi，j=（ai+ai+1+ +aj）mod 10 显然 gi，i=（ai mod 10+10）mod 10 gi，j= (gi,j

31、-1+gj,j) mod 10 (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：划分成的部分数,

32、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,j fmax1p,i,j= fmax1p-1,i,k*gk+1,j 2pm-1 max= min= 由于p-1阶段仅和p阶段发生联系，因此我 们将p-1阶段的状态转移方程fmin1p-1,i,j 设为fmin1i,j、fmax1p-1,i,j 设为 fmax1i,j，将p阶段的状态转移方程 fmin1p,i,j设为fmini,j、fm

33、ax1p,i,j设为 fmaxi,j。 read(n,m);读数字个数和划分的部 分数 fillchar(fmax1,sizeof(fmax1),0); fillchar(fmin1,sizeof(fmin1),$FF); 状态转移方程初始化 fillchar(g,sizeof(g),0); for i:=1 to n do依次读入每个数 ，一个数组成一部分 begin read(gi,i); gi,i:=(gi,imod mask+mask) mod mask; min1i,i:=gi,i;fmax1i,i:=gi,i ; end;for for i:=1 to n do计算一部分内的 数和

34、对10的模的所有可能情况 for j:=i+1 to n do begin gi,j:=(gi,j-1+gj,j) mod mask; fmax1i,j:=gi,j; fmin1i,j:=gi,j; end;for for p:=2 to m-1 do阶段：递 推计算划分2部分m-1部 分的结果值 begin fillchar(fmax,sizeof(fmax),0); 划分p部分的状态转移方 程初始化 fillchar(fmin,sizeof(fmin),$FF ); for i:=1 to n do状态：枚举被划分为p部分的数字区间 for j:=i to n do for k:=i to

35、 j-1 do决策：aiak被划分为p-1部分 begin if fmax1i,k*gk+1,jfmaxi,j 计算将ai、ai+1、aj划分 成p个部分的状态转移方程 then fmaxi,j:=fmax1i,k*gk+1,j; if(fmin1i,k=0)and(fmin1i,k*gk+1,j1) or (jmax then max:=(g1,i-1+gj+1,n) mod mask*fmax1i,j; if(fmin1i,j=0) and (g1,i-1+gj+1,n) mod mask*fmin1i,j0），则栈顶元素进入输出序列,递归子状态（tp -1,l+1,r）； v 操作数序列

36、的首元素入栈, 递归子状态（tp+1,l,r+1）。 procedure search（tp,l,r）; begin if r=n+1若得到一个输出序列，则输出序列的总数目 +1，回溯 then begin total:= total+1;exit回溯 end;then if tpflag)。若顶点i处于非输入 层（ci=flag），则递归计算ci。若前驱顶点I处于兴奋状态（ci0），则 将ci*gi,k计入ck。由此得出计算过程 procedure search(k : integer);递归计算顶点k的服从公式 var i : integer; begin ck:=-uk; 顶点k的服从公

37、式初始化 for i:=1 to n do枚举顶点k的每一个前驱顶点 if gik0 then inc(ck,ci*gi,k);若前驱顶点I处于兴奋状态，则 累计顶点k的服从公式 end;then end; search 主程序 for i:=1 to n do递归计算每一个非输入层顶点的服从公 式 if ci=flag then search(i); exist:=false;输出层顶点的最后状态均为0 for i:=1 to n do枚举输出层中c处于兴奋状态的顶点 ，输出这些顶点的最后状态 if (di=0) and (ci0) then begin writeln(i, ,ci); e

38、xist:=true; 输出层存在最后状态非0的顶点 end;then if not exist then writeln(NULL);若输出层顶点的最 后状态均为0，则输出NULL 侦探推理 明明同学最近迷上了侦探漫画柯南并沉醉于 推理游戏之中，于是他召集了一群同学玩推理游 戏。游戏的内容是这样的，明明的同学们先商量 好由其中的一个人充当罪犯（在明明不知情的情 况下），明明的任务就是找出这个罪犯。接着， 明明逐个询问每一个同学，被询问者可能会说： 证词中出现的其他话，都不列入逻辑推理的内容。明明所知道 的是，他的同学中有N个人始终说假话，其余的人始终说真。 现在，明明需要你帮助他从他同学的话

39、中推断出谁是真正的凶 手，请记住，凶手只有一个！ 【输入格式】输入由若干行组成，第一行有二个整数，M（ 1M20）、N（1NM）和P（1P100）。M是参加游戏的明 明的同学数，N是其中始终说谎的人数，P是证言的总数。接下 来M行，每行是明明的一个同学的名字（英文字母组成，没有 空格，全部大写）。往后有P行，每行开始是某个同学的名宇， 紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所 列格式。证词每行不会超过250个字符。输入中不会出现连续的 两个空格，而且每行开头和结尾也没有空格。 【输出格式】如果你的程序能确定谁是罪犯，则输出他的名字 ；如果程序判断出不止一个人可能是罪犯，则输出 C

40、annot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。 算法分析 1、根据输入信息建立几张表 name为名字表，其中namei为第i个同学的名字； sform为证言的来源，其中sformi为第i句证言中提供证言的同学序 号； skind为证言的类型，其中skindi= sobj为证言的涉及的对象，其中sobji= （1ip） 证言格式为“证言人名字：证明内容”。显然，输入的证言是否合法 的条件是 v证言人名字后存在一个：； v证言人名字在name表中存在； v证明对象在name表中存在； 我们根据输入信息建立sform表、skind表和sobj表： r

41、eadln(m,n,l);输入同学数、说谎的人数和证言的句数 p:=0;sform表和skind表的指针初始化 for i:=1 to m do readln(namei);读每个同学的姓名 for i:=1 to l do逐句输入证言 begin readln(s);读第i句证言 j:=pos(:,s);计算提供证言的同学姓名nam1和编号k if j=0 then continue; name1:=copy(s,1,j-1); for k:=1 to m do if namek=name1 then break; if namekname1 then continue; inc(p);sf

42、romp:=k; delete(s,1,j+1); while slength(s)= do delete(s,length(s),1); if s=I am guilty. 将提供证言的同学编号k和证言类型记入sform表和skind 表，日期或证明对象编号记入sobj表 Then skindp:=1; else if s=I am not guilty. Then skindp:=2; else if length(s)9 then if copy(s,1,9)=Today is then begin delete(s,1,9); skindp:=5; if s=Monday. then

43、sobjp:=1 else if s=Tuesday. then sobjp:=2 else if s=Wednesday. then sobjp:=3 else if s=Thursday. then sobjp:=4 else if s=Friday. then sobjp:=5 else if s=Saturday. then sobjp:=6 else if s=Sunday. then sobjp:=7 else dec(p); endthen else begin j:=pos( ,s);计算证明对象的编号x，并记入sobj表 if j=0 then continue; name1

44、:=copy(s,1,j-1); for x:=1 to m do if namex=name1 then break; if namexm：所有同学已推理。在这种情况下，搜索所有 证言，按照下述方法计算罪犯情况表d或日期情况表 week。 依次判断每一句证言，根据提供证言的同学的诚信情况来 决定指认对象是否为罪犯或者当天的日期： v若第i句证言说得是 “I am guilty.”，则提供证言的同学是否为罪犯必须与 他的诚信情况一致，即dsfromi不能为-fsfromi，否则矛盾（即当 skindi=1时，若dsfromi=0或者dsfromi=fsfromi，则 dsfromi=fsfro

45、mi； v若第i句证言说得是 “I am not guilty.”，则提供证言的同学是否为罪犯必须 与他的诚信情况相反，即当skindi=2时，若dsfromi=0或者dsfromi=- fsfromi，则dsfromi=-fsfromi； v若第i句证言说得是“XX is guilty.”，则定指认对象XX是否为罪犯必须与 提供证言的同学的诚信情况一致，即当skindi=3时，若dsobji=0或者 dsobji=fsfromi，则dsobji=fsfromi； v若第i句证言说得是 “XX is not guilty.”，则定指认对象XX是否为罪犯必 须与提供证言的同学的诚信情况相反,即当skindi=4时，若dsobji=0或者 dsobji=-fsfromi，则dsobji=-fsfromi）； v若第i句证言说得是 “Today is XX.”，则今天是否为星期xx必须与提供证 言的同学的诚信情况一致，即当skindi=5时，若weeksobji=0或者 weeksobji=fsfromi，则 weeksobji:=fsfromi）； 然后分析 v若当天的日期不唯一（ ）或不确定的日期数为0，则 回溯； v若确定罪犯的人数为一人（ ），且以前没有确定过罪犯 或者当前确定的罪犯与以前确定的罪犯同属一人，则当前确定的罪 犯成立；否则，输出罪犯不止一人的信息； v若不确定罪犯