《2015南京市小学生信息学竞赛初赛复习 知识要点》由会员分享，可在线阅读，更多相关《2015南京市小学生信息学竞赛初赛复习 知识要点（18页珍藏版）》请在金锄头文库上搜索。
1、2015南京市小学生信息学竞赛初赛复习知识要点、典型题（版本1.0）一、知识要点1. 二分查找；2. 循环数组；3. 排序、新型排序；4. 字符串：分离单词从文件中读入；5. 进制穷举；穷举的优化（丑数）；6. 生成法求全排列；7. 组合取数；8. 递推迭代深入题目；9. 图形打印；10. 高精度计算；11. 数学类问题；数论问题；C（M，N）；12. 回溯；13. 贪心；14. 表达式计算；15. 文件操作；二、一些典型题目、经典算法（及源程序）1. 排序、查找、二分（1）冒泡排序（已做，需练习）【程序清单】DIM AS INTEGER NINPUT NDIM AS INTEGER A(N)
2、, I, FFOR I = 1 TO N INPUT A(I)NEXT IJ = 1DO F = 0 FOR I = 1 TO N - J IF A(I) A(I+1) THEN SWAP A(I), A(I+1) F = 1 END IF NEXT I J = J + 1LOOP UNTIL F = 0FOR I = 1 TO N PRINT A(I);NEXT ISLEEP : END（2）二分查找（已做）【程序清单】dim as integer ninput ndim as integer a(n), i, j, x, mfor i = 1 to n input a(i)next ifo
3、r i = 1 to n-1 for j = i+1 to n if a(i) a(j) then swap a(i), a(j) next jnext ifor i = 1 to n print a(i); ;next iprintL = 1 : r = ninput x= , xdo while L = R m = (L+R) 2 if x = a(m) then print found sleep : end end if if x a(m) then R = m - 1 else L = m + 1 end ifloopprint Not found!sleep : end（3）带二分
4、查找的插入排序（已做，需练习）【程序清单】DIM AS INTEGER ninput nDIM AS INTEGER a(n), tail, L, R, minput a(1)for i = 2 to n input xL = 1 : R = i-1 : m = (L+R) 2 Do while x a( m ) and (L a(m) then L = m + 1elseR = m 1 end ifm = (L+R) 2 loop if x a(m) then for j = i-1 to L step -1 a(j+1) = a(j) next j a(L) = x else for j
5、= i-1 to m step -1 a(j+1) = a(j) next j a(m) = xend ifnext iFOR i = 1 TO n PRINT a(i);NEXT iPRINTSLEEP : END2. 报数问题、循环数组（1）夏令营旗手（JS2010，第一题）（已做）【问题描述】2010年江苏省“信息与未来”小学生夏令营将在常州市局前街小学进行，该校的何老师得知本校营员小明同学被营委会选为夏令营的小旗手，就准备到他家去通知他。由于他不是本班的学生，所以何老师不知道小明家住在什么地方，只从其他同学那里得知，小明住在未来小区一幢不超过100层的高楼中，但在哪一层不清楚。其他同学
6、提供了三条有用的信息：1）小明家的楼层号是一个素数；2）该楼层号化为二进制数后，其中1的个数是偶数；3）满足以上两个条件中，楼层号最大的一个。请你写一个程序，计算并输出满足条件（1、2）的楼层个数总数及小明家的楼层号。【输入】本题无输入。【输出】两个整数，即楼层个数总数和小明家的楼层号。（2）狐狸找兔子(hide.bas) （已做）【问题描述】围绕着山顶有10个洞，一只兔子和一只狐狸各住一个洞，狐狸总想吃掉兔子。一天，兔子对狐狸说：你想吃我有一个条件，就是第一次隔一个洞找我，第二次隔两个洞找我，以后依此类推，次数不限。若能找到我，你就可以饱餐一顿，在没有找到我之前不能停止。狐狸一想只有10个洞
7、，寻找的次数又不限，哪有找不到的道理，就答应了条件。结果就是没找着。现请你编写一个程序，假定狐狸找了1000次，兔子躲在哪个洞里才安全。（3）循环报数(baoshu.bas) （已做，需练习）【问题描述】 现有N个人围成一圈（N为输入的数据），按1M的间隔报数（M也是一个输入的数据）。根据报数的结果发现，第一个出列的人是1号，第二个出列的人是2号，第三个出列的人是3号，最后一个出列的人是N号。问原来这N个人的排列位置是怎样的？【输入】 两个整数N和M，表示人数和报数的间隔。【输出】 一行共N个数，即这N个人原来的排列顺序。（4）环绕数(round.bas) （已做，需练习）【问题描述】一个环绕
8、数有如下三个特点：a) 每个数字指示了它下一个数字的位置（自左向右数，数到末尾后，再绕到最左位往右数）；b) 组成这个环绕数的数字只轮到一次；c) 当所有数字都轮过一次后，正好回到第一次开始所取到的那个数字。例如，3162就是一个环绕数：l 取该数任一数字作为开始，如取1；l 由此数字开始向右数1位，轮到了数字6；l 由6向右数，数到2时绕回到3，再向左数共数6位，就轮到了数字3；l 由3向右数3位，便轮到了数字2；l 由2绕回到3再向右数，共数2位，于是回到1。【任务】求以3开头的四位数中，共有几个环绕数，分别为多少？（5）2N个好人与坏人问题（已做，需练习）【问题描述】有N个好人与N个坏人
9、首尾相接地站成一圈（N为输入的一个整数，且前N个人为好人，后N个人为坏人），按照报数间隔M进行1到M地循环报数（即每报到M的人就出列），但M未知。你的任务是求出一个最小的报数间隔M，使得最先报出的N个人都是坏人。【输出】 一个整数，表示N。【输出】 一个整数，即所求出的报数间隔M。【输入样例】 3【输出样例】 53. 排序、新型排序、复杂排序（已做，需练习）（1）命名那个数字（ namenum.bas ）【问题描述】在威斯康辛州牛大农场经营者之中，都习惯于请会计部门用连续数字给母牛打上烙印。但是，母牛用手机时并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴，而不是用像这个的语
10、句“Cmon, #4734, get along”。请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。因为母牛们现在都有手机了，使用那标准的按键的排布来把收到从数目翻译到文字（除了“Q”和“Z”而外）： 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S可接受的名字都被放在这样一个叫作dict.txt 的文件中，它包含一连串的少于 5000个可接受的牛名字（所有的名字都是大写的）。收到母牛的编号返回那些能从编号翻译出来并且在字典中的名字。举例来说，编号 4734 能产生的下列各项名
11、字：GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDIGREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEIGSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFIHRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDIHSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEIIPF
12、G IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFIISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI碰巧，81个中只有一个“GREG”是有效的（在字典中）。现在，请你写一个程序来对给出的编号打印出所有的有效名字，如果没有则输出“NONE”。编号可能有12位数字。【输入】（ namenum.in )单独的一行包含一个编号（长度可能从1到12）。【输出】（ namenum.out ）以字典顺序输出一个有效名字的不负列表，一行一个名字。【样例输入】4734【样例输出】GREG（2）分数线划定(scor
13、e.bas) （已做，需练习）【问题描述】世博会志愿者的选拔工作正在 A 市如火如荼地进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。【输入】输入文件名为 score.in。第一行，两个整数n，m（5 n5000，3 mn），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000k9999）和该选手的笔试成绩s（1s100）。数据保证选手的报名号各不相同。【输出】输出文件 score.out。第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出
