大一上学期算法

1、要使计算机解决一个问题，必须首先针对问题设计一个解题步骤，然后将解题步骤用程序代码实现，由程序解决指定的问题。所谓的算法，就是指问题的解题步骤，而程序则是用某种程序设计语言对解题步骤的描述。 由此可见，算法是问题求解规则的一种过程描述。在算法中，要精确定义一系列操作，以便在有限的步骤内得到问题的解。 算法的设计一般采用由上至下，逐步求精的方法。算法算法会因求解问题的不同而千变万化，但是它们都具有如下特性：（1）确定性：算法中的每一步骤都必须有明确的定义，不存在歧义。（2）有穷性：算法必须在有限的步骤之后终止。（3）可行性：算法的每一步骤都可以通过有限个已经实现的基本操作来实现。（4）输入：一个

2、算法有零个或多个输入。（5）输出：一个算法应该至少有一个输出。累加与累乘累加与累乘是最基本的算法，一般依靠循环结构来实现。累加就是在原来的和的基础上一次又一次地再加上一个数；累乘又叫连乘是在原来积的基础上一次又一次地再乘上一个数。穷举法 穷举法是对所有可能是解的候选解按某种顺序进行逐一枚举和检验，从中找出那些符合要求的候选解作为问题的解。一般采用循环实现。 【例3- 107】数字灯谜。设有算式: ABCD-） CDC ABC递推法 递推法又称迭代法，是利用问题本身所具有的一种递推关系求问题解的方法。设要求问题的规模为N的解，当N=1时，解或为已知，或能非常方便地得到。能采用递推法构造算法的问题

3、一定有着递推性质，即当得到问题规模为i-1的解后，能从已求得的规模为1，2，i-1的一系列解，构造出问题规模为i的解。这样，程序可以从i=0或i=1出发，由已知i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。 【例3- 108】打印斐波那契(Fibonacci)数列的前20项斐波那契数列如下: 0，1，1，2，3，5，8，13，即从第三项起每一项是其前两项之和递归算法 如果一个规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解方法和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模

4、稍大问题的解，那么就可以用递归算法求解。通俗的讲，就是用自身的结构来描述自身。N! 辗转相除法 用辗转相除法求两自然数m，n的最大公约数和最小公倍数。解：求最大公约数的算法： (1)对于已知两数m，n，使得mn； (2) m除以n得余数r； (3)若r=0，则n为最大公约数结束；否 则执行(4)； (4)mn，nr，再重复执行(2)。求得了最大公约数后，最小公倍数就是将原来的两个数相乘后除以最大公约数。 If m n Then t = m: m = n: n = tr=m mod nDo While (r 0) m=n n=r r= m mod nLoopPrint 最大公约数=, n 数组排

5、序 对于n个数按递增或递减的次序进行的排列，叫排序。排序有很多种，如选择排序、冒泡排序等。 选择法对已知的六个数9、8、7、6、5、0，用选择法递增排序解：(1)从n个数的序列中选出最小的数(递增),与第1个数交换位置; (2)除第1个数外，其余n-1个数再按(1)的方法选出次小的数，与第2个数交换位置; (3)重复(1)n-1遍，最后构成递增序列。 冒泡法 对已知的六个数9、8、7、6、5、0，用冒泡法递增排序解：冒泡法排序与选择排序相似，选择法排序在每轮循环找到的第n小的数字的时候，就将其和第n个位置交换；而冒泡法排序在每轮循环找到的第n小的数字的时候，就和相邻的数做比较，当次序不符合要求时就交换位置，移到第n个位置。 数组查找 顺序查找 二分法查找 用二分法查找可以提高效率，但在使用前被查找数组必须有序。High：表示查找范围的顶部Low：表示查找范围的底部 Mid：表示查找范围的中间Mid=(high+low)2取整要