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

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 N INPUT N DIM AS INTEGER A(N), I, F FOR I = 1 TO N INPUT A(I) NEXT I J = 1 DO 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 + 1 LOOP UNTIL F = 0 FOR I = 1 TO N PRINT A(I); NEXT I SLEEP : END （2）二分查找（已做） 【程序清单】 dim as integer n input n dim as integer a(n), i, j, x, m for i = 1 to n input a(i) next i for i = 1 to n-1 for j = i+1 to n if a(i) a(j) then swap a(i), a(j) next j next i for i = 1 to n print a(i); ; next i print L = 1 : r = n input x= , x do 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 if loop print Not found! sleep : end （3）带二分查找的插入排序（已做，需练习） 【程序清单】 DIM AS INTEGER n input n DIM AS INTEGER a(n), tail, L, R, m input a(1) for i = 2 to n input x L = 1 : R = i-1 : m = (L+R) \ 2 Do while x a( m ) and (L = R) if x a(m) then L = m + 1 else R = m – 1 end if m = (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 = i-1 to m step -1 a(j+1) = a(j) next j a(m) = x end if next i FOR i = 1 TO n PRINT a(i); NEXT i PRINT SLEEP : END 2. 报数问题、循环数组 （1）夏令营旗手（JS2010，第一题）（已做） 【问题描述】 2010年江苏省“信息与未来”小学生夏令营将在常州市局前街小学进行，该校的何老师得知本校营员小明同学被营委会选为夏令营的小旗手，就准备到他家去通知他。 由于他不是本班的学生，所以何老师不知道小明家住在什么地方，只从其他同学那里得知，小明住在未来小区一幢不超过100层的高楼中，但在哪一层不清楚。其他同学提供了三条有用的信息： 1）小明家的楼层号是一个素数； 2）该楼层号化为二进制数后，其中1的个数是偶数； 3）满足以上两个条件中，楼层号最大的一个。 请你写一个程序，计算并输出满足条件（1、2）的楼层个数总数及小明