今天完成昨天的算法，银行家算法，这个大家如果知道操作系统这门课程的话应该会明白，昨天一直忙于复习，今天也是，不过下午还是完成了基本调试，调试环境GCC和TC，现在我把代码奉献给大家
银行家算法说明：最早由算法大师 迪杰克斯拉 (Edsger Dijkstra) 提出，银行家算法，顾名思义，它的原理来源于银行系统的存贷款发放管理，即银行（系统）要将一定的款项（资源）贷款（分配）给N个人（进程），当然不需要考虑信用问题< '_'>，在已经发放了一定的金额后，要使得银行的每一次放款（分配资源）都能使得银行（系统）的运行安全（预防死锁）（可以这么理解吧），因此银行家要对现有的资金进行合理分配发放，基本要求要银行必须保留一定的存款不能低于一定的限度（临界资源），同时又不能不放贷款不然会让客户“饿死”（进程饥饿），客户在使用完贷款后要返还（释放）这笔贷款，当然是没有利息的，然后银行要再分配给客户，直到满足客户的多有贷款请求
Read more…
今天讲点简单的算法，最简单的背包0算法，使用了递归的方法，相信看完代码的朋友会发现这段代码很熟悉，不过CG提供这些代码的目的只是让全部背包算法的完整提供地给大家，代码很简单，相信高手一看就懂，这里的背包算法只是考虑了物品的重量，没有考虑物品的价值，是初学递归算法的朋友必看的代码，高手的话全当复习一下吧。
因为CG最近要考试了，一口气要考6门，所以博客更新没有这么快了，请大家见谅不过我还是会保持每天提供至少一篇的速度写博文，希望大家能支持，谢谢
预告下明天的算法博文，《银行家算法》，今天复习了下操作系统，晚上重新安装了系统，浪费了两个小时，代码明天调试后奉上，希望大家继续关注。
Read more…
今天再讲点跟N皇后有关的问题，骑士遍历问题，或者象棋中马的遍历问题，当然这里的马是国际象棋了，两者有着很多相似点，同时又有很多不同点，主要还是限制路径的区别，N皇后主要是自由放置只要满足条件就好，马的遍历则跟上下遍历的路径有关了，主要运用了图算法之深度广度遍历，以及图的建立等算法。
要求：实现棋盘上任意位置的一个棋子马，使它不重复的走过棋盘上的每一个棋盘格
分析：首先知道马在棋盘是怎么走的，根据国际象棋规则，马在一个起始位置共有8个可用的行动位置，当然边界方面需要另外考虑，我们的马的行走必须考虑这8种类可能性，排除不能使用的位置，走可用的位置，当8个位置不可以使用的时，需要考虑返回上一步，这点有点像图的广度优先遍历相同，当马走完所有位置，同时没有可用的位置用于行走的时候遍历结束。
Read more…
今天继续背包问题相关解法，主要内容：动态规划
想到这个解法是想到了前几天的一道软考软件设计师考试的下午算法考题，我是参加者，内容大概如下：通常每种食物往往有不同的营养价值，顾客往往需要一种算法实现用最少的花费获得最高的营养价值，（食物不重复），现在要求在花费N元钱获得最大营养价值
分析：相信求解的原理不用说了，背包问题，软考的题录使用的是动规算法，跟今天的主题相关，那我们看下面的代码吧。
本题动规解法的原理：由于客户选择不同的食物会产生不同的营养结果，因此我们需要动态绑定两者之间的价格和营养价值总和和关系，建立一个关联数组，这样的话每一种价格花费会产生不同结果，我们再进行大小筛选，就是在已有的选择的前提下再增加一定价格的食物，如果相加之后超出则排除，或者相加它的营养价值之后小于相加一种更价格便宜的食物的话也排除，这样可以求出每一个价位的食品的最大营养价值，然后根据要求输出某一价位的结果
Read more…
今天整理自己的文档，发现自己当年做一些的C语言程序，现在与大家分享
程序一、黑白棋程序，当年最早在mac上出现的小游戏，也就是俗称的苹果棋游戏，小时候没玩过？自己调试玩玩看看
调试环境 ：GCC ,TC
需要BGI驱动支持，调过c语言的应该知道吧
代码如下(只提供AI部分)：完整地址www.lidaren.com/code/WBchess.c.txt
Read more…
求输入的N（1~20）个整数（1~200000）的最大公约数算法
盐城师范学院软件协会 ACM/ICPC 试题
如需转载请保留相关作者注释，标明出处
说明：
算法使用了位运算的优化，减少MOD运算和除法运算的开销
实现一次遍历求出结果
算法时间复杂度O（n），最差情况O（Log2^C *N）C=所有数中最大数
Read more…
Recent Comments