常用的算法的表示方法(算法的三种表示方法A版)

1.算法的三种表示方法（A版）

去百度文库，查看完整内容>

内容来自用户：yicaohan

算法的三种表示方法（A版）

自然语言、程序框图和程序语句是算法的三种表示方法，是算法的形式化表示，且它们是严格对应的.例如，以下是给出三个数求其中的最大数的自然语言算法、框图和程序的对应情况，通过本例体会其严密的对应关系.

例 已知，设计程序输入x的值，输出相应的y的值，写出其

算法，画出程序框图并写出其程序.

解：算法步骤为：

第一步：输入x;

第二步：判断x是否大于0，若是，y=1；若不是，y=0;

第三步：输出y.

程序框图为：

程序为：

INPUT “x=”;x

IF x>0 THEN

y=1

ELSE

y=0

END IF

PRINT y

END

点评：本题使用了条件语句“IF…THEN…ELSE…ENDIF”

2.算法的三种表示方法（A版）

去百度文库，查看完整内容>内容来自用户：yicaohan算法的三种表示方法（A版） 自然语言、程序框图和程序语句是算法的三种表示方法，是算法的形式化表示，且它们是严格对应的.例如，以下是给出三个数求其中的最大数的自然语言算法、框图和程序的对应情况，通过本例体会其严密的对应关系.例 已知，设计程序输入x的值，输出相应的y的值，写出其算法，画出程序框图并写出其程序. 解：算法步骤为： 第一步：输入x； 第二步：判断x是否大于0，若是，y=1；若不是，y=0； 第三步：输出y. 程序框图为： 程序为： INPUT “x=”;x IF x>0 THEN y=1 ELSE y=0 END IF PRINT y END 点评：本题使用了条件语句“IF…THEN…ELSE…ENDIF”。

3.什么是算法,常用的算法描述有哪些

算法的描述方式主要有自然语言，流程图，伪代码等，它们的优势和不足可以简单地归纳如下：1、自然语言优势：自然语言描述的算法通俗易懂，不用专门的训练不足：a.由于自然语言的歧义性，容易导致算法执行的不确定性.b.自然语言的语句一般较长，导致描述的算法太长.c.当一个算法中循环和分歧较多时就很难清晰地表示出来.d.自然语言表示的算法不便翻译成计算机程序设计语言.2、流程图优势：流程图描述的算法清晰简洁，容易表达选择结构，它不依赖于任何具体的计算机和计算机程序设计语言，从而有利于不同环境的程序设计.不足：不易书写，修改起来比较费事，可以借助于专用的流程图制作软件来提升绘制和修改.3、伪代码优势：伪代码回避了程序设计语言的严格、烦琐的书写格式，书写方便，同时具备格式紧凑，易于理解，便于向计算机程序设计语言过渡的优点.不足：由于伪代码的种类繁多，语句不容易规范，有时会产生误读.。

4.简述算法的各种表示形式

一、什么是算法 算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

时间复杂度用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O(1)常数阶；O(log2n)对数阶；O(n)线性阶；O(n2)平方阶。

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。

同时间复杂度相比，空间复杂度的分析要简单得多。 二、算法设计的方法 1.递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。

设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1,2，…，i-1的一系列解，构造出问题规模为I的解。

这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。 【问题】 阶乘计算 问题描述：编写程序，对给定的n(n≤100)，计算并输出k的阶乘k!(k=1,2，…，n)的全部有效数字。

由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a[ ]存储： N=a[m]*10m-1+a[m-1]*10m-2+ … +a[2]*101+a[1]*100 并用a[0]存储长整数N的位数m，即a[0]=m。

按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素……。例如，5!=120，在数组中的存储形式为： 3 0 2 1 …… 首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。

计算阶乘k！可采用对已求得的阶乘（k-1）！连续累加k-1次后求得。例如，已知4!=24，计算5！，可对原来的24累加4次24后得到120。

细节见以下程序。 # include # include # define MAXN 1000 void pnext(int a[ ],int k) { int *b,m=a[0],i,j,r,carry; b=(int * ) malloc(sizeof(int)* (m+1)); for ( i=1;i0;i--) printf(“%d”,a[i]); printf(“\n\n”); } void main() { int a[MAXN],n,k; printf(“Enter the number n: “); scanf(“%d”,&n); a[0]=1; a[1]=1; write(a,1); for (k=2;k1时)。

写成递归函数有： int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2)； } 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。

例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。

依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。

例如在函数fib中，当n为1和0的情况。 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。

在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。

由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。

例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。 【问题】 组合问题 问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。

例如n=5,r=3的所有组合为： （1）5、4、3 (2)5、4、2 (3)5、4、1 (4)5、3、2 (5)5、3、1 (6)5、2、1 (7)4、3、2 (8)4、3、1 (9)4、2、1 (10)3、2、1 分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。

当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。

设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字。