Java & PHP RSA 互通密钥、签名、验签、加密、解密

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。阅读全文→

标签: php java rsa

smarteng 发布于 2021-09-10 09:29

单向链表翻转

struct linka {
int data;
linka next;
};
void reverse(linka
& head) {
if(head ==NULL) return;
linka pre, cur, *ne;
pre=head;
cur=head->next;
while(cur) {
ne = cur->next; //将下一个节点保存
cur->next = pre; //将当前节点的下一个节点置为当前节点
pre = cur; //将当前节点保存为前一节点
cur = ne; //将当前节点置为下一节点
}
head->next = NULL;
head = pre;
}

linka reverse(linka p,linka& head) {
if(p == NULL || p->next == NULL) { //判断跳出条件
head=p; return p;//将链表切断,否则会形成回环
} else {
linka
tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}阅读全文→

标签: 算法

smarteng 发布于 2013-03-10 21:41

行程长度编码(游程编码)

游程编码RLErun-length encoding),又译行程长度编码,又称变动长度编码法run coding),在控制论中对于二值图像而言是一种编码方法,对连续的黑、白像素数(游程)以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法,其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之,其缺点是对于不重复的资料反而加大容量。

例如有一张图片,以W表示白色,B表示黑...

阅读全文→

smarteng 发布于 2013-03-09 14:59

标签(Tag)的数据库设计

最近,在del.icio.us mailinglist(译者按:应该是美味书签的讨论版块。以下del.icio.us翻译为美味书签)上面发了一个问题:“有人知道美味书签的数据库设计吗?”。之后我得到了一些回复,所以我想把这部分东西的知识分享给大家。

疑问

当你要为一个书签添加你认为需要的一个或多个标签时(或日志或其他)其数据库是如何设计的?然后,执行查询时取消这些书签中标签的合集(union)或交集(...

阅读全文→

smarteng 发布于 2013-02-28 13:16

推荐算法

如今,到网上购物的人已经习惯了收到系统为他们做出的个性化推荐。Netflix 会推荐你可能会喜欢看的视频。TiVo 会自动把节目录下来,如果你感兴趣就可以看。Pandora 会通过预测我们想要听什么歌曲从而生成个性化的音乐流。

所有这些推荐结果都来自于各式各样的推荐系统。它们依靠计算机算法运行,根据顾客的浏览、搜索、下单和喜好,为顾客选择他们可能会喜欢、有可能会购买的商品,从而为消费者服务。推荐系统...

阅读全文→

smarteng 发布于 2012-11-13 18:33

从10亿查询词找出出现频率最高的10个

1. 问题描述
在大规模数据处理中,常遇到的一类问题是,在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常称为“top K”问题,如:在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载率最高的前10首歌等等。
2. 当前解决方案
针对top k类问题,通常比较好的方案是【分治+trie树/hash+小顶堆】,即先将数据集按照hash方法分解成多个小数据集...
阅读全文→

smarteng 发布于 2012-05-24 19:42

缓存中的算法-RAND算法,FIFO算法,LFU算法,LRU算法,OPT算法

在段式虚拟存储器中,虚存空间中能容纳的程序段数要比主存空间中能存放的相同长度的程序段数多得多。因此,必然会出现当主存中所有页面都已经被占用,或者所有主存空间都已经被占用,而又要从磁盘存储器中调入新页的情况。这时,必须从主存储器中淘汰掉一个不常用的页面,以便腾出主存空间来存放新调入的页面。下面介绍几种常用的替换算法:RAND算法,FIFO算法,LFU算法,LRU算法,OPT算法。

阅读全文→

smarteng 发布于 2011-02-20 20:55

23种设计模式有趣诠释

创建型模式

1、FACTORY—追MM少不了请吃饭了,麦当劳的鸡翅和肯德基的鸡翅都是MM爱吃的东西,虽然口味有所不同,但不管你带MM去麦当劳或肯德基,只管向服务员说“来四个鸡翅”就行了。麦当劳和肯德基就是生产鸡翅的Factory

工厂模式:客户类和工厂类分开。消费者任何时候需要某种产品,只需向工厂请求即可。消费者无须修改就可以接纳新产品。缺点是当产品修改时,工厂类也要做相应的修改。如:如何创建及如何向客户端提供。

2、BUILDER—MM最爱听的就是“我爱你”这句话了,见到不同地方的MM,要能够用她们的方言跟她说这句话哦,我有一个多种语言翻译机,上面每种语言都有一个按键,见到MM我只要按对应的键,它就能够用相应的语言说出“我爱你”这句话了,国外的MM也可以轻松搞掂,这就是我的“我爱你”builder。(这一定比美军在伊拉克用的翻译机好卖) [break]

建造模式:将产品的内部表象和产品的生成过程分割开来,从而使一个建造过程生成具有不同的内部表象的产品对象。建造模式使得产品内部表象可以独立的变化,客户不必知道产品内部组成的细节。建造模式可以强制实行一种分步骤进行的建造过程。

3、FACTORY METHOD—请MM去麦当劳吃汉堡,不同的MM有不同的口味,要每个都记住是一件烦人的事情,我一般采用Factory Method模式,带着MM到服务员那儿,说“要一个汉堡”,具体要什么样的汉堡呢,让MM直接跟服务员说就行了。

工厂方法模式:核心工厂类不再负责所有产品的创建,而是将具体创建的工作交给子类去做,成为一个抽象工厂角色,仅负责给出具体工厂类必须实现的接口,而不接触哪一个产品类应当被实例化这种细节。

4、PROTOTYPE—跟MM用QQ聊天,一定要说些深情的话语了,我搜集了好多肉麻的情话,需要时只要copy出来放到QQ里面就行了,这就是我的情话prototype了。(100块钱一份,你要不要)

原始模型模式:通过给出一个原型对象来指明所要创建的对象的类型,然后用复制这个原型对象的方法创建出更多同类型的对象。原始模型模式允许动态的增加或减少产品类,产品类不需要非得有任何事先确定的等级结构,原始模型模式适用于任何的等级结构。缺点是每一个类都必须配备一个克隆方法。

5、SINGLETON—俺有6个漂亮的老婆,她们的老公都是我,我就是我们家里的老公Sigleton,她们只要说道“老公”,都是指的同一个人,那就是我(刚才做了个梦啦,哪有这么好的事)

单例模式:单例模式确保某一个类只有一个实例,而且自行实例化并向整个系统提供这个实例单例模式。单例模式只应在有真正的“单一实例”的需求时才可使用。

结构型模式

6、ADAPTER—在朋友聚会上碰到了一个美女Sarah,从香港来的,可我不会说粤语,她不会说普通话,只好求助于我的朋友kent了,他作为我和Sarah之间的Adapter,让我和Sarah可以相互交谈了(也不知道他会不会耍我)

适配器(变压器)模式:把一个类的接口变换成客户端所期待的另一种接口,从而使原本因接口原因不匹配而无法一起工作的两个类能够一起工作。适配类可以根据参数返还一个合适的实例给客户端。

7、BRIDGE—早上碰到MM,要说早上好,晚上碰到MM,要说晚上好;碰到MM穿了件新衣服,要说你的衣服好漂亮哦,碰到MM新做的发型,要说你的头发好漂亮哦。不要问我“早上碰到MM新做了个发型怎么说”这种问题,自己用BRIDGE组合一下不就行了

桥梁模式:将抽象化与实现化脱耦,使得二者可以独立的变化,也就是说将他们之间的强关联变成弱关联,也就是指在一个软件系统的抽象化和实现化之间使用组合/聚合关系而不是继承关系,从而使两者可以独立的变化。

8、COMPOSITE—Mary今天过生日。“我过生日,你要送我一件礼物。”“嗯,好吧,去商店,你自己挑。”“这件T恤挺漂亮,买,这条裙子好看,买,这个包也不错,买。”“喂,买了三件了呀,我只答应送一件礼物的哦。”“什么呀,T恤加裙子加包包,正好配成一套呀,小姐,麻烦你包起来。”“……”,MM都会用Composite模式了,你会了没有?

合成模式:合成模式将对象组织到树结构中,可以用来描述整体与部分的关系。合成模式就是一个处理对象的树结构的模式。合成模式把部分与整体的关系用树结构表示出来。合成模式使得客户端把一个个单独的成分对象和由他们复合而成的合成对象同等看待。

9、DECORATOR—Mary过完轮到Sarly过生日,还是不要叫她自己挑了,不然这个月伙食费肯定玩完,拿出我去年在华山顶上照的照片,在背面写上“最好的的礼物,就是爱你的Fita”,再到街上礼品店买了个像框(卖礼品的MM也很漂亮哦),再找隔壁搞美术设计的Mike设计了一个漂亮的盒子装起来……,我们都是Decorator,最终都在修饰我这个人呀,怎么样,看懂了吗?

装饰模式:装饰模式以对客户端透明的方式扩展对象的功能,是继承关系的一个替代方案,提供比继承更多的灵活性。动态给一个对象增加功能,这些功能可以再动态的撤消。增加由一些基本功能的排列组合而产生的非常大量的功能。

10、FACADE—我有一个专业的Nikon相机,我就喜欢自己手动调光圈、快门,这样照出来的照片才专业,但MM可不懂这些,教了半天也不会。幸好相机有Facade设计模式,把相机调整到自动档,只要对准目标按快门就行了,一切由相机自动调整,这样MM也可以用这个相机给我拍张照片了。

门面模式:外部与一个子系统的通信必须通过一个统一的门面对象进行。门面模式提供一个高层次的接口,使得子系统更易于使用。每一个子系统只有一个门面类,而且此门面类只有一个实例,也就是说它是一个单例模式。但整个系统可以有多个门面类。

11、FLYWEIGHT—每天跟MM发短信,手指都累死了,最近买了个新手机,可以把一些常用的句子存在手机里,要用的时候,直接拿出来,在前面加上MM的名字就可以发送了,再不用一个字一个字敲了。共享的句子就是Flyweight,MM的名字就是提取出来的外部特征,根据上下文情况使用。

享元模式:FLYWEIGHT在拳击比赛中指最轻量级。享元模式以共享的方式高效的支持大量的细粒度对象。享元模式能做到共享的关键是区分内蕴状态和外蕴状态。内蕴状态存储在享元内部,不会随环境的改变而有所不同。外蕴状态是随环境的改变而改变的。外蕴状态不能影响内蕴状态,它们是相互独立的。将可以共享的状态和不可以共享的状态从常规类中区分开来,将不可以共享的状态从类里剔除出去。客户端不可以直接创建被共享的对象,而应当使用一个工厂对象负责创建被共享的对象。享元模式大幅度的降低内存中对象的数量。

12、PROXY—跟MM在网上聊天,一开头总是“hi,你好”,“你从哪儿来呀?”“你多大了?”“身高多少呀?”这些话,真烦人,写个程序做为我的Proxy吧,凡是接收到这些话都设置好了自动的回答,接收到其他的话时再通知我回答,怎么样,酷吧。

代理模式:代理模式给某一个对象提供一个代理对象,并由代理对象控制对源对象的引用。代理就是一个人或一个机构代表另一个人或者一个机构采取行动。某些情况下,客户不想或者不能够直接引用一个对象,代理对象可以在客户和目标对象直接起到中介的作用。客户端分辨不出代理主题对象与真实主题对象。代理模式可以并不知道真正的被代理对象,而仅仅持有一个被代理对象的接口,这时候代理对象不能够创建被代理对象,被代理对象必须有系统的其他角色代为创建并传入。

行为模式

13、CHAIN OF RESPONSIBLEITY—晚上去上英语课,为了好开溜坐到了最后一排,哇,前面坐了好几个漂亮的MM哎,找张纸条,写上“Hi,可以做我的女朋友吗?如果不愿意请向前传”,纸条就一个接一个的传上去了,糟糕,传到第一排的MM把纸条传给老师了,听说是个老处女呀,快跑!

责任链模式:在责任链模式中,很多对象由每一个对象对其下家的引用而接

起来形成一条链。请求在这个链上传递,直到链上的某一个对象决定处理此请求。客户并不知道链上的哪一个对象最终处理这个请求,系统可以在不影响客户端的情况下动态的重新组织链和分配责任。处理者有两个选择:承担责任或者把责任推给下家。一个请求可以最终不被任何接收端对象所接受。

14、COMMAND—俺有一个MM家里管得特别严,没法见面,只好借助于她弟弟在我们俩之间传送信息,她对我有什么指示,就写一张纸条让她弟弟带给我。这不,她弟弟又传送过来一个COMMAND,为了感谢他,我请他吃了碗杂酱面,哪知道他说:“我同时给我姐姐三个男朋友送COMMAND,就数你最小气,才请我吃面。”,:-(

命令模式:命令模式把一个请求或者操作封装到一个对象中。命令模式把发出命令的责任和执行命令的责任分割开,委派给不同的对象。命令模式允许请求的一方和发送的一方独立开来,使得请求的一方不必知道接收请求的一方的接口,更不必知道请求是怎么被接收,以及操作是否执行,何时被执行以及是怎么被执行的。系统支持命令的撤消。

15、INTERPRETER—俺有一个《泡MM真经》,上面有各种泡MM的攻略,比如说去吃西餐的步骤、去看电影的方法等等,跟MM约会时,只要做一个Interpreter,照着上面的脚本执行就可以了。

解释器模式:给定一个语言后,解释器模式可以定义出其文法的一种表示,并同时提供一个解释器。客户端可以使用这个解释器来解释这个语言中的句子。解释器模式将描述怎样在有了一个简单的文法后,使用模式设计解释这些语句。在解释器模式里面提到的语言是指任何解释器对象能够解释的任何组合。在解释器模式中需要定义一个代表文法的命令类的等级结构,也就是一系列的组合规则。每一个命令对象都有一个解释方法,代表对命令对象的解释。命令对象的等级结构中的对象的任何排列组合都是一个语言。

 

16、ITERATOR—我爱上了Mary,不顾一切的向她求婚。

Mary:“想要我跟你结婚,得答应我的条件”

我:“什么条件我都答应,你说吧”

Mary:“我看上了那个一克拉的钻石”

我:“我买,我买,还有吗?”

Mary:“我看上了湖边的那栋别墅”

我:“我买,我买,还有吗?”

Mary:“你的小弟弟必须要有50cm长”

我脑袋嗡的一声,坐在椅子上,一咬牙:“我剪,我剪,还有吗?”

……

迭代子模式:迭代子模式可以顺序访问一个聚集中的元素而不必暴露聚集的内部表象。多个对象聚在一起形成的总体称之为聚集,聚集对象是能够包容一组对象的容器对象。迭代子模式将迭代逻辑封装到一个独立的子对象中,从而与聚集本身隔开。迭代子模式简化了聚集的界面。每一个聚集对象都可以有一个或一个以上的迭代子对象,每一个迭代子的迭代状态可以是彼此独立的。迭代算法可以独立于聚集角色变化。

17、MEDIATOR—四个MM打麻将,相互之间谁应该给谁多少钱算不清楚了,幸亏当时我在旁边,按照各自的筹码数算钱,赚了钱的从我这里拿,赔了钱的也付给我,一切就OK啦,俺得到了四个MM的电话。

调停者模式:调停者模式包装了一系列对象相互作用的方式,使得这些对象不必相互明显作用。从而使他们可以松散偶合。当某些对象之间的作用发生改变时,不会立即影响其他的一些对象之间的作用。保证这些作用可以彼此独立的变化。调停者模式将多对多的相互作用转化为一对多的相互作用。调停者模式将对象的行为和协作抽象化,把对象在小尺度的行为上与其他对象的相互作用分开处理。

18、MEMENTO—同时跟几个MM聊天时,一定要记清楚刚才跟MM说了些什么话,不然MM发现了会不高兴的哦,幸亏我有个备忘录,刚才与哪个MM说了什么话我都拷贝一份放到备忘录里面保存,这样可以随时察看以前的记录啦。

备忘录模式:备忘录对象是一个用来存储另外一个对象内部状态的快照的对象。备忘录模式的用意是在不破坏封装的条件下,将一个对象的状态捉住,并外部化,存储起来,从而可以在将来合适的时候把这个对象还原到存储起来的状态。

19、OBSERVER—想知道咱们公司最新MM情报吗?加入公司的MM情报邮件组就行了,tom负责搜集情报,他发现的新情报不用一个一个通知我们,直接发布给邮件组,我们作为订阅者(观察者)就可以及时收到情报啦

观察者模式:观察者模式定义了一种一队多的依赖关系,让多个观察者对象同时监听某一个主题对象。这个主题对象在状态上发生变化时,会通知所有观察者对象,使他们能够自动更新自己。

20、STATE—跟MM交往时,一定要注意她的状态哦,在不同的状态时她的行为会有不同,比如你约她今天晚上去看电影,对你没兴趣的MM就会说“有事情啦”,对你不讨厌但还没喜欢上的MM就会说“好啊,不过可以带上我同事么?”,已经喜欢上你的MM就会说“几点钟?看完电影再去泡吧怎么样?”,当然你看电影过程中表现良好的话,也可以把MM的状态从不讨厌不喜欢变成喜欢哦。

状态模式:状态模式允许一个对象在其内部状态改变的时候改变行为。这个对象看上去象是改变了它的类一样。状态模式把所研究的对象的行为包装在不同的状态对象里,每一个状态对象都属于一个抽象状态类的一个子类。状态模式的意图是让一个对象在其内部状态改变的时候,其行为也随之改变。状态模式需要对每一个系统可能取得的状态创立一个状态类的子类。当系统的状态变化时,系统便改变所选的子类。

21、STRATEGY—跟不同类型的MM约会,要用不同的策略,有的请电影比较好,有的则去吃小吃效果不错,有的去海边浪漫最合适,单目的都是为了得到MM的芳心,我的追MM锦囊中有好多Strategy哦。

策略模式:策略模式针对一组算法,将每一个算法封装到具有共同接口的独立的类中,从而使得它们可以相互替换。策略模式使得算法可以在不影响到客户端的情况下发生变化。策略模式把行为和环境分开。环境类负责维持和查询行为类,各种算法在具体的策略类中提供。由于算法和环境独立开来,算法的增减,修改都不会影响到环境和客户端。

22、TEMPLATE METHOD——看过《如何说服女生上床》这部经典文章吗?女生从认识到上床的不变的步骤分为巧遇、打破僵局、展开追求、接吻、前戏、动手、爱抚、进去八大步骤(Template method),但每个步骤针对不同的情况,都有不一样的做法,这就要看你随机应变啦(具体实现);

模板方法模式:模板方法模式准备一个抽象类,将部分逻辑以具体方法以及具体构造子的形式实现,然后声明一些抽象方法来迫使子类实现剩余的逻辑。不同的子类可以以不同的方式实现这些抽象方法,从而对剩余的逻辑有不同的实现。先制定一个顶级逻辑框架,而将逻辑的细节留给具体的子类去实现。

23、VISITOR—情人节到了,要给每个MM送一束鲜花和一张卡片,可是每个MM送的花都要针对她个人的特点,每张卡片也要根据个人的特点来挑,我一个人哪搞得清楚,还是找花店老板和礼品店老板做一下Visitor,让花店老板根据MM的特点选一束花,让礼品店老板也根据每个人特点选一张卡,这样就轻松多了;

访问者模式:访问者模式的目的是封装一些施加于某种数据结构元素之上的操作。一旦这些操作需要修改的话,接受这个操作的数据结构可以保持不变。访问者模式适用于数据结构相对未定的系统,它把数据结构和作用于结构上的操作之间的耦合解脱开,使得操作集合可以相对自由的演化。访问者模式使得增加新的操作变的很容易,就是增加一个新的访问者类。访问者模式将有关的行为集中到一个访问者对象中,而不是分散到一个个的节点类中。当使用访问者模式时,要将尽可能多的对象浏览逻辑放在访问者类中,而不是放到它的子类中。访问者模式可以跨过几个类的等级结构访问属于不同的等级结构的成员类。
 


smarteng 发布于 2009-10-18 15:53

约瑟夫环 php实现

一群猴子排成一圈,按1,2,...,n依次编号。

然后从第1只开始数,数到第m只,把它踢出圈,

从它后面再开始数, 再数到第m只,在把它踢出去...,

如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王。

要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。


目录
• 方法一 按逻辑依次去除
• 方法二 递归的算法
• 方法三:线性表应用
 方法一 按逻辑依次去除编辑本段回目录
<?php
/*
* filename: kingmonkey.php
* author: luochuan wang
* date: April 2nd, 2009
* descript: an arithmetic to a program
* program: 
   一群猴子排成一圈,按1,2,...,n依次编号。 
   然后从第1只开始数,数到第m只,把它踢出圈,
   从它后面再开始数,  再数到第m只,在把它踢出去...,
   如此不停的进行下去,  直到最后只剩下一只猴子为止,那只猴子就叫做大王。 
   要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。
*/

function getKingMokey($n, $m)
{
        $monkey[0] = 0;

        //将1-n只猴子顺序编号 入数组中[break]
        for($i= 1; $i<= $n; $i++)
        {
               $monkey[$i] = $i;
        }

        $len = count($monkey);

        //循环遍历数组元素(猴子编号)
        for($i= 0; $i< $len; $i= $i)
        {
              $num = 0;

             /*
              * 遍历$monkey数组,计算数组中值不为0的元素个数(剩余猴子的个数)
              * 赋值为$num,并获取值不为0的元素的元素值
             */
             foreach($monkey as $key => $value)
             {
                if($value == 0) continue;
                $num++;
                $values = $value;
             }

             //若只剩一只猴子 则输出该猴子编号(数组元素值) 并退出循环
             if($num == 1)
             {
                    echo $values;
                    exit;
             }

             /*
              * 若剩余猴子数大于1($num > 1)
              * 继续程序
             */

             //将第$i只猴子踢出队伍(相应数组位置元素值设为0)
             $monkey[$i] = 0;

             //打印该猴子位置
             echo $i."";

            /*
             * 获取下一只需要踢出队伍的猴子编号
             * 在$m值范围内遍历猴子 并设置$m的计数器
             * 依次取下一猴子编号
             * 若元素值为0,则该位置的猴子已被踢出队伍
             * 若不为0,继续获取下一猴子编号,且计数器加1
             * 若取得的猴子编号大于数组个数
             * 则从第0只猴子开始遍历(数组指针归零) 步骤同上
             * 直到计数器到达$m值 * 最后获取的$i值即为下一只需要踢出队伍的猴子编号
             */

             //设置计数器
             for($j= 1; $j<= $m; $j++)
             {
                   //猴子编号加一,遍历下一只猴子
                   $i++;

                   //若该猴子未被踢出队伍,获取下一只猴子编号
                   if($monkey[$i] > 0) continue;

                   //若元素值为0,则猴子已被踢出队伍,进而循环取下一只猴子编号
                   if($monkey[$i] == 0)
                   {
                           //取下一只猴子编号
                           for($k= $i; $k< $len; $k++)
                           {
                                   //值为0,编号加1
                                   if($monkey[$k] == 0) $i++;

                                   //否则,编号已取得,退出
                                   if($monkey[$k] > 0) break;
                           }
                    }

                   //若编号大于猴子个数,则从第0只猴子开始遍历(数组指针归零) 步骤同上
                   if($i == $len) $i = 0;

                   //同上步骤,获取下一只猴子编号
                   if($monkey[$i] == 0)
                   {
                          for($k= $i; $k< $len; $k++)
                          {
                                   if($monkey[$k] == 0) $i++;

                                  if($monkey[$k] > 0) break;
                          }
                   }
            }
      }
}

//猴子个数
$n = 10;

//踢出队伍的编号间隔值
$m = 3;

//调用猴王获取函数

getKingMokey($n, $m);

?>


方法二 递归的算法编辑本段回目录$monkeys = array(1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10);  //monkey的编号
$m = 4;  //数到第几只的那只猴子被踢出去
/* 猴王算法*/
/*面向过程的实现 */
function killMonkey($monkeys , $m , $current = 0){
    $number = count($monkeys);
        $num = 1;
        if(count($monkeys) == 1){
            echo $monkeys[0]."成为猴王了";
            return;
        }
        else{
            while($num++ < $m){
                    $current++ ;
                    $current = $current%$number;
                }
                echo $monkeys[$current]."的猴子被踢掉了<br/>";
                array_splice($monkeys , $current , 1);
                killMonkey($monkeys , $m , $current);
        }
}
killMonkey($monkeys , $m);

最后这个算法最牛有网友给了解释:

居伽爱牛 

哦,是这样的,每个猴子出列后,剩下的猴子又组成了另一个子问题。只是他们的编号变化了。第一个出列的猴子肯定是a[1]=m(mod)n(m/n的余数),他除去后剩下的猴子是a[1]+1,a[1]+2,…,n,1,2,…a[1]-2,a[1]-1,对应的新编号是1,2,3…n-1。设此时某个猴子的新编号是i,他原来的编号就是(i+a[1])%n。于是,这便形成了一个递归问题。假如知道了这个子问题(n-1个猴子)的解是x,那么原问题(n个猴子)的解便是:(x+m%n)%n=(x+m)%n。问题的起始条件:如果n=1,那么结果就是1。

方法三:线性表应用编辑本段回目录 /**
* 线性表应用(选首领问题)
*
* @param  $n  总数
* @param  $m  当报数到 m 时,m出列
* @return 最后剩下的数字
*/
function yuesefu($n,$m) { 
    $r=0; 
    for($i=2; $i<=$n; $i++) {
            $r=($r+$m)%$i; 
    }
    return $r+1; 

print_r(yuesefu(3,3));
?>
 


smarteng 发布于 2009-10-12 21:32

哈希算法

哈希算法将任意长度的二进制值映射为固定长度的较小二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生不同的值。

阅读全文→

smarteng 发布于 2009-10-10 23:33

二分查找(也叫做折半查找)及PHP实现

折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。

【基本思想】

将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。

二分搜索法的应用极其广泛,而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了,但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定,正确地归纳奇偶数的各种情况,其实整理后可以发现它的具体算法是很直观的。

 

 使用PHP描述顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象可以是一个有序数组
//二分查找(数组里查找某个元素)
function bin_sch($array, $low, $high, $k){
    if ($low <= $high){
        $mid = intval(($low+$high)/2);
        if ($array[$mid] == $k){
            return $mid;
        }elseif ($k < $array[$mid]){
            return bin_sch($array, $low, $mid-1, $k);
        }else{
            return bin_sch($array, $mid+1, $high, $k);
        }
    }
    return -1;
} [break]

1、顺序查找的基本思想
     基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。

2、顺序查找的存储结构要求
  顺序查找方法既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构(使用单链表作存储结构时,扫描必须从第一个结点开始)。

3、基于顺序结构的顺序查找算法
(1)类型说明
  typedef struct{
    KeyType key;
    InfoType otherinfo; //此类型依赖于应用
   }NodeType;
  typedef NodeType SeqList[n+1]; //0号单元用作哨兵

(2)具体算法
  int SeqSearch(Seqlist R,KeyType K)
    { //在顺序表R[1..n]中顺序查找关键字为K的结点,
      //成功时返回找到的结点位置,失败时返回0
      int i;
      R[0].key=K; //设置哨兵
      for(i=n;R[i].key!=K;i--); //从表后往前找
      return i; //若i为0,表示查找失败,否则R[i]是要找的结点
    } //SeqSearch
④顺序查找的优点
     算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。

⑤顺序查找的缺点
  查找效率低,因此,当n较大时不宜采用顺序查找

//顺序查找(数组里查找某个元素)
function seq_sch($array, $n, $k){
    $array[$n] = $k;
    for($i=0; $i<$n; $i++){ 
        if($array[$i]==$k){
            break;
        }
    }
    if ($i<$n){
        return $i;
    }else{
        return -1;
    }
}


smarteng 发布于 2009-10-10 21:36

折半查找

算法思想:
  将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。
  折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查找表中的数据元素必须有序。
  算法步骤描述:
  step1 首先确定整个查找区间的中间位置
  mid = ( left + right )/ 2
  step2 用待查关键字值与中间位置的关键字值进行比较;
  若相等,则查找成功
  若大于,则在后(右)半个区域继续进行折半查找
  若小于,则在前(左)半个区域继续进行折半查找
  Step3 对确定的缩小区域再按折半公式,重复上述步骤。最后,得到结果:要么查找成功, 要么查找失败。
  折半查找的存储结构采用一维数组存放。
  折半查找算法举例
  对给定数列(有序){ 3,5,11,17,21,23,28,30,32,50},按折半查找算法,查找关键字值为30的数据元素。
  折半查找的算法讨论:
  优点: ASL≤log2n,即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。
  缺点:因要求有序,所以要求查找数列必须有序,而对所有数据元素按大小排序是非常费时的操作。另外,顺序存储结构的插入、删除操作不便利。
  考虑:能否通过一次比较抛弃更多的部分(即经过一次比较,使查找范围缩得更小),以达到提高效率的目的。……?
  可以考虑把两种方法(顺序查找和折半查找)结合起来,即取顺序查找简单和折半查找高效之所长,来达到提高效率的目的?实际上这就是分块查找的算法思想。
 


smarteng 发布于 2009-10-10 21:19
    1 2