以下是引用laoyang103在2011-5-8 20:20:32的发言:
1.递推法//斐波拉切数列
f(n) = f(n-1)+f(n-2)
f(1) =
f(2) = 1
结果为 1 1 2 3 4 5 8 13..............此法也称迭代
2.递归法//最简单的 求阶乘
其实递归就是划分子问题 是问题的规模减一或者更多
f(n) = n*f(n-1) 由于本人愚钝
至今
//没有弄明白迭代和递归怎么转化 什么关系
只知道迭代式从第一个推最后一个 也就是结果
而递归式先从要求的结果往前推
//一直到一个边界比如说 (0的阶乘等于1或者什么的) 然后再一层一层的往回返
//比较复杂一点的递归 比如汉诺塔 想移动n层就要先移动上面的n-1层 然后在移动第n层那个 然后在移动那n-1层到第n曾上
//han(n-1,a,b,c);//先移动上面的n-1 mov(a,b);//移动第n个 han(n-1,c,a,b);//再把那n-1个压到第n个上
//关于递归 还有很多 本人愚钝
再说就丢人了
3.穷举搜索法//这个简单
比如说求1--100之间的素数
就是把每一个数都判断一下就可以了
穷举简单好理解 但是属于暴力算法
4.贪婪法//其实把也是把问题划分成多个问题
然后每个问题都最优
其实就是局部最优
5.分治法//不太懂
不敢多说
6.动态规划法//最优子结构
比如说背包问题 f(i,v) = max{f(i-1,v) , f(i-1,v-c)+w} 此问题俗称0 1背包
//f(i,v)表示把前i个物品放入容积为v的背包所获得的最大价值
他就等于 1.如果不放入第i个物品
//那就是f(i-1,v) 2.如果放入第i个物体 既然要放入第i个了那背包的容积最多就剩下v-c
c为
//第i个物品的体积
那么就是把剩下的i-1个物品放入v-c的最大价值f(i-1,v-c)加上w(第i个物品的价值)
//然后再娶个max 旧的到了最优子结构 这样一直推就可以得到结果
7.迭代法//和递推差不多
还是求阶乘
f(n) = n*f(n-1)
3!=(3*2!) 2!=(2*(1!))
1! = (1*0!)
//编号为 1 2 3式
把3带入2 再把2带入1
你就会看到迭代
8.分支界限法//学习中
老杨愚钝
花了半个小时写了这些东西
我所知道的东西 已经倾囊而赠了
希望对大家有帮助
非常感谢了
只要是自己的理解
就非常棒