今天讲背包问题的最后一种解法，递归解法，这种解法也是目前算法教材上讲的基本解法之一，如果你有一本关于这类算法的书籍，一般都可以找到你想要的算法，背包问题具体是什么，大家可以参考我的以前的文章，可以直接到下面的相关链接里面找到，我在最近发布关于背包问题的基本解法，动态规划解法，回溯解法，大家可以直接参照我的页面链接，如果具体还有问题不懂的话，也非常欢迎大家留言
好的，讲一讲递归算法，我提供的算法是使用了有效重量，最大可用价值作为递归参数逐个测试物件的重量和价值，直到找到最佳的侯返回，请注意，这里我设置的条件是只要满足背包可以放就可以，并不是贪心算法，请注意区别。
今天再讲点跟N皇后有关的问题，骑士遍历问题，或者象棋中马的遍历问题，当然这里的马是国际象棋了，两者有着很多相似点，同时又有很多不同点，主要还是限制路径的区别，N皇后主要是自由放置只要满足条件就好，马的遍历则跟上下遍历的路径有关了，主要运用了图算法之深度广度遍历，以及图的建立等算法。
要求：实现棋盘上任意位置的一个棋子马，使它不重复的走过棋盘上的每一个棋盘格
分析：首先知道马在棋盘是怎么走的，根据国际象棋规则，马在一个起始位置共有8个可用的行动位置，当然边界方面需要另外考虑，我们的马的行走必须考虑这8种类可能性，排除不能使用的位置，走可用的位置，当8个位置不可以使用的时，需要考虑返回上一步，这点有点像图的广度优先遍历相同，当马走完所有位置，同时没有可用的位置用于行走的时候遍历结束。
今天讲点比较高级的算法，目的也很简单，求质数，但是应用一种新的算法Miller-Rabin算法，这是一种利用了概率和费马小定理的算法设计，有点玄乎吧，其实本人也是刚接触这种算法，这是一种纯数学的解法，如果各位不懂，当学习一下数学也好啊好，我们往下讲
首先了解基本的数学知识，费马小定理：
若n是素数，则对所有1≤a≤n-1的整数a，有a^(n-1)mod n=1;
作者Fermat 很牛的数学家，在他在世的时候好像还没有计算机，不过今天我们要用这个定理来设计算法
分析这个定理可以知道，如果一个数是质数，那么它必定满足任意一个整数属于(1，n-1)范围有a^(n-1)mod n=1，不懂？我们取逆否命题试试看，就是只要存在在(1，n-1)范围中的整数a 使得a^(n-1)mod n=1不成立，那么这个数就不是素数，相信明白了吧，我们要确定一个数是否是素数，只要随机生成一系列的数a，如果这些数a使N满足费马小定理的话那么就可以认定它是素数了，当然有个前提，就是这个推导只能在计算机领域内使用就跟我上次讲的用哥德巴赫猜想优化一道算法题目一样，在计算机可以运算的数的范围内可用，请不要在其他科学领域类使用
圣诞前夜讲点比较具有圣诞感觉的算法，背包问题算法，这里我写了经典算法和贪心算法两种解决方法，因为时间不多，所以给出的数组是已经排序的，因为贪心算法可能要用得到，经典算法因为是一个一个比较，因此排序也就没有那么重要了，可能两种算法的最终运行效果一样的，朋友们调试的时候记得修改我给出的测试数组，今天实在太忙了，贪心使用的排序算法没有写，留着以后给大家讲排序算法的时候使用吧，圣诞快乐，诸位朋友们。
背包问题：就是现在有一个容量为PSIZE的背包，同时又有N件item，现在要求将这些item放入这个背包里面去，要求尽量放一定要求的item（比如按照大小的顺序），又要求放最多的item或者放的item权值之和要最大
今天继续昨天的话题，字符串匹配算法之BM算法，BM可以说是继KMP算法之后更加优秀的字符串匹配算了，BM 是大师Boyer-Moore的算法杰作， 所以称BM算法，相比KMP算法效率提高了不少，在空间上BM算法需要一个跟匹配字符集相同的辅助空间，已存放不同的匹配字符，比KMP要浪费不少，但是这也是BM的特色，可以在不同的字符集使用，两个字符集的话那就放一个字符集同大小的辅助空间就好，最复杂字符就很好了，目前大部分的高级语言比如C#都使用了BM及其改进算法(AC-BM算法)，相比KMP匹配两个中文字符出现的半角结果而言，我还是偏好BM ，虽然浪费空间，但是，实现接近低于线性的消耗，少了一个n以上的的匹配时间，这点也是客观的
[算法]数据结构中关于货郎担路径问题的常用解法，边界路径问题相信诸位学习过高级算法数据结构的朋友肯定是知道“货郎担问题”是很经典的图算法问题货郎担问题可以总结出4种不同的解法，主要有回溯、贪心、动态规划以下提供的算法是使用的动态规划方法，结合边界路径问题提出的算法C语言实现，调试TC平台，动规算法
代码：
Read more…
相信知道除法的作用的人都知道除法怎么来计算吧，不过计算机计算除法的方法可能优点浪费资源了以下是使用位计算转换除法的过程，相信知道游戏编程的朋友对这个应该不陌生吧
原理：假如要实现A/B,B如果是2的整数次方的话，那就不用说的，直接位移了运算如果是0，这个就不要问我了A/0等于多少我也不知道。
代码：
Read more…
Recent Comments