青少年信息学（计算机）竞赛：程序设计的基本方法

查字典合肥奥数网讯：青少年信息学（计算机）竞赛：程序设计的基本方法。

一、模块化：

(1) 把一个较大的程序划分为若干子程序，每一个子程序解决一个总是独立成为一个模块；

(2) 每一个模块又可继续划分为更小的子模块；

(3) 程序具有一种层次结构。 注：运用这种编程方法，考虑问题必须先进行整体分析，避免边写边想。

二、自顶向下：

(1) 先设计第一层(即：顶层)，然后步步深入，逐层细分，逐步求精，直到整个问题可用程序设计语言明确地描述出来为止。

(2) 步骤： 首先对问题进行仔细分析，确定其输入、输出数据，写出程序运行的主要过程和任务； 然后从大的功能方面把一个问题的解决过程分 成几个问题，每个子问题形成一个模块。

(3) 特点：先整体后局部，先抽象后具体。

三、自底向上：

(1) 即先设计底层，最后设计顶层；

(2) 优点：由表及里、由浅入深地解决问题；

(3) 不足：在逐步细化的过程中可能发现原来的分解细化不够完善；

(4) 注意：该方法主要用于修改、优化或扩充一个程序。

4.例子：求1到n之间的素数。 解：要求1到n之间的素数，程序要做的事就是从1开始依次找，判断是否是素数，是则打印出来，否则继续往下找，直到n为止。于是初步设想成：

begin read(n); number:=2;

while number〈n do

begin

if number是一个素数 then write(number);

number取下一个值；

end；

end.

第二步：细化“number是一个素数”及“number取下一个值”。

(1) 细化“number是一个素数”： “number是一个素数”这是一个布尔值，当number是一个素数时为true，否则为false。细化如下：

k:=2; lim:=number-1; repeat

if nubmer能被k整除 then

prim:=false else begin

k:=k+1;

prim:=true;

end;

until not(prim) or (k达到lim)；

>>青少年信息学奥林匹克竞赛：算法竞赛

>>青少年信息学竞赛辅导资料

继续下一页阅读

(2) 细化“number取下一个值”：

number:=number+1;

第三步：细化“number能被k整除”及“k达到lim”。

(1) 细化“number能被k整除”：

number mod k=0;

(2) 细化“k达到lim”：

k<=lim;

第四步：补充完整程序。

第五步：从所有的素数除了2之外都是奇数的角度出发优化程序。

程序设计步骤:

1.分析问题： 对要解决的问题，首先必须分析清楚，明确题目的要求，列出所有已知量，找出题目的求解范围、解的精度等。例“第10周练习”第7题——兔子 的繁殖问题，必须找出其繁殖规律。

2.建立数学模型： 对实际问题进行分析之后，找出它的内在规律，就可以建立数学模型。只有建立了模型的问题，才能可能利用计算机来解决。如上例，可推出递 推公式u[n]=u[n-1]+u[n-2](这是菲波那契数列)

3.选择算法： 建立数学模型后，还不能着手编程序，必须根据数据结构，解决问题的算法。一般选择算法要注意：

(1) 算法的逻辑结构尽可能简单；

(2) 算法所要求的存贮量应尽可能少；

(3) 避免不必要的循环，减少算法的执行时间；

(4) 在满足题目条件要求下，使所需的计算量最小。

4.编写程序： 把整个程序看作一个整体，先全局后局部，自顶向下，一层一层分解处理，如果某些子问题的算法相同而仅参数不同，可以用子程 序来表示。

5.调试运行；

6.分析结果；

7.写出程序的文档： 主要是对程序中的变量、函数或过程作必要的说明，解释编程思路，画出框图，讨论运行结果等。

8.例1：输入奇数n，计算并输出n位的魔方阵。

说明：

(1) 魔方阵就是n*n个不同的正整数按方阵排列时，它的每一行，每一列以及沿对角线的几个数的和具有同一性质的方阵。

(2) 由1到n*n个自然数数构成的魔方阵是最基本的，又称为“幻方”，这种方阵的每行、每列和每个对角线上的元素的和全部相等，亦即等于一个 常数。该常数是n(n*n+1)/2 。

(3) 方法： 首先确定1的位置，通常放在第一行的中间位置； 然后当前自然数的右上方放下一个自然数； 如果当前自然数在第一行但不在最右侧

，则下一个自然数在最后一行，列数右移一列； 如果当前自然数在第一行最右侧，则下一个自然数在当前自然数的下侧； 如果当前自然数在其 它行的最右侧，则下一个自然数在上一行的最左侧。

9.例2：任何一个整数的立方都可以写成一串奇数之和。

说明：

(1)这是著名的尼科梅切斯定理。即 1^3=1 2^3=3+5=8 3^3=7+9+11=27 ……

(2)数据间关系的规律：

•n^3是n个奇数之和，如2^3是2个奇数之和，3^3是3个奇数之和；

•这n个奇数是相邻的，只要知道各式的第一个奇数也就知道所有的n个奇数： 组成1^3的1个奇数是奇数序列中的第1个奇数； 组成2^3的2个奇数中最大的奇数是奇数序列中的第3(3=1+2)个奇数(值为5)； 组成3^3的3个奇数中最大的奇数是奇数序列中的第6(6=1+2+3)个奇数(值为11)； 由此推出：

组成n^3的n个奇数中最大的奇数是奇数序列中的第m(m=1+2+3+...+n)个奇数，即： m=n(n+1)/2

•奇数序列中第m个奇数的值是：modd=2m-1 modd表示“第m个奇数”，是组成n^3的奇数序列中最大的一个奇数。 例如，第2个奇数是3，第6个奇数是11。

•n^3=modd+(modd-2)+(modd -4)+...(modd -2(n-1))

【青少年信息学（计算机）竞赛：程序设计的基本方法】相关文章：

★ 2015深圳走美杯四年级初赛真题&解析

★ 第七届“走美杯”小学四年级初赛试题

★ 2010年第八届走美四年级初赛试题及答案

★ 2015年第十三届走美杯决赛四年级获奖名单

★ 春蕾杯获奖作文：《对带病工作说“不”》

★ 2015年第13届走美杯各年级获奖名单（慈溪赛区）

★ 2015年第13届走美杯长沙赛区决赛初一年级获奖名单

★ 2013年第十一届走美杯宁波赛区报名及考点情况

★ 2013年第十八届华杯赛重庆地区取消初赛

★ 2011年走美杯五年级真题及答案汇总