ns结构流程图是什么

　　NS图是用于取代传统流程图的一种描述方式。 以 SP方法为基础，NS图仅含有下图 的5种基本成分，它们分别表示SP方法的几种标准控制结构。

　　在NS 图中，每个"处理步骤"是用一个盒子表示的，所谓"处理步骤"可以是语句或语句序列。需要时，盒子中还可以嵌套另一个盒子，嵌套深度一般没有限制，只要整张图在一页纸上能容纳得下，由于只能从上边进入盒子然后从下边走出，除此之外没有其他的入口和出口，所以，NS图限制了随意的控制转移，保证了程序的良好结构。用NS图作为详细设计的描述手段时，常需用两个盒子:数据盒和模块盒，前者描述有关的数据，包括全程数据、局部数据和模块界面上的参数等，后者描述执行过程。

　　NS图的优点:

　　首先，它强制设计人员按SP方法进行思考并描述他的设计方案，因为除了表示几种标准结构的符号之处，它不再提供其他描述手段，这就有效地保证了设计的质量，从而也保证了程序的质量;第二，NS图形象直观，具有良好的可见度。例如循环的范围、条件语句的范围都是一目了然的，所以容易理解设计意图，为编程、复查、选择测试用例、维护都带来了方便;第三，NS图简单、易学易用，可用于软件教育和其他方面。

　　NS图的缺点:

　　手工修改比较麻烦，这是有些人不用它的主要原因。

流程图也叫框图，它是是用各种几何图形、流程线及文字说明来描述计算过程的框图。用流程图描述算法的优点是：直观，设计者的思路表达得清楚易懂，便于检查修改。

6.1 算法的描述方法
1、用自然语言表达
所谓的“自然语言”指的是日常生活中使用的语言，如汉语、英语或数学语言。

例如：我们想计算1到N的累加和，为简单起见，设N的值不大于1000。

算法可以使用自然语言描述如下：

S1：输入n（要求n<=1000）；

S2：累加和sum置初值0；

S3：自然数i置初值1；

S4：若i<=n， 则重复执行：

S41：i+sum —> sum；

S42：i+1 —>i

S5：输出sum，结束。

这就是用自然语言配合数学语言描述算法。

用自然语言描述的算法通俗易懂，而且容易掌握，但算法的表达与计算机的具体高级语言形式差距较大，通常是用于介绍求解问题的一般算法。

2、用伪代码表示
伪代码是一种介于自然语言与计算机语言之间的算法描述方法。它结构性较强，比较容易书写和理解，修改起来也相对方便。其特点是不拘泥于语言的语法结构，而着重以灵活的形式表现被描述对象。它利用自然语言的功能和若干基本控制结构来描述算法。

伪代码没有统一的标准，可以自己定义，也可以采用与程序设计语言类似的形式。

3、用传统流程图描述算法
流程图也叫框图，它是是用各种几何图形、流程线及文字说明来描述计算过程的框图。用流程图描述算法的优点是：直观，设计者的思路表达得清楚易懂，便于检查修改。

表6.1是用传统流程图描述算法时常用的符号。

表6.1流程图常用符号

流程图符号 含义

数据输入/输出框，用于表示数据的输入和输出

处理框，描述基本的操作功能，如“赋值”操作、数学运算等

两分枝判断框，根据框中给定的条件是否满足，选择执行两条路径中的一条

开始/结束框，用于表示算法的开始与结束

连接符，用于连接流程图中不同地方的流程线

流程线，表示流程的路径和方向

条件

1 2 . . . n
多分支判断框，根据框中的“条件值”，选择执行多条路径中的一条

注释框，框中内容是对某部分流程图做的解释说明

用流程图描述算法时，一般要注意以下几点：

（1）应根据解决问题的步骤从上至下顺序地画出流程图，各图框中的文字要尽量简洁。

（2）为避免流程图的图形显得过长，图中的流程线要尽量短。

（3）用流程图描述算法时，流程图的描述可粗可细，总的原则是：根据实际问题的复杂性，流程图达到的最终效果应该是，依据此图就能用某种程序设计语言实现相应的算法（即完成编程）。

4、N-S结构化流程图
N-S结构化流程图主要特点是取消了流程线，全部算法由一些基本的矩形框图顺序排列组成一个大矩形表示，即不允许程序任意转移，而只能顺序执行，从而使程序结构化。

N-S图也是流程图的一种很好的表示方法，对应于三种基本结构的N-S图如图6.2所示。

S1

S1

条件

T F

S1

S2

(1)顺序结构 (2)选择结构

当“条件”满足

S1

直到“条件”满足

S1

(3)循环结构

图6.2 N-S图的三种基本控制结构

图中“S1”或“S2”既可以是简单功能的操作，如数据赋值、数据的输入或输出等，也可以是三种基本控制结构中的1种。

在我们的教材中有一些简单的例题，比较详细地示范了如何使用这些算法的描述方法进行算法描述，请大家认真进行自学，通过例题，体会一下这些常用的算法描述方法。

6.2 算法设计中的基本方法

人们希望计算机求解的问题是千差万别的，所设计的求解算法也千差万别，一般来说，算法设计没有什么固定的方法可循。但是通过大量的实践，人们也总结出某些共性的规律，其中包括递归方法、分治方法、贪心法、回溯法、动态规划法以及平衡原则等等。

在我们的课程中不可能对每一种算法都进行深入的讲解，我们只选择最基本、最典型的的穷举法进行一些讨论，以使大家对于算法和算法设计方法有一个初步的了解。

1、程序设计的一般步骤
我们在拿到问题之后，不可能马上就动手编程解决问题，要经历一个思考、编程的过程，对于一般的小问题，我们可以进行简单处理，按照下面给出的5步进行求解：

第1步：明确问题的性质，分析题意

我们可以将问题简单地分为：数值型问题和非数值型问题。不同类型的问题可以有针对性地采用不同的方法进行处理。

第2步：建立问题的描述模型

对于数值型问题，我们可以建立数学模型，通过数学模型来描述问题。对于非数值型问题，我们一般可以建立一个过程模型，通过过程模型来描述问题。

第3步：设计/确定算法

对于数值型的问题，我们可以采用数值分析的方法进行处理。在数值分析中，有许多现成的固定算法，我们可以直接使用，当然我们也可以根据问题的实际情况设计算法。

对于非数值型问题，我们可以通过数据结构或算法分析与设计进行处理。也可以选择一些成熟的方法进行处理，例如：穷举法，递推法，递归法，分治法，回溯法等。

在算法确定之后，我们要使用上一节中介绍的算法描述方法对算法进行描述。

第4步：编程调试

根据算法，采用一种编程语言编程实现，然后上机调试，得到程序的运行结果。

第5步：分析运行结果

对于运行结果要进行分析，看看运行结果是否符合预先的期望，如果步符合，要进行判断问题出在什么地方，找出原因对算法或程序进行修正，直到得到正确的结果。

下面我们采用穷举法对数值型问题进行求解，让大家首先来体会一下求解数值问题的思考过程。

2、使用穷举法解决数值型问题
穷举法也叫枚举法或蛮干法。其基本思想是根据面临的问题，逐一列举各种可能的情况，并判断每种情况是否满足题设条件。这种方法的好处是最大限度考虑了各种情况，从而为求出最优解创造了条件。

例1：百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?

问题分析与算法设计
这是一个典型的数值型问题，我们要首先建立这个问题的数学模型，数学模型也就是我们平时说的数学方程。

假设：我们要买x只公鸡，y只母鸡，z只小鸡，根据题目的意思可以得到两个方程：

x+y+z=100 ①

5x+3y+z/3=100 ②

根据题目的意思，我们可以确定x和y的取值范围：0 <= x、y、z <= 100。

我们可以采用穷举法进行求解。对于变量x,y,z的不同组合，看它们是否满足上面的两个方程，如果满足了，就是问题的一个解。如果不满足，就不是问题的解。

我们可以采用三重嵌套的循环对变量x,y,z进行组合。我们可以写出程序1。

程序1：

#include

main( )

{int x, y, z, j=0; /* j为计数器，记录解的数量 */

for (x=0; x<=100; x++) /* 穷举变量x */

for (y=0; y<=100; y++) /* 穷举变量y */

for (z=0; z<=100; z++) /* 穷举变量z */

if ( x+y+z==100 && 5*x+3*y+z/3==100 ) /* 判断是否满足两个方程 */

printf("%2d:cock=%2d hen=%2d chicken=%2d\n", ++j, x, y, z);

}

运行上面的程序，可以得到运行结果：

1: cock= 0 hen=25 chicken=75

2: cock= 3 hen=20 chicken=77

3: cock= 4 hen=18 chicken=78

4: cock= 7 hen=13 chicken=80

5: cock= 8 hen=11 chicken=81

6: cock=11 hen= 6 chicken=83

7: cock=12 hen= 4 chicken=84

分析程序的运行结果，我们应该可以注意到有有三组解有问题，第2、4、6组解中，小鸡的数量不能被3整除。问题到底出在什么地方呢？我们进行进一步分析，将这些解代入方程②：5x+3y+z/3=100，可以看到：

5*3+3*20+77/3=15+60+25.67=100.67≠100

5*7+3*13+80/3=35+39+26.67=100.67≠100

5*11+3*6+83/3=55+18+27.67=100.67≠100

显然，这三组解不满足数学方程，但由于我们在C语言中，进行int型除法时，77/3的结果就是25，80/3的结果就是26，83/3的结果就是27，这也是计算机在处理整型数据时的特点，在进行除法运算时，对于商的小数部分不再进行处理，直接截断。所以就造成了在数学上本来不成立的方程，在计算机中成立了。

产生这个问题的根本原因就是我们在分析问题的过程中忽略了一个重要条件，变量z要能够被3整除。为了解决这个问题我们要在原来两个方程的基础上增加一个判断条件：

z%3==0

经过修改后，我们可以得到新的程序2：

程序2：

#include

main( )

{ int x, y, z, j=0;

for (x=0; x<=20; x++)

for (y=0; y<=33; y++)

for (z=0; z<=100; z++)

if ( z%3==0 && x+y+z==100 && 5*x+3*y+z/3==100 ) /* 增加了z%3==0 */

printf("%2d:cock=%2d hen=%2d chicken=%2d\n", ++j, x, y, z ) ;

}

再次运行程序，可以得到正确的结果：

1: cock= 0 hen=25 chicken=75

2: cock= 4 hen=18 chicken=78

3: cock= 8 hen=11 chicken=81

4: cock=12 hen= 4 chicken=84

为了保证变量z能够整除3，我们还可以换一个思路，在与z有关的for循环上作文章。程序2的循环中变量z每次+1，这样z就很可能不时3的倍数，我们可以对此进行优化，让变量z每次循环不是加1，而是加3，这样就可以保证变量z一定是3的倍数，因此我们就可以省略判断z是否可以被3整除的过程。

按照这样的思路，我们可以得到程序3。

程序3：

#include

main( )

{int x, y, z, j=0; /* j为计数器，记录解的数量 */

for (x=0; x<=100; x++) /* 穷举变量x */

for (y=0; y<=100; y++) /* 穷举变量y */

for (z=0; z<=100; z+=3) /* 穷举变量z，每次增加的步长为3 */

if ( x+y+z==100 && 5*x+3*y+z/3==100 ) /* 判断是否满足两个方程 */

printf("%2d:cock=%2d hen=%2d chicken=%2d\n", ++j, x, y, z);

}

运行程序3，也可以得到正确的结果。

进一步分析程序3，我们还可以看到：穷举变量x的取值范围过大了，x的取值范围只应该在0～20之间，并且，一旦确定了变量x和变量z的值，我们就可以利用方程①直接计算出变量y的值，这样就可以去掉对变量y的穷举过程。

于是我们可以得到程序4。

程序4：

#include

main( )

{ int x, y, z, j=0; /* j为计数器，记录解的数量 */

for (x=0; x<=20; x++)

for (z=0; z<100; z+=3)

{ y = 100-x-z;

if ( 5*x+3*y+z/3==100 )

printf("%2d:cock=%2d hen=%2d chicken=%2d\n", ++j, x, y, z ) ;

}

很显然，程序4的循环减少了一层，变量x的穷举范围也减少了。

我们进一步分析程序，变量z的穷举次数还是太多，我们可以对变量y进行穷举。

在变量x确定的情况下，我们利用方程②：5x+3y+z/3=100，就可以减少求出变量y的穷举范围，这样可以得到程序5。

#include

main( )

{ int x, y, z, j=0; /* j为计数器，记录解的数量 */

for (x=0; x<=20; x++)

for ( y=0; y<=(100-5*x)/3; y++ )

{ z = 100-x-y;

if ( z%3==0 && 5*x+3*y+z/3==100 )

printf("%2d:cock=%2d hen=%2d chicken=%2d\n", ++j, x, y, z ) ;

}

程序5不仅是正确的，而且运行的效率也是比较高的。

例2：小明有5本新书，要借给A、B、C三位小朋友，若每人每次只能借一本，则可有多少种不同的借法？

问题分析与算法设计
这是一个数学中的排列问题，即求从5中取3的排列数。

我们可以对5本书从1至5进行编号，假设三个人分别借这5本书中的1本。当a=i时，表示a借了编号为i的书。

当3个人所借的书的编号都不相同时，就是满足题意的一种借阅方法。

假设：三个人为 a、b、c，则它们的取值范围为：

1 <= a、b、c <= 5

且当：a!=b && a!=c && b!=c 时，即为一种可能的借书方法。

使用穷举法，我们可以得到以下程序：

#include

main( )

{int a, b, c, count=0; /* count为借书方案计数器 */

for ( a=1; a<=5; a++ )

for ( b=1; b<=5; b++ )

for ( c=1; a!=b && c<=5; c++)

/* 当前两个人借不同的书时，穷举第三个人的借本情况 */

if ( c!=a && c!=b )

printf( count%8 ? "%2d:%d,%d,%d" : "%2d:%d,%d,%d\n", ++count, a, b, c );

}

通过这两个例子我们可以看到，我们首先要建立数学模型，这是我们能够正确处理问题的基础，然后要确定合理的穷举范围，如果穷举的范围过大，则运行效率会比较低，如果穷举的范围太小了，则可能丢失正确的结果。

3、使用逐步求精的思想设计算法
我们知道，对于复杂的问题，我们不可能一下就得到程序，正确的可行方法是：先将问题中简单的部分明确出来，再逐步对复杂部分进行细化，然后一步一步推出完整程序。这样一种逐步向前推进的思想就是逐步求精法。

下面我们通过典型输出简单图形的例题，来体会一下使用逐步求精法的思维过程。

例3：打印边长为 m 的正方型。要求：从键盘输入 m 值，输出 m 行每行 m 个*号组成的正方型。例：输入 m=4，输出的图形如下：

* * * *

* * * *

* * * *

* * * *

算法分析与设计
对于上面的问题，我们可以将整个程序的过程分为两大步，写出第1个基本的分析过程：

分析过程1：

1. 从键盘输入 m ，

2. 重复打印 m 行，每行打印 m 个 *；

分析过程1中我们使用的就是自然语言的算法描述。

显然，分析过程1中的第1步比较容易实现，第2步要实现的难度就比较大了，我们可以先对第2步中自然语言的算法描述进行加细，采用类似C语言的循环语句进行细化，这样可以得到分析过程。

分析过程2：

1. 输入 m ；

2. for ( k=1; k<=m; k++)

打印一行中的 m 个 * ；

在分析过程2中，我们采用一个for循环，表示了前一步分析过程中“重复打印m行”这样的自然语言的描述。显然，分析过程2中的描述比分析过程1中的描述要进了一步。

下面，我们可以将“打印一行中的m个*”进行进一步细化，分为两个动作：首先打印m个*，然后在屏幕上换一个新行。这样可以得到更新的分析过程。

分析过程3：

1. 输入m；

2. for ( k=1; k<=m; k++)

2.1 { 打印 m 个 * ；

2.2 换新行;

}

我们可以继续将分析过程3中的“打印m个*”进行细化，采用一个for循环输出m个*。将“换新行”直接变为“输出1个\n”。这样就可以得到分析过程4。

分析过程4：

1. 输入m；

2. for ( k=1; k<=m; k++)

{ for ( j=1; j<=m; j++ )

输出1个*；

输出1个\n ;

}

此时，分析过程4已经非常接近程序了，算法的每一步都可以使用C语言的语句实现了，我们进行整理，按照编写C语言程序的要求，加上必要的函数和变量说明，就可以得到程序如下：

#include

main ( )

{ int k, m, j；

scanf ( ”%d”, &m )；

for ( k=1; k<=m; k++ ) /* 控制打印 m 行 */

{ for ( j=1; j<=m; j++ ) /* 打印一行中的m个*号 */

printf (”*”)；

printf(”\n”)；

}

}

以上这个过程就是一个典型的采用逐步求精法对问题进行逐步分析，最终得到正确程序的全过程。

下面我们再来看一个例子。

例4：从键盘输入h值，输出h行用*号组成等腰三角形。例：输入 h=4，输出的图形如下：

*

* * *

* * * * *

* * * * * * *

算法分析
根据图形的要求，我们可以分析出下列结论：

1、图形按行输出，共输出 h 行。

2、整个图形的每一行中，前面先输出空格，后面再输出*。所以程序的关键是：要找出每一行（第k行）中，输出的空格的数量和*的数量。

3、对于图形中的第 k 行(1<=k<=h)：则要输出 h-k 个 空格 和 2k-1 个 *

算法设计
模仿例3的分析过程，我们可以写出第一个分析过程。

分析过程1：

1.输入 h;

2.重复打印h行。对于第 k 行，每行 h-k 个空格和 2k-1 个*

我们对分析过程1中的第2步进行加细，可以得到进一步的过程：

分析过程2：

1.输入 h;

2. for ( k=1; k<=h; k++ ) /* h行 */

{ 重复打印 h-k 个空格；

重复打印 2k-1 个 *；

换行；

}

到了分析过程2，我们就可以非常容易地继续借助例3中的细化方法推出最后的程序。

程序：
#include

main ( )

{ int h, k, j;

scanf (”%d”, &h);

for ( k=1; k<=h; k++) /* 控制打印 h 行 */

{ for ( j=1; j<=h-k; j++) /* 打印空格 */

printf (” ”);

for ( j=1; j<=2*k-1; j++)/* 打印 * 号 */

printf (”*”)；

printf(”\n”) ;

}

}