程序设计常用算法

程序设计常用算法

程序设计常用算法全文共20页，当前为第1页。算法与程序设计算法—解决现实问题的方法或手段如：求解一元二次方程的解程序设计常用算法全文共20页，当前为第2页。常见算法1、穷举法2、递归法3、迭代法4、递推法程序设计常用算法全文共20页，当前为第3页。1、穷举法穷举法（列举法或枚举法），是蛮力策略的具体体现，是一种简单而直接地解决问题的方法程序设计常用算法全文共20页，当前为第4页。百鸡问题

中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？程序设计常用算法全文共20页，当前为第5页。百鸡问题问题分析与算法设计

设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程：5x+3y+z/3=100x+y+z=100程序设计常用算法全文共20页，当前为第6页。百鸡问题intmain(){

intx,y,z,j=0;printf("Folleingarepossibleplanstobuy100fowlswith100Yuan.\n");for(x=0;x<=20;x++)/*外层循环控制鸡翁数*/for(y=0;y<=33;y++)/*内层循环控制鸡母数y在0~33变化*/{z=100-x-y;/*内外层循环控制下，鸡雏数z的值受x,y的值的制约*/if(z%3==0&&5*x+3*y+z/3==100)/*验证取z值的合理性及得到一组解的合理性*/printf("%2d:cock=%2dhen=%2dchicken=%2d\n",++j,x,y,z);}}程序设计常用算法全文共20页，当前为第7页。穷举框架穷举通常应用循环结构来实现在循环体中，根据所求解的具体条件，应用选择结构实施判断筛选，求得所要求的解穷举法的框架描述：

n=0;for(k=<区间下限>;k<=<区间上限>;k++)//根据指定范围实施穷举

if(<约束条件>)//根据约束条件实施筛选

{printf(<满足要求的解>);//输出满足要求的解

n++;//统计解的个数

}

程序设计常用算法全文共20页，当前为第8页。穷举应用1、找出n个自然数（1,2,3,…,n）中r个数的组合。例如，当n=5，r=3时，求出组合总数及每一个组合。2、几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1～9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。程序设计常用算法全文共20页，当前为第9页。2、递归法

递归法求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解，进而最终导致原问题的解决。1若n=0

n!=n×(n-1)!

若n>0程序设计常用算法全文共20页，当前为第10页。递归定义

1n=0n！=n(n-1)!n>0阶乘函数intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}程序设计常用算法全文共20页，当前为第11页。Fibonacci数列一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，已知事先给出一对兔子，那么一年以后可以繁殖多少对兔子？1个月，小兔子没有繁殖能力，所以还是1对;2个月，生下一对小兔共有2对;3个月，老兔子又生下1对，因为小兔子还没有繁殖能力，所以一共是3对;依次类推可以列出下表：月数：1、2、3、4、5、6、7、8、9、10、11、12兔子：1、2、3、5、8、13、21、34、55、89、144、

程序设计常用算法全文共20页，当前为第12页。使用递归的条件1.递归需要有边界条件、递归前进段和递归返回段当边界条件不满足时，递归前进当边界条件满足时，递归返回2.考虑使用递归算法编写程序时，应满足两点：该问题能够被递归形式描述存在递归结束的边界条件

递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。

程序设计常用算法全文共20页，当前为第13页。3、迭代法迭代法也称辗转法一种不断用变量的旧值递推新值的过程。与迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。

迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。程序设计常用算法全文共20页，当前为第14页。迭代应用例

一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第12个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为u1，第2个月时兔子的只数为u2，第3个月时兔子的只数为u3，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有

u1＝1，u2＝u1＋u1×1＝2，u3＝u2＋u2×1＝4，……程序设计常用算法全文共20页，当前为第15页。迭代应用u1＝1，u2＝u1＋u1×1＝2，u3＝u2＋u2×1＝4，……根据这个规律，可以归纳出下面的递推公式：

un

＝u(n－1)×2(n≥2)

对应un和u(n－1)，定义两个迭代变量y和x，可将上面的递推公式转换成如下迭代关系：

y=x*2

x=y让计算机对这个迭代关系重复执行11次，就可以算出第12个月时的兔子数。参考程序如下：

x=1

for（i=2；i<=12;i++){

y=x*2

x=y}

printx

end

程序设计常用算法全文共20页，当前为第16页。迭代实例阿米巴用简单分裂的方式繁殖，它每分裂一次要用3分钟。将若干个阿米巴放在一个盛满营养参液的容器内，45分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴220,220个。试问，开始的时候往容器内放了多少个阿米巴？请编程序算出。程序设计常用算法全文共20页，当前为第17页。4、递推法递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。

程序设计常用算法全文共20页，当前为第18页。思考：1、在西方，星期五和数字13都代表着坏运气，两个不幸的个体最后结合成超级不幸的一天。所以，不管哪个月的十三日又恰逢星期五就叫“黑色星期五”。要求：输入年份，输出是：判断该年是否包含黑色星期五，如包含，给出具体日期程序设计常用算法全文共20页，当前为第19页。2、小明去银行存钱，拿了一堆硬币。已知1角的硬币厚度为1.8mm，5角的硬币厚1.5mm，1元的硬币为2.0mm。小