基础题和串运算重点课件

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