2015南京市小学生信息学竞赛初赛复习 知识要点

。2015年南京市小学生信息学奥林匹克预赛综述知识要点、典型问题(1.0版)一、知识要点1.二元搜索；2.圆形阵列；3.排序和新排序；4.字符串：从文件中读取单独的单词；5.穷举系统；穷举优化(丑陋的数字)；6.寻找完美排列的生成方法；7.组合检索；8.递归迭代深入到主题中；9.图形印刷；10.高精度计算；11.数学问题；数论问题；c(男，女)；12.回溯；13.贪婪。14.表达式计算；15.文件操作；第二，一些典型的主题，经典算法(和源程序)1.分类、搜索和二分法(1)气泡分类(完成后，需要练习)程序清单二进制整数N输入N二进制整数A(N)，I，FI=1至N投入(一)下一个我J=1做F=0对于I=1至N - J如果A(I) A(I 1)那么全部门办法A(一)、A(一1)F=1结束中频下一个我J=J 1循环直到F=0I=1至N印刷品一；下一个我睡眠：结束(2)二进制搜索(完成)程序清单dim为整数n输入ndim为整数a(n)、I、j、x、mi=1至n输入a(i)接下来我对于i=1至n-1对于j=i 1至n如果a(i) a(j ),则交换a(i), a(j)下一个j接下来我i=1至n打印a(I)；“;接下来我打印L=1 : r=n输入“x=”, x当L=R时执行m=(左)2如果x=a(m ),则打印“找到”睡眠：结束结束if如果x a(m)则R=m - 1其他L=m 1结束if环打印“未找到！”睡眠：结束(3)用二进制搜索插入排序(完成，需要练习)程序清单作为整数的二进制数输入n二进制整数a(n)，尾部，L，R，m输入a(1)对于i=2至n输入xL=1 : R=i-1 : m=(L R) 2当x a(m)和(L=R)时执行如果x a(m)则L=m 1其他r=m1结束ifm=(左)2环如果x a(m)则对于j=i-1至L步骤-1a(j 1)=a(j)下一个ja(L)=x其他对于j=i-1至m步骤-1a(j 1)=a(j)下一个ja(m)=x结束if接下来我i=1至n打印a(I)；下一个我打印睡眠：结束2.数字报告问题，循环数组(1)夏令营旗手(JS2010，问题1)(完成)问题描述2010年江苏“信息与未来”小学生夏令营将在常州市局钱洁小学举行。当何老师得知学校的营员小明被团委选为小旗手时，他准备回家通知他。由于他不是这个班的学生，何老师不知道小明住在哪里。他只是从其他学生那里了解到，小明住在未来社区一栋不超过100层的高层建筑里，但具体在哪一层还不清楚。其他学生提供了三条有用的信息：1)小明的楼层号是质数；2)楼层号转换成二进制数后，1为偶数；3)满足上述两个条件中楼层数最大的一个。请写一个程序，计算并输出符合条件(1，2)的总层数和小明的房屋层数。投入此主题没有输入。产出两个整数，即总层数和小明房子的层数。(2)狐狸寻找兔子问题描述山顶周围有10个洞。一只兔子和一只狐狸分别住在一个洞里。狐狸总是想吃兔子。一天，兔子对狐狸说：“如果你想吃我，一个条件是第一次每隔一个洞找到我，第二次每隔一个洞，等等。次数没有限制。”如果你能找到我，你就能吃一顿好饭，直到找到我你才能停下来。当狐狸认为只有10个洞并且搜索次数没有限制时，他同意了这个条件。结果，我找不到它。现在请写一个程序，假设狐狸已经搜索了1000次，兔子可以安全地藏在哪个洞里。(3)宝石(已经完成，需要练习)问题描述目前，n个人组成一个圆圈(n是输入数据)并以1M的间隔计数(M也是输入数据)。根据统计结果，第一个被列入名单的人是1号，第二个被列入名单的人是2号，第三个被列入名单的人是3号，最后一个被列出的人是n号。n号人最初的安排是什么？投入两个整数n和m，表示人数和报告数之间的间隔。产出一行有n个数字，也就是n个人的原始顺序。(4) round.bas(完成，需要练习)问题描述圆形数字有以下三个特征：a)每个数字指示其下一个数字的位置(从左到右计数，计数到末尾，然后四舍五入到最左边的右边位置)；b)构成这个包围数的数只转一次；c)当所有的数字都旋转一次后，就返回到第一轮开始时得到的数字。例如，3162是包装号：l取这个数的任意一个数作为开始，如1；从这个数字开始，向右数一个数字，然后转到数字6。l从6向右计数，当计数到2时返回到3，向左计数总共6位数，然后转到数字3；l从3数到右边的3个数字，然后它变成数字2。l从2舍入到3并向右计数，总共2位，因此返回到1。任务从3开始的四位数分别有多少周长？(5)2N个好人和坏人的问题(做完了，需要练习)问题描述有n个好人和n个坏人首尾相连站成一个圆圈(n是整数输入，前n个人是好人，最后n个人是坏人)。根据计数间隔m，该数字从1到m循环计数(即，将列出向m报告的每个人)，但是m是未知的。你的任务是找出一个最小的数字间隔m，这样前n个被报道的人都是坏人。产出表示n的整数。产出整数，即计算出的数字之间的间隔m。输入样本3输出样本53.排序、新排序、复杂排序(已完成，需要练习)(1)命名号码(namenum.bas)问题描述在威斯康辛州的牧场主中，习惯上要求会计部门给牛打上连续的数字。然而，奶牛在使用手机时并没有感受到这个系统的便利。他们喜欢用自己最喜欢的名字来称呼他们的同伴，而不是像这样用“Cmon，4734，相处融洽”这样的词。请写一个程序来帮助可怜的牛郎把一头牛的品牌号码翻译成一个可能的名字。因为奶牛现在有了手机，用标准的按键排列将收到的数字翻译成单词(除了“q”和“z”):2: A、B、C 5: J、K、L 8: T、U、V3: D，E，F 6: M，N，O 9: W，X，Y4: G，H，I 7: P，R，S可接受的名字放在这样一个名为“dict.txt”的文件中，该文件包含一系列少于5000个可接受的奶牛名字(所有名字都大写)。收到的奶牛编号返回的名称可以从编号中翻译出来，并且在字典中。例如，数字4734可以产生以下名称：GPDG GPDH GPDI GPEG GPEH GPEI全球政策论坛GPFH全球政策论坛格雷戈格雷赫GREI格雷戈格雷戈夫GRFI格雷戈夫GSFG、HPFH、HPFIHRDG人权协会HRDI HREG HREH HREI人权基金会人权基金会HSDG人权协会HSDIHSEI HSFG HSFI IPDG国际人权讲习所IPDI IPEG IPEH IPEIIPFH IPFI IRDG人权研究所IRDI IREG人权研究所IREI IRFG人权研究所IRFIISDG ISDH ISDI ISEG ISEH ISEI国际安全论坛ISFH ISFI碰巧，81个“GREG”中只有一个是有效的(在字典里)。现在，请编写一个程序来打印给定号码的所有有效名称，如果没有，则输出“NONE”。该数字可能有12位数字。投入单行包含一个数字(长度范围从1到12)。产出按照字典顺序输出一个不负责任的有效名称列表，每行一个名称。样本输入4734样本输出GREG(2)乐谱问题描述世博会志愿者的选拔正在A市如火如荼地进行。为了选拔最合适的人才，a市对所有报名的选手进行了笔试。只有笔试成绩达到面试分数线的人才可以参加面试。面试分数线按计划报名的150%绘制，即如果计划报名m名志愿者，面试分数线为排名m*150%(四舍五入)的参赛选手的分数，最终进入面试的参赛选手为笔试分数不低于面试分数线的所有参赛选手。现在请写一个程序来画出面试分数线，并输出所有参加面试的参赛者的注册号和笔试成绩。投入输入文件名作为分数在第一行，两个整数n，m(5 n5000，3 mn)用空格隔开，其中n代表参加笔试的参赛者总数，m代表计划参加的志愿者人数。输入数据确保m*150%在舍入后小于或等于n。第二行到第一行，每行包括两个用空格隔开的整数，即参赛者的注册号k(1000k9999)和参赛者的笔试成绩s(1s100)。这些数据确保参赛者有不同的注册号。产出出去。在第一行，有两个用空格隔开的整数，第一个整数代表面试评分线；第二个整数是参加面试的实际人数。从第二行开始，每一行包含两个整数，用空格隔开，分别表示参加面试的参赛者的参赛人数和笔试成绩。如果分数相同，则根据条目编号的顺序从高到低输出。样本输入和输出得分。得分，出局6 31000 903239 882390 957231 841005 951001 8888 51005 952390 951000 901001 883239 88样品描述M*150%=3*150%=4.5，向下舍入到4。确保4人进入面试的分数线是88，但因为88的分数很高，所有得分在88或更高的玩家都可以进入面试，所以最终有5人进入面试。(3)分类3.bas(完成，需要练习)问题描述学生们已经学习了几种分类方法，解决了许多分类问题。现在，让我们来看一个三值排序问题，也就是说，给你一个只有三个不同值的数字序列。这种顺序也可以在我们的日常生活中看到。例如，当我们根据金牌、银牌和铜牌对比赛的获胜者进行排名时，就会出现这种顺序。在我们的任务中，只有三个可能的值：1、2和3。我们用交换的方法按升序排列它们。现在，请编写一个程序来计算按升序排列一个由1、2和3组成的长度为n的数字序列所需的最小交换数。投入键盘输入：第一行是表示n的整数(1=n=1000)；对于第二行到第一行，请为每行输入一个介于1和3之间的整数。产出屏幕输出一个数字，表示按升序排列所需的最少交换次数。样本输入9221333231样本输出44.弦乐(完成，需要练习)(1)分隔单词需要从文档中读取英语句子或段落，然后分隔单词。5.数字分离和十进制转换(已经完成，