简明现代魔法 -> 计算机算法

各种排序算法的C++实现与性能比较

了解下各种排序的效率问题

排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法,那么哪些排序算法比较有效率,哪些算法在特定场合比较有效,下面将用C++实现各种算法,并且比较他们的效率,让我们对各种排序有个更深入的了解。

发布于 2010-11-13 分类:algorithm

时间复杂度为O(1)的删除链表结点方法

从分析与思考中找到答案

这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n) 了。

发布于 2010-10-30 分类:algorithm

寻找丑数(Ugly Number)

只包含因子2、3和5的数称作丑数

我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。下面是一道在网络上广为流传的面试题,据说google曾经采用过这道题。

发布于 2010-10-29 分类:algorithm

用分治法求数组中的最大最小值

分治算法的一个简单应用

分治算法通俗的讲就是把一个规模比较大的问题分成n个规模较小的问题来解决,再将每个小规模的问题进行合并,最后得到结果。通常问题规模比较大难以用普通的编程方法实现,或者不可能实现的时候采用分治算法,能够简化问题的解决。下面举个例子,求出一个数组中的最大值和最小值。

发布于 2010-10-26 分类:algorithm

合并排序算法介绍

合并算法采用分治法的思路

合并算法采用分治法的思路,即问题划分成n个规模较小而结构和原来问题相似的子问题,递归解决这些子问题,然后合并结果,最终得到原来问题的解。合并算法主要分为三个部分,第一个部分是分解,将运来的问题分解成两个包含n/2个元素的数组的排序的问题,然后分别递归调用函数解决这两个数组的排序问题。

发布于 2010-10-25 分类:algorithm

计算机编程中一些重要的算法

你应该了解一下这些算法来拓宽视野

下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。(注:本篇文章并非翻译,其中的算法描述大部份摘自Wikipedia,因为维基百科描述的很专业了)

发布于 2010-10-20 分类:algorithm

蚂蚁爬木杆问题的一点思考

其实更像一个脑筋急转弯

题目如下:有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过两只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆 的最小时间和最大时间。

发布于 2010-10-19 分类:algorithm

面试中常见的一些算法问题

在面试中你也许会遇到其中的一些

Problem 1 : Is it a loop ? (判断链表是否有环?)方法:使用两个指针,从头开始,一个一次前进一个节点,一个前进2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。同样的,可以找到链表的中间节点。同上。

发布于 2010-10-17 分类:algorithm

欧几里德算法(辗转相处算法)练习

介绍欧几里德算法的算法根据

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b)。证明:a可以表示成a = kb + r,则r = a mod b。假设d是a,b的一个公约数,则有:a % d == 0 , b % d == 0,而r = a - kb,因此 r % d == 0 。因此d是(b,a mod b)的公约数。

发布于 2010-10-15 分类:algorithm

求平方根sqrt()函数的底层算法效率问题

数学在程序设计中是非常有用的

虽然有可能你平时没有想过这个问题,不过正所谓是“临阵磨枪,不快也光”,你“眉头一皱,计上心来”,这个不是太简单了嘛,用二分的方法,在一个区间中,每次拿中间数的平方来试验,如果大了,就再试左区间的中间数;如果小了,就再拿右区间的中间数来试。比如求sqrt(16)的结果,你先试(0+16)/2=8,8*8=64,64比16大,然后就向左移,试(0+8)/2=4,4*4=16刚好。

发布于 2010-10-06 分类:algorithm

Google校园招聘题:程序员买房

顺便谈一下社会问题

Google的2011年校园招聘宣讲会分别在北大和清华举行。其中前10个选择题中有一个特别雷人的,题如下:现在北京有一套房子,价格200万,假设房价每年上涨10%,一个软件工程师每年固定能赚40万。如果他想买这套房子,不贷款,不涨工资,没有其他收入,每年不吃不喝不消费,那么他需要几年才能攒够钱买这套房子?

发布于 2010-09-29 分类:algorithm

求和最大的连续子串问题

网易的一道笔试题

给定一整型数字a[]={a[0],...,a[n])},找出连续子串{a[x]),a[x+1],...,a[y]},使得和最大,其中,0<=x<=y<=n。要求时间复杂度为O(n)。解决思路:和最大的子串一定是以数组a中的某一个元素为结束,所以我们分别对每一个元素作为当前子串的结尾计算当前和最大的子串,再对计算出的所有子串和进行比较,最大的那个就是解。

发布于 2010-09-29 分类:algorithm

不使用递归求解裴波那契数列

用函数求解裴波那契数列

裴波那契数列 1,1,2,3,5,8,13,21…………,一般来说使用递归会使问题简单很多。但是有些时候会要求我们不用递归解决这类问题,比如Lisp这种不支持递归的语言,或者对程序的执行效率要求很高,或者面试等等场合。本文给出一种不使用递归求解裴波那契数列的方案。

发布于 2010-09-15 分类:algorithm

大整数相加问题

用字符串保存操作数和结果

在计算机中,由于处理器位宽限制,只能处理有限精度的十进制整数加减法,比如在32位宽处理器计算机中,参与运算的操作数和结果必须在-231~231-1之间。如果需要进行更大范围的十进制整数加法,需要使用特殊的方式实现,比如使用字符串保存操作数和结果,采取逐位运算的方式。

发布于 2010-08-26 分类:algorithm

背包问题介绍与分析

深入探讨各种背包问题

背包问题是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品,重量各不同。此人通过秘密地选择一部分物品并将它们放 到背包中来加密消息。背包中的物品中重量是公开的,所有可能的物品也是公开的,但背包中的物品是保密的。附加一定的限制条件,给出重量,而要列出可能的物品,在计算上是不可实现的。

发布于 2010-08-18 分类:algorithm
 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们