Browsed by
Category: 算法

各以1/2的概率输出0和1

各以1/2的概率输出0和1

在看CLRS中的第五章,发现课后的这道习题非常有意思。 题目:Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 – p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability...

Read More Read More

判断数组中是否存在两个数之和为指定值

判断数组中是否存在两个数之和为指定值

题目是CLRS 2.3-7。原题如下: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x,determines whether or not there exist two elements in S whose sum is exactly x. 初看这个题目,就大约想到用排序来解决。我大概的思路是先排序,然后再用二分查找法去寻找。 看了看CLRS的答案,给出的方法跟我思路不同,他的想法是,添加一个数组,其值为原输入数组中值与x的差,删除掉两个数组中相同的数,然后合并排序那两个数组,如果合并排序后数组中相邻的两个数相同,则说明原数组中有sum为x的元素。 觉得答案给出的方法也比较有意思,于是试着实现了一下。过程中还真遇到了点问题,下次要吸取教训。 问题是这样的,要删除原数组中相同的元素,我用的如下的方法: // assume array, length is defined. int i = 0; for(; i < length – 1; i++){ if(array[i] == array[i+1]){ int tmp = i; while(tmp < length – 1){ array[tmp] = array[tmp + 1]; tmp++; } } } 看出问题在哪儿了吗?在遇到这样{-26 -23 -22 -19…

Read More Read More

推荐一个win下用的算法研究环境

推荐一个win下用的算法研究环境

通常用到的IDE都比较庞大,我个人觉得不太简洁,因为如果单纯只是算法研究的话,一个绿色的开发环境会比较方便。 现在我使用的是一个叫msys-cn的项目,它地址是http://code.google.com/p/msys-cn/,从这个地址下载压缩包,安装后,再运行msys.bat就可以进入环境了,一点都不需要自己配置。之后无论是vim还是gcc都很方便。 另外这个项目首页还有如下的教程,写得非常不错,强烈推荐! 1. 介绍、下载与安装方法 2. 操作系统历史回顾 3. MSYS开发环境与开发工具 4. 基于MSYS环境的精短C语言教程 5. 基于MSYS、MingW的Windows编程教程 6. 基于MSYS的 Flex & Bison (编译器开发工具)使用教程 7. 基于MSYS的Win32动态链接库DLL开发 8. 基于MSYS的Windows驱动程序开发 9. 通用PID算法例子 10. 数据结构与算法快速教程 11. 让kqemu加速模块可以在windows的mingw上编译的代码补丁 12. 通用数学矢量类算法封装 13. 手写词法分析教程 14. 通用多源代码格式支持、依赖关系支持Makefile msys-cn

插入排序

插入排序

按照计划,接下来开始实现书中的一些算法。今天是比较简单的插入排序法,但是也不是一次就成功,可见再简单的算法,也需要真正实践才能确保没有问题。 主要问题是处在插入排序需要找到一个key,用于标记当前需要插入的值。其原理想象起来也简单,就是想插入扑克牌一样,把目标扑克牌插入一个已经排序好的牌中,所以需要一个key来标记当前要插入的牌。而平时写冒泡比较多,所以很习惯的就写了两个for循环,然后才发现不太好往下面写了,其实第二循环换成while更加顺畅。 #include void InsertionSort(int array[], int length){ int i = 1; int j = 0; for(; i < length; i++){ int key = array[i]; j = i - 1; while(j >= 0 && array[j] > key){ array[j+1] = array[j]; j–; } array[j+1] = key; } } int main(int argc, char** argv){ int array[] = {8, 7, 6, 5, 4, 3, 2, 1}; int length = 8; int i = 0; printf(“before sort\n”); for(; i < length; i++){ printf("%d ",...

Read More Read More

单链逆序寻找

单链逆序寻找

最近老是接触面试,接触了不少题。今天电话面试被问到了这么一题,当时没有给出最佳答案,过后在网上搜索了一下,发现果然还是有更简单的解决办法。(人还是这么懒,没有自己思考,罪过) 题目是:给你一个单链,要求找出倒数第M个元素。 直观的方法是:遍历一次得到元素总长N,再遍历一次第N-M个元素。 另一种改良方法是:遍历一次改单链为双链,再从尾部找到倒数第M个元素。 最佳的办法是:设置两个遍历指针,第一开始遍历并计数,当计数到第M个时,同时开始第二个遍历,当第一个到尾部时,第二个指向的即使倒数第M个元素。 我觉得在面试的时候出这种题目,如果事先没有接触过类似题目的人,能够答出的可能性不高。因为这种解答属于某种灵光一现的解决方案,即使答出来了,也不见得就是真正的想到了,也可能跟我一样是搜索到了类似题目。尽管如此,这道题目解决方法本身还是非常值得学习的,体现了解决问题时,利用了增加的办法,通常人都只想到用一个指针来遍历,如果增加一个,就能解决问题,和这个类似的问题还有寻找双链中的是死链。

NP完全学习小结1

NP完全学习小结1

连续学习这个章节已经大概有两周了,学习进度慢的原因有两个: 这部分的内容的确很难 最近节假日比较多,而且个人还在考虑职业规划的问题,所以有点分心。 无论如何,现在先总结一下吧。注:本人还是不太会用严格的语言来描述问题。 P类问题是指一类可以在多项式时间内解决的问题。 NP类问题是指一类可以再多项式时间验证的问题。 NP完全问题是指可以在多项式时间内验证,但是难度又是跟别的NP问题一样难的问题。这里的难(hard)指的是,一旦确定它是一个NP完全问题,那么任何NP问题都可以用这个问题规约。 规约是指可以用这个问题的解在多项式时间解决另一个问题。 NP完全问题之所以有这么大的魅力是因为,一旦在多项式时间解决了一个NP完全问题,那么就证明了P=NP。现在这个问题还没有答案。 接下来还学习了一些NP完全问题,如下图。目前的困扰是不熟悉这些问题,我的学习方式比较倾向于通过例子来理解,而这节的介绍中例子比较少,所以不太理解其中的例子,郁闷中。介绍这些NP完全问题,是因为如果面对一个问题,可以通过其中的已知的NP完全问题规约,那么就说明这个问题是NP完全问题。

RSA公钥加密系统

RSA公钥加密系统

公钥加密系统(public key cryptosystem)可以对传输于两个通信单位之间的消息进行加密,这样即使窃密者窃听到被加密的信息,也不能对加密信息进行破译。 RSA公钥加密系统主要是基于以下事实:寻找大素数是很容易的,但是要把一个数分解为两个大素数的积确实相当困难的。 貌似看起来这套系统是很神秘的,其实RSA系统分析后,确实两个很简单的公式就能表达,这也从一个侧面表现了数学之美。下面我就总结一下这周学习这个系统的一些内容。 RSA加密系统中,每个参与者都有一把公钥和一把密钥。密码学上习惯把参与者叫做“Alice”和“Bob”。用[math]P_A[/math]和[math]S_A[/math]分别代表alice的公钥和密钥。[math]P_B[/math]和[math]S_B[/math]分别代表bob的公钥和密钥。M为要加密的信息。有如下公式成立: [math]M=S_A(P_A(M))[/math] [math]M=P_A(S_A(M))[/math] 这下明白了吧,有这两个公式成立,那么经过密钥处理过的信息,再经过公钥处理,就能还原成源信息。这里存在的一个技术问题是,如何保证公开了公钥,而外界的敌人不会通过公钥还原出密钥。这也就是RSA的重要假设一个数分解为两个大素数的积确实相当困难的。 RSA系统可以有这么几种应用: bob取得alice的公钥,bob把信息用公钥加密,然后发给alice,alice再用密钥解开。 alice可以用RSA系统签名。例如她可以用用密钥签署信息M,把签名和M一块发送给bob,bob再用alice的公钥来还原签名,如果和信息M相同,则证明是alice签名的信息。 签署者首先把他的数字签名附在信息的后面,然后再用他希望的接受者的公钥对得到的信息/签名对进行加密。接受者运用他的密钥对收到的消息进行解密,以同时获取原始信息和数字签名,然后,他可以用签署者的公钥对签名进行验证。 无公钥加密系统。这个系统加密密钥和解密密钥是相同的。如果alice希望私下把一条很长的消息M发送给bob,在无公钥加密系统中,她选取一把随机密钥K,然后运用K对M进行加密,得到密文C。她利用bob公开的RSA密钥对K进行加密。她把(C,[math]P_B(K)[/math])传送给bob,bob对[math]P_B(K)[/math]解密后得到K,然后再用K对C进行解密从而得到M。 “混合”模式。如果Alice希望签署一条消息M,她首先用hash函数h作用于M得到指纹h(M),然后,她用密钥来加密h(M)。她把(M,[math]S_A(h(M))[/math])做为她签署的M版本发送给bob。bob可以通过计算h(M),然后验证用[math]P_A[/math]作用于他收到的[math]S_A(h(M))[/math],看是否等于h(M)来验证签名的真实性。 RSA系统是这么实现的:(偷懒用原文了) Select at random two large prime numbers p and q such that p ≠ q. The primes p and q might be, say, 512 bits each. Compute n by the equation n = pq. Select a small odd integer e that is relatively prime to φ(n), which equals (p – 1)(q – 1). Compute d as the multiplicative inverse of e, modulo φ(n). Publish…

Read More Read More

线性规划

线性规划

用线性规划的方法可以解决这一类的问题:可以表述问题为最大化或最小化某一个目标,其中包含的资源有着约束条件,而目标和约束条件都可以用线性函数来表示。 CLRS中介绍了解决线性规划的方法—单纯形算法。其中精妙的地方包括: 1.将线性规划转换为标准型。 这里有4种原因使得线性规划不是标准型: * 目标函数可能是一个最小化,不是最大化 * 可能有的变量不具备非负性约束 * 可能有等式约束 * 可能有大于等于的约束 转换的基本方法就是: 如果是最小化,那么乘-1转换 如果是非负性,那么用x’-x”,并限制x’>=0, x”>=0来替换原有的x 如果是等式,就用>=0&&<=0来替换 经过这些巧妙的转换,就可以变为标准型了。 2.单纯形算法的基本原理就是主元的替换,那么问题就是定义谁是主元,谁被换入。 其基本思想为: * 主元的选择是选择把目标中为正的项 * 换入的选择是在限制条件中,放大主元,选择其中最紧的约束,它限制了主元可以增大多少 3.对偶性 找到了一个方法,把原有的最大化问题转化为最小化问题,而最大化问题和最小化问题相等的时候,是最优化的解。进一步的,证明单纯型法得出的解满足对偶性,那么单纯型算法的解就是最优解。

终于完成第二轮CLRS了

终于完成第二轮CLRS了

终于完成了第二轮的学习,打算回顾一下。 第一遍看这本书是去年这个时候,基本上是下班之后,如果有时间就会看看,那时候躺在床上看,基本没有用过笔,主观上也没有重视这件事情,所以第一是看得慢,第二是看得不细,最后大概看到最大流的那章。之后发生了一些事情,就中断了看书,这么一晃,1年就过去了。 第二遍看这本书,是在今年的9月底。这次是下定了决心要好好看这本书,主要的方法就是根据MIT的公开课视频,按照其制定的计划来学习。至今,除了最后一个Quiz没有完成(打算周末搞定),剩余的课程内容都已经学习完成了。 学习算法是个困难的过程,这也是我这个博客存在的原因之一,没有人可以宣泄,只能在这上面写写。客观上的原因很多,导致学习过程比较艰辛,多东西都不明白。但是我坚信,只要有恒心,就一定能掌握。 顺便抱怨一下,MIT的课程真的很恐怖,很难想象那里的学生整天学习这类东西。首先,这个课程是给本科生设计的,我相信在国内的学校,可能很多研究生都没有掌握里面的知识,其次,它还布置了大量的练习,其中很多的练习,都需要花大量时间,我不认为我比那些上课的学生差,因为课上教授提问时,那帮孩子基本答不上来,所以我花了很多时间的练习,他们应该也需要花很多时间,然而问题就是,我仅仅是学习这一门课,他们可是要学习很多门课的,很难想象他们如何能够完成这么重的学业。因此,我认为我们国内大学还是比较轻松的,让他们羡慕嫉妒恨吧。 我们中国教育体系下的孩子,想象力都会比较贫乏,这一点在学习这门课上我也有深刻的体会。如果是我们的学校教这门课,布置的练习一定都是那种只有一个标准答案的练习。而这门课的练习就跟我以前接触过的不同,练习基本都是一些故事型,出一些跟章节相关的例子,另外练习的问题也很有意思,基本都是逐步引导你去思考的。 唠叨了一堆,最后订一下后续的计划。 1、挑选CLRS书中算法问题精选中的章节阅读。 2、第三轮看书。这次的重点是用c语言实现其中的算法,并且每一类算法都记录心得到本博客,另外挑选课后练习做。 3、看一下TAOCP中关于概率的章节。

Cache-Oblivious Algortihms

Cache-Oblivious Algortihms

连续4天都在研究这个,始终没有掌握到精髓,看Erik D.Demaine的论文,也觉得讲的不太明了,好多地方都是一带而过,根本就没有详细解释。也许Erik太天才了,里面的东西在他看来都是小儿科,所以不必解释,郁闷中。 顺带说说,我这个粗心的毛病还真是改不了,这几天一直都认为这个算法是Cache Obvious,怎么也没有理解这种算法到底怎么obvious了,今天才发现是Cache Oblivious,那就能理解了,是在不经意间就完成了cache。根据定义Cache Oblivious算法是设计一种不用知道B和M的External-memory算法,按照课堂上的说法是不用知道B和M的Cache aware算法。 唉,继续学习吧。