1.2 程序和程序逻辑

学习目标

1）掌握算法与程序的概念。

2）了解算法的基本描述方法。

实例3 程序与算法的概念——梵塔推理

实例任务

将1号柱大小不等的三个物体，移动到3号柱上，顺序必须与1号柱顺序一致。要求每次只移动一个物体，而且每根柱上小块物体必须置于大块物体之上。其移动过程如图1-10所示。

相关知识

1.程序

程序包括两部分，一是对数据的描述，即数据结构；二是对操作的描述，即操作步骤，也称为算法，它指明了解决某一具体问题的方法和步骤。因此，计算机科学家Nikiklaus Wirth提出了如下公式：

数据结构+算法=程序

就算法而言，大致可分为两大类：一类是数值运算算法，用于求解数值；另一类是非数值运算算法，用于分析推理和逻辑推理。如实例中的梵塔推理并非求解一定的数值，而只是完成一定的推理操作。

2.算法的自然语言描述

实例为梵塔推理难题的解题步骤，也是人逻辑思维的基本方法。计算机的算法思想与此类似，只是表示方法不同而已。

用计算机解此题的难点在于，如何用数据结构表示每块物体的所在位置，以及如何描述某一物体由1号柱移动到2号柱这一动作，这也是算法设计的关键所在。梵塔推理可以用自然语言表示如下：

将A由1号柱移到3号柱mov(A:1,3 )

将B由1号柱移到2号柱mov(B:1,2 )

将A由3号柱移到2号柱mov(A:3,2 )

将C由1号柱移到3号柱mov(C:1,3 )

将A由2号柱移到1号柱mov(A:2,1 )

将B由2号柱移到3号柱mov(B:2,3 )

将A由1号柱移到3号柱mov(A:1,3 )

实例4 算法图形描述——求n!

实例任务

数学上，阶乘n!=1×2×3×…×n。现要求输入n的值，求出n!的值。程序的运行结果如图1-11所示。

程序代码

相关知识

1.N-S图

流程图除用自然语言描述外，还可以使用图形来描述，常用的流程图有传统流程图和N-S图。N-S图又称为结构化盒图，它使用一种方框来描述程序的基本结构。本实例程序可绘制成如图1-12所示的N-S图。

2.传统流程图

传统流程图是通过指定的几何图形框和箭头线来描述各个环节的操作和执行的过程。这种描述方法比较直观，而且程序走向清晰，非常易于读者理解，易于编写C语言代码。但如果程序比较复杂，则使用传统流程图描述比较烦冗，不易理解。本实例程序可绘制成如图1-13所示的传统流程图。

在传统流程图中，长方形框表示执行一定的操作，如赋值或计算等；菱形框表示条件判断；椭圆矩形框表示程序的开始与结束；平行四边形表示输入输出数据；箭头表示程序语句的执行方向。

课堂精练

1）用N-S图描述1+2+3+…+10的值的算法。请将图1-14中的空缺语句补充完整。

2）用传统流程图描述1+2+3+…+10的值的算法。请将图1-15中的空缺语句补充完整。