快动网公共基础知识视频教程配套电子教材(pdf完整版本)(2)

2.归纳法

简单的说，就是列举少量的特殊情况，分析找出一般的关系，但是实际问题中不是件容易的事，要①细心的观察→②丰富的联想→③不断的尝试→④总结归纳。归纳即为抽象，对结果只是一种猜测（即归纳假象），所以必须严格的证明结果。

例如上面我们找出每一项之间的关系最终得出一个规律求出分子和分母这就属于归纳法。3.递推法

递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。例如阶乘计算,现在要求出5的阶乘。C程序如下:1.#include"stdio.h"2.main()3.{

4.intn,s=1;

5.for(n=1;n<=5;n++)6.{

7.s=s*n;/*1的阶乘为1,1的阶乘乘以2就是2的阶乘,2的阶乘乘以3就是3的阶乘,以此类

推,直到求出5的阶乘*/

8.}

9.printf("5!=%d",s);10.}分析：

第5行到第8行采用一个循环结构总共递推5次第7行就是具体递推出下一个值。

4.递归

程序调用自身的编程技巧称为递归，例如c语言中学习的递归调用。

一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。上面的阶乘程序我们改成c语言递归实现：

1.#include"stdio.h"

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

2.longfactorial(longnum){3.if(num==1){4.return1;5.}

6.returnnum*factorial(num-1);7.}

8.main()9.{

10.printf("5!=%d",factorial(5));

11.}

分析：

第2行到第7行定义一个求阶乘的函数，该函数通过递归调用进行求解。

5.穷举法

穷举法是编程中常用到的一种方法,通常在找不到解决问题的规律时对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解。

例如用穷举法求百元百鸡问题,公鸡5元一只,母鸡3元一只,小鸡1元三只。现有100元要买100只鸡,需包含公鸡、母鸡和小鸡,求可能有哪几种方案。程序如下：

1.#include"stdio.h"2.main()3.{

4.inti,j,k,n=0;/*变量n表示方案数*/

5.for(i=1;i<20;i++)/*变量i表示公鸡的数量,就算全部买公鸡也只能买20只*/6.for(j=1;j<33;j++)/*变量i表示母鸡的数量,就算全部买母鸡也只能买33只*/7.for(k=1;k<300;k++)/*变量i表示小鸡的数量,就算全部买小鸡也只能买300只*/8.if(int(i*5+j*3+k*1/3)==100&&i+j+k==100){/*一共100元,并且正好100只鸡*/9.n++;10.printf("n=%d,cook=%d,hen=%d,chick=%d\n",n,i,j,k);11.}12.}分析：

第5行到第13行为第一层循环，第6行到13行为第二层循环，第7层到13行为第三层循环通过三层循环进行穷举，列出所有可能的方案

第9行为判断是否是100元买了100只鸡，注意int(i*5+j*3+k*1/3)只所以要转换成整数是因为小鸡的价格是3毛一只，计算得出的金额是小数所以要转换为整数才能和100比较。

第5行的循环体for后边没有用大括号，因为它的循环体就是第6行开始的循环体。同理第6行和第7行的循环体也都没有用大括号。

6.减半递推技术(分治法)

减半递推即将问题的规模减半，然后，重复相同的递推操作。例如，一元二次方程的求解，二分查找等。7.回溯法

有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。对于

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

这类问题，只能采用试探的方法，通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换别的路线进行试探。这种方法，即称为回溯法。

如人工智能中的机器人下棋，再例如八皇后问题，八皇后问题是一个古老而著名的问题。该问题是在8*8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后不允许处在同一横排,同一纵列,也不允许处在同一与棋盘边框成45度角的斜线上。问有多少种摆法。

1.1.2算法的复杂度

算法的复杂度分为时间复杂度和空间复杂度。其作用是：时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。 时间复杂度

时间复杂度即实现该算法需要的计算工作量。为了能够比较客观地反映某个算法的效率，在度量一个算法的工作量时不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需要基本运算的执行次数来度量算法的工作量。

基本运算反映了算法的主要特征，因此用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。例如在求几个数的累加和时可以将每次累加的运算作为基本运算，再比如在数组中查找一个元素时可以把与数组元素的比较运算作为基本运算。1.O(n)

求1到n的累加和我们用以下程序实现：

1.intj,sum=0,n=10;2.for(j=1;j<=n;j++)3.sum=sum+j；分析：

第1行定义三个变量，j作为循环变量，sum作为累加和变量，n就是累加数的量大值第2行到第3行用一个for循环进行累加运算这个程序的基本运算应该是第3行，第3行的执行次数为n次，当然第1行和第2行也是要执行的，但是我们前边说了要用基本运算的执行次数去度量一个算法的工作量所以这两行我们略去不计。该程序的问题规模是n，算法所需要的时间为T(n)，T(n)是n的某一函数，T(n)称为这一算法的“时间复杂度”。

通常情况我们常用大O表示法来表示时间复杂性即“大O记法”，在这种描述中使用的基本参数是n，即问题实例的规模，把复杂性或运行时间表达为n的函数即为O(n)，所以说该算法的时间复杂度为O(n)。

2.O(n^2)

我们将上面的程序变化一下：

1.inti,sum=0；

2.for(i=1;i<=n;i++)

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

3.for(j=1;j<=n;j++)4.sum++；分析：

在该程序中第4行为基本运算，它的执行次数为n*n，因为是双重循环，也就是n的2次方，那么它的时间复杂度表示为：O(n^2)3.O(log2n)

再看一个例子：

1.i=1;

2.while(i<=n)3.i=i*2;分析：

第3行为基本运算，它的执行次数为多少次呢？是n次吗？不是，因为i=i*2，i不是每次循环自增1。我们可以认为第3行的执行次数最大为log2n次，那么它的时间复杂度就为O(log2n)。4.O(3n)再例如：

1.a=0;2.b=1;

3.for(i=1;i<=n;i++)4.{5.s=a+b;6.b=a;7.a=s;8.}分析：

第5行到第7行为该程序的基本运算，第5行执行n次，第6行执行n次，第7行执行n次，总共执行次数为n+n+n即3n，时间复杂度为O(3n)5.O(1)

以上我们分析的算法都使用了循环结 …… 此处隐藏：3061字，全部文档内容请下载后查看。喜欢就下载吧 ……