1、上海市控江中学上海市控江中学 王建德王建德题题 型型 题题 型型与课内知识和编程基础相关自由落体、级数求和、乒乓球、麦森数、不高兴的津津、花生采摘、津津的储蓄计划构造法均分纸牌、传染病控制、火星人数据结构字符近似查找、合并果子（堆排序）、栈、FBI树（二叉树）、神经网络（图）枚举法虫食算、侦探推理回溯法选数、字串变换动态程序设计方法过河卒、数字游戏、加分二叉树、合唱队形 几何计算矩形覆盖1、凸现信息学知识和凸现信息学知识和学科学科知识整合的趋势知识整合的趋势。为了考核学生为了考核学生运用学科知识运用学科知识的能力，激发学生的能力，激发学生的创造力，的创造力，2002年全国奥林匹克信息年全国奥林
2、匹克信息联联赛赛(NOIP)中学科类中学科类的试题增加，并且首次出现了计算几的试题增加，并且首次出现了计算几何类的试题何类的试题。这说明信息学与。这说明信息学与学科学科的依赖的依赖关系日益凸现，关系日益凸现，学科基础好、尤其是学科基础好、尤其是数学素质数学素质好的人虽然不一定会编程，但希望学习编程的好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深的潜质和爱好，他们中愈来愈多的人也希望深造数学。造数学。各各门学科的交融和整合是奥林匹克信门学科的交融和整合是奥林匹克信息学息学联赛联赛活动
3、发展的一个大趋势活动发展的一个大趋势（有专家提议，数学教材（有专家提议，数学教材讲算法，信息科技教材讲语言，上海的信息科技教材出现真值表（初中）和讲算法，信息科技教材讲语言，上海的信息科技教材出现真值表（初中）和c语言（高中）。语言（高中）。2、“构造法构造法”或贪心策略类试题的引或贪心策略类试题的引入，使得入，使得算法知识的不确定性和不稳定算法知识的不确定性和不稳定性增加。性增加。这正体现了科学的本质这正体现了科学的本质知识知识是不断推陈出新的。是不断推陈出新的。3、试题的综合性增加试题的综合性增加，并不一定随知，并不一定随知识的分类而发生变化，有时几乎找不识的分类而发生变化，有时几乎找不到
4、一个到一个单一单一的的经典算法经典算法，也找不到一个，也找不到一个纯粹纯粹的数据结的数据结构问题构问题关键是你从哪个角度去分析，关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；愈高，得胜的机率愈大；4、经常面对着不知道算法的试题，经常面对着不知道算法的试题，面对着谁都不知如何处置的情境面对着谁都不知如何处置的情境，因此必须使学生正确地理解问题、因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的深入问题的空间并形成解决问题的意识、习惯和能力意识、习惯和能力。能
5、不能能不能创造性创造性地应答没有遇到过的挑战地应答没有遇到过的挑战，成为培成为培训的基本要求和目标。训的基本要求和目标。1、培养问题意识和问题能力、培养问题意识和问题能力。创造创造始于问题。始于问题。“有了问题才会思考，有了有了问题才会思考，有了思考才有解决问题的方法，才有找到独思考才有解决问题的方法，才有找到独立思路的可能（陶行知）立思路的可能（陶行知）”。有问题虽。有问题虽然不一定有创造，但没有问题一定没有然不一定有创造，但没有问题一定没有创造创造；2、处理好基础性与前沿性、直线培训和、处理好基础性与前沿性、直线培训和散点培训、循序渐进与跳跃式的矛盾散点培训、循序渐进与跳跃式的矛盾。如果恪
6、守按部就班的培训程序，不谋求跳跃式如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的都有必
7、要的跳跃，不少人还能够实现比较大的跳跃跳跃v学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构v培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的，因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。3、参与活动的学生应由竞、参与活动的学生应由竞争关系和独立关系争关系和独立关系转向合作转向合作学习的学习的关系关系学生的心理调适：学生的心理调适：v我掌握的知识仅不过是沧海一粟我掌握的知识
8、仅不过是沧海一粟(进取心进取心)；v固守错误的概念比一无所知更可怕固守错误的概念比一无所知更可怕（明智）（明智）；v三人之行必有我师三人之行必有我师（谦虚）（谦虚）；v知识生产社会化条件下人的基本素质之一知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如上千科学家进行长期甚至跨国的合作，例如制作制作windows，人类基因工程），人类基因工程）（现代意识）（现代意识）；前提条件：前提条件：水平相当的同质成员水平相当的同质成员或各有所长（包括数学知识、编或各有所长（包括数学知识、编程能力和思维方式
9、等解题所需的程能力和思维方式等解题所需的各种因素）的异质成员是开展合各种因素）的异质成员是开展合作学习的组织基础；作学习的组织基础；合作学习的效应：合作学习的效应：v集思广益容易出好的算法；集思广益容易出好的算法；v群体设计的测试数据相对全面；群体设计的测试数据相对全面；v在群体活动中能比较客观的反映自己在群体活动中能比较客观的反映自己能力情况；能力情况；v每个学生在付出与给予中可提高合作每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相精神和编程能力，成功者往往是那些相容性好、容性好、乐于帮助他人，并且善于取乐于帮助他人，并且善于取他人之长的学生他人之长的学生（符文杰、张一飞
10、等）。（符文杰、张一飞等）。4、选手面对从未遇到过的、选手面对从未遇到过的挑战应调整好心态，挑战应调整好心态，不要急不要急功近利，要只管耕耘、不问收获、功近利，要只管耕耘、不问收获、潜心钻研、其乐潜心钻研、其乐无穷无穷。那怕是一两。那怕是一两次失误，也是砥砺之石，可从中汲次失误，也是砥砺之石，可从中汲取有益的经验取有益的经验和教训和教训。“不是一番不是一番寒彻骨，哪得梅花扑鼻香寒彻骨，哪得梅花扑鼻香”。有些基础题虽然直接给出了计算公式或算法十分明显（例如统计数和），但是，如果变量的数据类型选错了，或者不会文件操作，同样会做错题，导致意外的失误。因此作题必须强调两基：两基：基础知识基础知识 基本
11、基能基本基能已知：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:extendeds,b,k:extended；数列的和、项数、
12、最接近sn(大于sn)的整数值begins0；b0；数列的和、项数初始化readln(k)；读最接近sn(大于sn)的整数值kwhile s1)），则输出当前局的比分a：b。请注意，如果输入的字符为E，则标志比赛结束，11分制计算完毕；否则，继续读下一个字符，计算新一局的比分。然后，对当前输入行计算21分制下每一局比赛的比分。计算方法基本如上。有所不同的是，若华华得分a或者对方得分b达到21分且双方的分数差值大于1（(a21)or(b21)and(abs(a-b)1)），则输出当前局的比分a：b。按照上述方法对每一输入行计算11分制和21分制的比赛结果，直至文件读完（eof(input)）为止
13、。assign(input,inp);reset(input);输入文件读准备 assign(output,out);rewrite(output);输出文件写准备 a:=0;b:=0;当前局双方的比分初始化 while not eof(input)do若文件未读完，则循环 begin while not eoln(input)do若当前行处理完，则11分制的比赛结束 begin read(ch);读一个字符 case ch of根据字符的种类分情形处理 E:begin若比赛结束，则输出双方比分 writeln(a,:,b);break;退出11分制的计算过程 end;E W,L:begin华
14、华或对方得一分 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 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
15、eoln(input)do若当前行处理完，则21分制的比赛结束 begin read(ch);读一个字符 case ch of根据字符的种类分情形处理 E:begin若比赛结束，则输出双方比分，退出21分制的计算过程 writeln(a,:,b);break;end;E W,L: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
16、end;W,L end;case end;while readln;end;while close(input);close(output);关闭输入文件和输出文件 关键是文件操作。如果在计算关键是文件操作。如果在计算21分分制的得分前，不会通过制的得分前，不会通过reset(input)将读头移到文件首，则会出错！将读头移到文件首，则会出错！串是由零个或多个字符组成的有限序串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这列。一个串中包含的字符个数称为这个串的长度。长度为零的串称为空串，个串的长度。长度为零的串称为空串，它不包含任何字符。它不包含任何字符。1.连接运算连接运算函
17、数函数concat(s1concat(s1，s2s2，snsn)：其中值：其中值参参s1s1，snsn为为stringstring类型，函数值为类型，函数值为stringstring类型。若连类型。若连接后的串长大于接后的串长大于255255，则自动截断超出部分。，则自动截断超出部分。2.2.求子串求子串函数函数copy(scopy(s，i i，l)l)：其中值参：其中值参s s为为stringstring类型，类型，i i和和l l为为integerinteger类型。函数返回类型。函数返回s s串中第串中第i i个字符开始、长个字符开始、长度为度为l l的子串（的子串（stringstri
18、ng类型）。若类型）。若i i大于大于s s的长度，则回送的长度，则回送一个空串；若一个空串；若l l大于第大于第 i i个字符开始的余串长度，则仅个字符开始的余串长度，则仅回送余串。回送余串。3.3.删子串删子串过程过程delete(vardelete(var s s，i i，l)l)：其中变量参数：其中变量参数s s为为stringstring类型，值参类型，值参i i、l l为为ingtegeringteger类型。该过程删去类型。该过程删去s s中第中第i i个字符开始的长度为个字符开始的长度为l l的子串，并返回剩余串的子串，并返回剩余串s s。若。若i i大大于原串于原串s s的长
19、度，则不删任何字符；若的长度，则不删任何字符；若l l大于第大于第i i个字符个字符开始的余串长度，则删去余串。开始的余串长度，则删去余串。4.4.插入子串插入子串过程过程insert(s1insert(s1，varvar s s，i)i)：变量参数：变量参数s s为为stringstring类型，类型，值参值参s1s1为为stringstring类型。该过程将类型。该过程将s1s1子串插入空串子串插入空串s s的第的第i i个字符位个字符位置处，并返回插入后的结果置处，并返回插入后的结果s s。若插入后。若插入后s s的串长大于的串长大于255255个字符，个字符，则截断超出部分。则截断超出
20、部分。5.5.求串长求串长函数函数length(s)length(s)：值参：值参s s为为stringstring类型。该函数返回类型。该函数返回s s串的串的实际长度值（实际长度值（integerinteger类型）。类型）。6.6.搜索子串位置搜索子串位置函数函数pos(s1pos(s1，s2)s2)：值参：值参s1s1和和s2s2为为stringstring类型。若类型。若s1s1是是s2s2的一个子串，则返回的一个子串，则返回s1s1中第中第1 1个字符在个字符在s2s2串中的位置串中的位置（integerinteger类型）；若类型）；若s1s1非非s2s2的一个子串，则返回的一个
21、子串，则返回0 0。7.7.数值转换为数串数值转换为数串过程过程str(xstr(x，varvar s)s)：值参：值参x x为为integerinteger类型或类型或realreal类型，变量参数类型，变量参数s s为为stringstring类型。该过程将返回数值类型。该过程将返回数值x x对应的对应的数串数串s s。8.8.数串转换为数值数串转换为数值过程过程val(sval(s，var vvar v，varvar c)c)：值参：值参s s为为stringstring类型，类型，变量参数变量参数v v为为integerinteger类型或类型或realreal类型，变量参数类型，变量
22、参数c c为为integerinteger类型。类型。该过程试将该过程试将s s串转换成数值串转换成数值v v。若转换成功，则。若转换成功，则c c为为0 0，并返回对，并返回对应的数值应的数值v v；否则；否则c c为无效字符的序数。为无效字符的序数。9.9.字符的大写转换字符的大写转换函数函数upcase(chupcase(ch)：值参：值参chch为为charchar类型。该函类型。该函数返回数返回chch字符的大写体（字符的大写体（charchar类型）类型）设有n个正整数，将他们连接成一排，组成一个最大的多位整数.例如：n=3时，3个整数13，312，343，连成的最大整数为：343
23、31213。又如：n=4时，4个整数7，13，4，246连接成的最大整数为7424613。程序输入：N N个数程序输出：连接成的多位数 由于连接后的字串长度不变，我们可以利用字符串的大小顺序和十进制的进位关系，对n个数串s进行排序for i1 to n-1 do 顺序排定s1sn-1 for ji+1 to n do if si+sj 0)and(si que3)do ii-1；if i0then insert(que5，s，i)将que5字符插在i位置前 else begin writeln(Error!)；halt；end；else替换操作：从串首出发，由左而右寻找que3字符的位置。若找
24、不到，失败退出；否则将que5替换所有的que3字符：errortrue；for i1 to length(s)do由左而右替换que3字符 if si=que3 then begin errorfalse；sique5；end；then if error then若找不到，失败退出 begin writeln(Error!)；halt；endthen 输入原串s和命令串que；case que1 of D：begin 删除操作；end；D I：begin 插入操作；end；I R：begin 替换操作；end；R end；case 输出s；字符近似查找字符近似查找 设有n个单词的字典表（1n
25、100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）：i：该单词在字典表中的序号；Ei：在字典表中仅有一个字符不匹配的单词序号；Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号；N：其他情况 当查找时有多个单词符合条件，仅要求第一个单词的序号即可。输入文件输入文件 输入文件名为a.in，文件的格式如下：n（字典表的单词数）n行，每行一个单词 待匹配单词输出文件输出文件 输出文件名a.out，格式如下：i Ei Fi其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情况不存在，则输出N。输入输出
26、样例输入输出样例输入1:5abcdeabcasdfasfdabcdaacdabcd输出输出1:4E5F1输入输入2:1ab输出输出2:0E0F0N我们将字典表中的单词分成3类：第1类：单词与待匹配单词多或少一个字符，其余字符匹配；第2类：单词仅有一个字符与待匹配单词不匹配；第3类：单词与待匹配单词完全匹配；设constnote:array1.3 of string=(F,E,)；匹配情况的标志var want:string；待匹配单词list:array1.100 of string；字典表。其中listi为字典ians：array1.100 of integer；单词的类别序列。其中ansi
27、=其他情况相同与有一个字符不同与得到中添加或删除一个字符在0321ilistwantilistwantilistwant1 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 判别一个字串是否比另一个字串多一个字符（其余字符匹配）判别一个字串是否比另一个字串多一
28、个字符（其余字符匹配）我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则猜想不成立。function check(a,b:string):integerfunction check(a,b:string):integer；输入字串输入字串a,ba,b。若。若b b能够在能够在a a的基础上添加一的基础上添加一个字符得到的话，则返回个字符得到的话，则返回1 1；否则返回；否则返回00varvari:integeri:integer；beginbegincheck0check0；for i0
29、 to length(a)do begin for i0 to length(a)do begin acopy(a,1,i)+bi+1+copy(a,i+1,255)acopy(a,1,i)+bi+1+copy(a,i+1,255)；在在aiai后插入后插入bi+1bi+1if a=b if a=b 若插入后两串相同，则成功退出若插入后两串相同，则成功退出 then begin check1then begin check1；exitexit；endend；thenthendelete(a,i+1,1)delete(a,i+1,1)；删去删去a a中的插入字符中的插入字符 endend；for
30、forendend；checkcheck2 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 对字典
31、中的每个单词进行分类 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的类别记为0 if length(listi)+1=length(want)then ansi check(listi,want)；if length(listi)=length(want)+1 then ansi check(want,listi)；end；forhavefalse；匹配情况存在的标志初始化for i3 downto 1 do begin 依次输出每一类别的单词在字典表最先出现的序号 k0；for j1 to n do if ansj=i then begin kj；break；end；thenhavehave or(k0)；writeln(notei,k)；end；for
