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

1、2015南京市小学生信息学竞赛初赛复习知识要点、典型题（版本）一、知识要点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), I

2、, FFOR I = 1 TO NINPUT 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 if

3、or 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 <= Rm = (L+R) 2 if x = a(m) then print "found" sleep : end end ifif x < a(m) thenR = m - 1elseL = m +

4、 1end ifloopprint "Not found!"sleep : end（3）带二分查找的插入排序（已做，需练习）【程序清单】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) 2Do while x <> a( m ) and (L <= R) if x > a(m) then L = m + 1elseR = m 1 end ifm = (L+R) 2 lo

5、opif x <> a(m) then for j = i-1 to L step -1 a(j+1) = a(j) next j a(L) = xelsefor j = 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年江苏省“信息与未来”小学生夏令营将在常州市局前街小学进行，该校的何老师得知本校营员小明同学被营委会选为夏令营的

6、小旗手，就准备到他家去通知他。由于他不是本班的学生，所以何老师不知道小明家住在什么地方，只从其他同学那里得知，小明住在未来小区一幢不超过100层的高楼中，但在哪一层不清楚。其他同学提供了三条有用的信息：1）小明家的楼层号是一个素数；2）该楼层号化为二进制数后，其中1的个数是偶数；3）满足以上两个条件中，楼层号最大的一个。请你写一个程序，计算并输出满足条件（1、2）的楼层个数总数及小明家的楼层号。【输入】本题无输入。【输出】两个整数，即楼层个数总数和小明家的楼层号。（2）狐狸找兔子(hide.bas)（已做）【问题描述】围绕着山顶有10个洞，一只兔子和一只狐狸各住一个洞，狐狸总想吃掉兔子。一天，

7、兔子对狐狸说：你想吃我有一个条件，就是第一次隔一个洞找我，第二次隔两个洞找我，以后依此类推，次数不限。若能找到我，你就可以饱餐一顿，在没有找到我之前不能停止。狐狸一想只有10个洞，寻找的次数又不限，哪有找不到的道理，就答应了条件。结果就是没找着。现请你编写一个程序，假定狐狸找了1000次，兔子躲在哪个洞里才安全。（3）循环报数()（已做，需练习）【问题描述】 现有N个人围成一圈（N为输入的数据），按1M的间隔报数（M也是一个输入的数据）。根据报数的结果发现，第一个出列的人是1号，第二个出列的人是2号，第三个出列的人是3号，最后一个出列的人是N号。问原来这N个人的排列位置是怎样的？【输入】 两个

8、整数N和M，表示人数和报数的间隔。【输出】一行共N个数，即这N个人原来的排列顺序。（4）环绕数(round.bas)（已做，需练习）【问题描述】一个环绕数有如下三个特点：a) 每个数字指示了它下一个数字的位置（自左向右数，数到末尾后，再绕到最左位往右数）；b) 组成这个环绕数的数字只轮到一次；c) 当所有数字都轮过一次后，正好回到第一次开始所取到的那个数字。例如，3162就是一个环绕数：l 取该数任一数字作为开始，如取1；l 由此数字开始向右数1位，轮到了数字6；l 由6向右数，数到2时绕回到3，再向左数共数6位，就轮到了数字3；l 由3向右数3位，便轮到了数字2；l 由2绕回到3再向右数，共

9、数2位，于是回到1。【任务】求以3开头的四位数中，共有几个环绕数，分别为多少？（5）2N个好人与坏人问题（已做，需练习）【问题描述】有N个好人与N个坏人首尾相接地站成一圈（N为输入的一个整数，且前N个人为好人，后N个人为坏人），按照报数间隔M进行1到M地循环报数（即每报到M的人就出列），但M未知。你的任务是求出一个最小的报数间隔M，使得最先报出的N个人都是坏人。【输出】 一个整数，表示N。【输出】 一个整数，即所求出的报数间隔M。【输入样例】 3【输出样例】 53. 排序、新型排序、复杂排序（已做，需练习）（1）命名那个数字（ namenum.bas ）【问题描述】在威斯康辛州牛大农场经营者之

10、中，都习惯于请会计部门用连续数字给母牛打上烙印。但是，母牛用手机时并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴，而不是用像这个的语句“C'mon, #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"

11、的文件中，它包含一连串的少于 5000个可接受的牛名字（所有的名字都是大写的）。收到母牛的编号返回那些能从编号翻译出来并且在字典中的名字。举例来说，编号 4734 能产生的下列各项名字：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

12、HRFG HRFH HRFI HSDG HSDH HSDIHSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEIIPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFIISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI碰巧，81个中只有一个“GREG”是有效的（在字典中）。现在，请你写一个程序来对给出的编号打印出所有的有效名字，如果没有则输出“NONE”。编号可能有12位数字。【输入】（ )单独的一行包含一个编号（长度可能从1到12

13、）。【输出】（ ）以字典顺序输出一个有效名字的不负列表，一行一个名字。【样例输入】4734【样例输出】GREG（2）分数线划定(score.bas)（已做，需练习）【问题描述】世博会志愿者的选拔工作正在 A 市如火如荼地进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。【输入】输入

14、文件名为 score.in。第一行，两个整数n，m（5 n5000，3 mn），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000k9999）和该选手的笔试成绩s（1s100）。数据保证选手的报名号各不相同。【输出】输出文件 score.out。第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名

15、号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。【输入输出样例】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）三值排序（）（已做，需练习）【问题描述】同学们已经学过若干种排序方法，也解过不少有关排序的问题。现在，我们来看一种三值排序问题

16、，即给你一个数字序列，该序列中只有三种不同的值。这种序列在我们日常生活中也能见到，例如，当我们给某项竞赛的优胜者按金银铜牌排序的时候，就会出现这样的序列。在我们这个任务中，可能的值只有三种：1，2和3。我们用交换的方法，把它们排成升序序列。现在，请你写一个程序，计算出当给定一个长度为N的、由1、2、3组成的数字序列后，将该序列排成升序所需要的最少交换次数。【输入】键盘输入：第一行是一个整数，表示N（1<=N<=1000）；接下来的第二行到N+1行，每行输入一个1到3之间的整数。【输出】屏幕输出一个数字，表示排成升序所需要的最少交换次数。【样例输入】9221333231【样例输出】4

17、4. 字符串（已做，需练习）（1）分离单词要求从文件中读入英文句子或段落，再分离单词。5. 数位分离、进制转换（已做，需练习）（1）将二进制数化为十进制数，包含小数。（2）将十进制数化为二进制数，包含小数。（3）如果一个十进制数是回文数，把它转换成二进制数后仍为回文数，这个数称为绝对回文数。找出11，500以内的绝对回文数。（4）求最大公约数与最小公倍数（已做）【问题描述】输入二个二进制整数（长度不超过20位），求出其最大公约数与最小公倍数，并用二进制数输出。例如：输入：11，100输出：1 1100【输入】两个二进制数。【输出】用二进制数表示的最大公约数与最小公倍数（4）进制数（已做）【问题

18、描述】给出一个正整数N（1=N=1023），将其化为10位二进制数，然后计算出二进制数中的“1”的个数，若1的个数为奇数，则在最高位前加一个1，否则加一个0，最后将在此基础上形成一个11位二进制数，用3个十六进制数输出。例如：输入23，化为二进制数为：0000010111，因为1的个数为4，在最高位前加0，得到00000010111。输出：0H，1H，7H【输入格式】键盘输入。一个正整数N。【输出格式】根据形成的11位二进制数，用3个十六进制数输出。【样例】输入：453输出：5H，CH，5H（5）数列（）（已做）【问题描述】给定一个正整数k(3k15),把所有k的方幂及所有有限个互不相等的k的

19、方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：1，3，4，9，10，12，13，（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，）请你求出这个序列的第N项的值（用10进制数表示）。例如，对于k=3，N=100，正确答案应该是981。【输入文件】输入文件sequence.in 只有1行，为两个正整数k和N（k、N的含义与上述的问题描述一致，且3k15，10N1000）。【输出文件】输出文件sequence.out 为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。（整数前不要有空格和其他符号）。【输入样例】 3,1

20、00【输出样例】981（6）海明码（hamming.bas）【问题描述】给出 N，B 和 D：找出 N 个编码（1 <= N <= 64），每个编码有 B 位（1 <= B <= 8），使得两两编码之间至少有 D 个单位的“海明距离”（1 <= D <= 7）。“海明距离”是指对于两个编码，他们的二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234 之间的区别（0x554 表示一个十六进制数，每个位上分别是 5，5，4）： 0x554 = 0101 0101 0100 0x234 = 0010 0011 0100 不同的二进制位:

21、 xxx xx因为有五个位不同，所以“海明距离”是 5。【输入】输入文件名为，文件中只有一行，包括 N, B, D。【输出】输出文件名为，其中共有N 个编码（用十进制表示），要排序，十个一行。如果有多解，你的程序要输出这样的解：假如把它化为 2B 进制的数，它的值要最小。【样例输入】16,7,3【样例输出】0 7 25 30 42 45 51 52 75 7682 85 97 102 120 1276. 进制穷举、复杂穷举、穷举的优化（1）丑数(humble.bas)（已做，需练习）（）【问题描述】对于一个给定的素数集合 S = p1, p2, ., pK（也就是说，p1、p2、pk都是给定的

22、素数），考虑那些质因数全部属于S 的数的集合这个集合中的数包括：p1, p1*p2, p1*p1, p1*p2*p3,。称由这些数构成的集合为相应S的丑数集合。注意：规定 1 不是丑数。你的任务是对于输入的集合S，去寻找丑数集合中第N个丑数。【输入】(humble.in)第1行：两个由空格隔开的整数K 和 N，此处1<= K<=100，1<=N<=100,000；第 2 行：K个由空格隔开的整数，它们都是集合S的元素。【输出】(humble.out)一行，输出第N个丑数。【输入样例】4 192 3 5 7【输出样例】277. 生成法求全排列（已做，需练习）【程序清单】D

23、IM AS INTEGER N, I, SINPUT NDIM AS INTEGER A(n)FOR I=1 TO N A(i)=INEXT IDO S=S+1 FOR I=1 TO NPRINT A(i); NEXT I PRINT FOR I=N TO 2 STEP -1 IF A(i-1)<A(i) THEN M=I-1:EXIT FOR NEXT I IF I=1 THEN EXIT DOI=N DO IF A(i)>A(m) THEN SWAP A(i),A(m):EXIT DO I=I-1LOOPI=M+1J=N DO SWAP A(i),A(j)I=I+1 J=J-1

24、 LOOP UNTIL I>=JLOOPPRINT SSLEEP : END8. 组合取数（已做，需练习）【程序清单】DIM AS INTEGER N, R, S, I, JINPUT N，RDim AS INTEGER b(r)S = 0FOR I = 0 TO R 产生初始的、也是第一种排列 B（I）=INEXT IDO WHILE B(0)=0S=S+1FOR I = 1 TO R 打印当前这一组组合的排列情况PRINT B（I）；“ ”；NEXT IPRINTJ=RDO WHILE B(J)=NR+ J 若允许R=N，则要改一下条件，否则会出现问题J=J-1LOOPB（J）=B（

25、J）+1FOR I = J+1 TO R B（I）=B（I-1）+1NEXT ILOOPPRINT “S=”；SSLEEP : END9. 递推迭代深入（1）求数组元素（已做）已知给出任意一个自然数(N<=100)，输出满足下列条件的数组元素及不同方案数，条件是：1) 数组元素由各不相同的自然数组成；2) 最后一个元素必为N；3) 每一个元素都不小于它前面一个元素的平方（第一个元素除外）；4) 数组中包含的元素个数可以不相同，但至少要有一个元素；例如：输入：N=1输出：数组: (1)K=1 用K记录不同的方案数又如： N=5数组： (5)，(1，2，5)，(1，5)， (2,5) K=4

26、（2）回文数列（已做，需练习）【问题描述】对一个正整数K，求出K的所有拆分，并统计输出其中回文数列的个数。所谓回文数列是指该数列中的所有数字，从左向右或从右向左看都相同。例如，K=4时，有如下的拆分： 4 = 1 + 1 + 1 + 1 回文数列1 = 1 + 1 + 2= 1 + 2 + 1 回文数列2= 2 + 1 + 1= 2 + 2 回文数列3= 1 + 3= 3 + 1因此，回文数列共有3个。【输入】一个正整数K（1<K26）。【输出】满足条件的回文数列的个数。【输入样例】4【输出样例】3（3）排序集合（）（已做，需练习）【问题描述】对于集合N=1,2,N的子集，定义一个称为“

27、小于”的关系：设S1=X1,X2,Xi，(X1<X2<<Xi)，S2=Y1,Y2,Yj，(Y1<Y2<<Yj)，如果存在一个k，（0<=k<=mini,j），使得X1=Y1，Xk=Yk，且k=i或X(k+1)<Y(k+1)，则称S1“小于”S2。你的任务是：对于任意的n（n<=31）及k（k<2n），求出第k小的子集。【输入】(sort.in) 输入文件仅一行，包含两个用空格隔开的自然数，n和k。【输出】(sort.out) 输出文件仅一行，是该子集的元素，由小到大排列。空集输出0。【输入输出样例】： 3 4： 1 2 310.

28、 图形打印（1）螺旋方阵（JS2010，T5，10分）（已做）【问题描述】输入一个正整数N（1<=N<=20）后，可以得到一个N*N的数字螺旋方阵，分别求该方阵中的主对角线与副对角线上的数字之和S、P，输出S、P的差。例如：N=5，得到的数字螺旋方阵如下：12345161718196152425207142322218131211109其中，主对角线从左上角到右下角，得到的数字之和为：S=1+17+25+21+9=73；副对角线从右上到左下，得到的数字之和：P=5+19+25+23+13=85，S-P=-12。【输入】一个整数N。【输出】主对角线与副对角线上数字和的差。【样例】 见

29、问题中的举例。11. 高精度计算（1）印度国王的棋盘（JS2010，T3，10分）（已做，需练习）【问题描述】印度国王使用的棋盘有N*N个格子（N无限大），现在从第一个格子开始放麦粒，第一个格子放1粒，第二个格子放2粒，第三个格子放4粒，第N个格子放2(N-1)粒麦粒。请你编程计算从第K格至第M格共有多少粒麦粒。【输入】一行，两个整数K，M（4<=K<M<=100）。【输出】共有多少粒麦粒（结果不超过6位时，直接输出结果；结果超过6位时，只输出结果的最高3位和最低3位，以逗号分隔）。12. 数学类问题（数论问题）(1)数学作业(math.bas)（已做）【问题描述】小明的数学

30、老师布置了一堆数学题作为作业，这些数学题有一个共同的特点，就是都是要求计算出C(N,M)中不同质因子的个数。Steven请你帮他写一个程序，来帮助他尽快地完成这些作业。C(N,M)即求在N个数中选M个数的组合数。【输入格式】(math.in)输入文件中只有一行，其中有两个整数，表示N和M(1<=N, M<=50000)。【输出格式】(math.out) 输出一个整数，表示C(N,M)中质因子的个数。【输入样例】7 3【输出样例】 2（2）细胞分裂(cell.bas)【问题描述】Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家。现在，他正在为一个细胞实验做准备工

31、作：培养细胞样本。Hanks 博士手里现在有N 种细胞，编号从1N，一个第i 种细胞经过1 秒钟可以分裂为Si 个同种细胞（Si 为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入M 个试管，形成M 份样本，用于实验。Hanks 博士的试管数M 很大，普通的计算机的基本数据类型无法存储这样大的M 值，但万幸的是，M 总可以表示为m1的m2次方，即 ，其中m1、m2均为基本数据类型可以存储的正整数。注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4 个细胞，Hanks 博士可以把它们分入2 个试管，每试管内2

32、个，然后开始实验。但如果培养皿中有5个细胞，博士就无法将它们均分入2 个试管。此时，博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。为了能让实验尽早开始，Hanks 博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入M 个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。【输入】输入文件名为 cell.in，共有三行。第一行有一个正整数 N，代表细胞种数。第二行有两个正整数m1、m2，以一个空格隔开，即表示试管的总数M。第三行有 N 个正整数，第i 个数Si 表示第i 种细胞经过1 秒钟可以分

33、裂成同种细胞的个数。【输出】输出文件 cell.out 共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的最少时间（单位为秒）。如果无论 Hanks 博士选择哪种细胞都不能满足要求，则输出整数-1。【输入输出样例 1】12 13-1【输入输出样例1 说明】经过 1 秒钟，细胞分裂成3 个；经过2 秒钟，细胞分裂成9 个；。可以看出，无论怎么分裂，细胞的个数都是奇数，因此永远不能分入2 个试管。【输入输出样例 2】224 130 122【输入输出样例2 说明】第 1 种细胞最早在3 秒后才能均分入24 个试管，而第2 种最早在2 秒后就可以均分（每试管144/(241)=6 个）。故实验最早可以在2 秒后开始。【数据范围】对于 50%的数