文档介绍：:..,又称暴力算法,即列举问题解空间所有可能情况,并逐个测试,从而找出符合问题条件的解。这份通常是一种费时算法,人工手动求解W难,但计算机的出现使得穷举法有了用武之地。例如:密码破译通常用的足穷举法,即将密码进行逐个推算直到找到真正的密码为止。理论上讲,穷举法可以破解任何一种密码,但对于一个长度为n位的密码,其可能的密码有2An种。可见,当n较大吋穷举法将成为一个NP难度问题。典型例题【百钱买百鸡问题】公元5世纪末,中国古代数学家张丘建在他的《算经》中提到了著名的“百钱买百鸡”问题:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各儿何?分析:设鸡翁、鸡母、鸡雏的个数各为x、y、z,百钱买百鸡问题可以用如下方程式表示:5x+3y+z/3=100x+y+z=1001<=x<20,1<=y<33,3<=z<100,zmod3=0对于百钱买白鸡问题,很容易用穷举法对x、y、z的取值,判断方程(1)、(2)及zmod3=0是否成立,若成立,则是问题的-个解。百钱买白鸡问题求解篇法://百钱买白鸡问题穷举算法//设鸡翁、鸡母、鸡雏的个数分别为x、y、zfor(x=l;x<20;x++)for(y=l;y<33;y++)for(z=3;z<100;z++)if(x+y+z==100)and(5x+3y+z/3==100)and(zmod3=0)writeln(x,y,z)上述算法是一个三熏循环,最内层的条件判断盂要执行19*32*97次,即58976。在条件判断中,利用了整数的求模运算,如果将鸡雏的个数设为3z,可以避免该项判断,且可减少内熏循环次数。即:for(z=l;z<34;z++)if(x+y+3z==100)and(5x+3y+z=100)writeln(x,y,3z)【0-1背包fuj题1】给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,背包的容量为Wm。应如何选择装入背包的物品,使得装入背包的物品总价值最大?分析:所谓0-1背包问题,是指在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包。另外,不能将物品i装入背包多次,也不能只装入部分的物品i。0-1背包问题是一种组合优化的NP完全问题,最容易想到方法的就是穷举法。0-1背包问题求解的穷举算法。//设数组w[0-n-l]存储n件物品的重量,数组c[0-n-l]存储//n件物品的价ffi,数组b[0-n-l]为秘识数组,若物品i未选//择,则b[i-l]=O,否则b[i-l]=lcmax=Ofor(i=l;i<=2An-l;i-H-){b[0』-l]=将i转化为n位的二进制字符串tenipw=求和b[j]*w[j]tempc=求和b[j]*c[j]If(tempw<wmax&&tempc>cmax){tempb=b[O..n-l];cmax=tempc;>}输出最佳方案tempb[O..n-l],。递推关系可以抽象为一个简单的数学模型,即给定一个数的序列aeA,…,an若存在整数n。,使当吋,可以用等号(或大于号,小于号)将an与其前面的某些项a<0<i<n)联系起來,这样的式子称为递推公式,又称递推关系。递推算法的基本思想是把一个复杂庞大的计算过程转化为简单过程的多次重复。该类算法利用了计算机速度快和自动化的特点。递推算法是一种简笮的算法,通过已知条件利用特定的递推关系可以得到中间推论,直至得到问题的最终结果。递推算法分为顺推法和逆推法两种。【斐波那契数列算法1】斐波那契数列,又称力黄金分割数列。在数学上,斐波那契数列可以用递推方法定义,其递推公式为Fi=0,F2=l,Fn=F(n-i)+F(n-2)(n>=3,neN*)o写一算法求斐波那契数列第10项的值。分析:从斐波那契数列的定义可知,数列的第一项为一,第二项也为一,递推关系是当前项等于前二项之和◊因此,通过顺推可以得到f(3)=f(l)+f(2)=2,f(4)=f(2)+f(3)=3,f(5)=f(3)+f(4)=5,以此类推,可以得到f(10)的值。求斐波那契数列的顺推算法://求斐波那契数列第十项的值并输出ni]=ifT2]=2while(n<=10){f[n]=f[n-l]4f[n-2]n=n+lwrite(f[10]),递推是从已知条件出发,一步步递推出未知项,直到问题的解。递归也是递推的一种,只不过它是对待解问题的递推,直到把-个复杂的问题递推为简单的易解W题,然后再一步步返回,从而得到原M题的解。【斐波那契数列算法2】利用递归思想写出求斐波那