以图明志

计算机算法

[专题] 漫谈递归:递归与循环

大部分递归可以转化为循环
大家都知道递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的。递归是利用系统的堆栈保存函数当中的局部变量来解决问题的。递归说白了就是在栈处理栈上一堆的指针指向内存中的对象,这些对象一直不被释放,直到递归执行到最后一次跳出条件的时候,才一个个出栈。所以开销很大。

计算机算法

[专题] 漫谈递归:递归的效率问题

效率和开销问题是递归最大的缺点
递归在解决某些问题的时候使得我们思考的方式得以简化,代码也更加精炼,容易阅读。那么既然递归有这么多的优点,我们是不是什么问题都要用递归来解决呢?难道递归就没有缺点吗?今天我们就来讨论一下递归的不足之处。谈到递归就不得不面对它的效率问题。

计算机算法

如何用牛顿法求一个数的平方根

牛顿的逐步逼进方法
牛顿迭代法(Newton's method)又称为牛顿-拉夫逊方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式,因此求精确根非常困难,甚至不可能,从而寻找方程的近似根就显得特别重要。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。

计算机算法

[专题] 漫谈递归:二分查找算法的递归实现

用递归写一个二分查找
还有一个典型的递归例子是对已排序数组的二分查找算法。现在有一个已经排序好的数组,要在这个数组中查找一个元素,以确定它是否在这个数组中,很一般的想法是顺序检查每个元素,看它是否与待查找元素相同。这个方法很容易想到,但它的效率不能让人满意,它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。

计算机算法

[专题] 漫谈递归:字符串回文现象的递归判断

回文符合递归的两个条件
回文是一种字符串,它正着读和反着读都是一样的。比如level,eye都是回文。用迭代的方法可以很快地判断一个字符串是否为回文。用递归的方法如何来实现呢?如果一个字符串是回文,那么在它的内部一定存在着更小的回文。 比如level里面的eve也是回文。 而且,我们注意到,一个回文的第一个字符和最后一个字符一定是相同的。

计算机算法

[专题] 漫谈递归:递归需要满足的两个条件

还是拿斐波那契数列来做例子
递归,并不是简单的“自己调用自己”,也不是简单的“交互调用”。它是一种分析和解决问题的方法和思想。简单来说,递归的思想就是:把问题分解成为规模更小的、具有与原问题有着相同解法的问题。比如二分查找算法,就是不断地把问题的规模变小(变成原问题的一半),而新问题与原问题有着相同的解法。

计算机算法

[专题] 漫谈递归:递归的思想

用归纳法来理解递归
很多不理解递归的人(今天在csdn里面看到一个初学者的留言),总认为递归完全没必要,用循环就可以实现,其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环,大家都知道递归分两步,递和归,那么可以知道递归对于空间性能来说,简直就是造孽,这对于追求时空完美的人来说,简直无法接接受,如果递归仅仅是循环,估计现在我们就看不到递归了。

计算机算法

如何用随机函数rand5来构造随机函数rand7

一道经典的算法题
rand5() 它能够等概率生成 1-5 之间的整数。所谓等概率就是1,2,3,4,5 生产的概率均为 0.2 。现在利用rand5(), 构造一个能够等概率生成 1- 7 的方法。 这里有两个特别重要的点,一是 如果 rand5() + rand5(), 我们能够产生一个均匀分布的 1 - 10 吗? 答案是否定的。比如对于 6来讲(4+2, 2+4, 3+3),它被生成的生成的概率比1 (1+0,0+1)要大。

计算机算法

海盗分宝石面试题的头脑风暴

逆推的思考
五个海盗得到100颗钻石,颗颗价值连城。这五个海盗非常聪明,都想自己得到钻石最多。因而他们设计了个规则,根据抽签后的顺序, 每个人提出个分配方案,如果有半数以上(不包括半数)的人表决通过,则按这个方案执行,否则提出方案的人要被扔到海里喂鱼。下一个人开始提方案,以此类推。

计算机算法

趣味算法:老鼠试毒瓶问题

二进制的巧妙使用
大家应该都听说过这个老题目:有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?这个问题的答案也堪称经典:把瓶子从 0 到 999 依次编号,然后全部转换为 10 位二进制数。

计算机算法

JavaScript语言描述的最大公共子串问题

常见的做法是使用矩阵
求最大公共子串,常见的做法是使用矩阵。假设有字符串:abcdefg和字符串abcd,则可构成如下矩阵。对两个字符串的每一项都进行比较,若匹配则该项为1,不匹配则为0。然后求出对角线最长为1的那一段序列,即为最大公共子串。看上面的分开,似乎得使用二维数组了,在两个字符串都较大的情况下不是很划算,是否可以进一步优化?

计算机算法

趣味算法:生男生女的比例

阿里巴巴的一道面试题
阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第一个女孩,就不再生了,如果是男孩就继续生,直到生到第一个女孩为止,问若干年后,男女的比例是多少?刚看到问题是的思维逻辑:用递推法,假设一对夫妻,生了个女儿,就不再要了;另外一对夫妻,生了个儿子,再要一个,是女儿,然后也就不要了。第一感觉,应该是女的比男的多。

计算机算法

从1到1亿这1亿个数里面有多少个1?

遍历每个数再toString() 看看里面有多少个1
乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单的办法不外乎就是遍历每个数,然后toString() 看看里面有多少个1,最后全部加起来,这是我们得到标准答案的办法。群里3个人写了3个笨方法都跑出来了,3个笨方法,呵呵 有意思,笨方法也不一样。 程序的实现真是变幻莫测。

计算机算法

趣味算法:猴子搬香蕉问题

关乎数学规划
在博客园一篇文章末尾看到一个有趣的数学问题,据说是小学4年级的题目,摘引如下:一只小猴摘了300个香蕉,需要搬回家,每次最多搬100个。小猴离家100米,它每走1米,都需要吃掉1个香蕉来补充能量,请问它最多能够搬回家多少个?

计算机算法

如何提高筛选法求大范围素数的效率

学习一下这种求素数的算法
筛选法求素数有一个很通用的算法,就是在遍例该集合时,比方检验一个数N是否素数,用N除以2-N的开方,只要有一个能整除,就说明N不是素数。另外这道题要求用数组来计算。谓"筛选法"指的是"埃拉托色尼(Eratosthenes)筛法"。他是古希腊的著名数学家。

计算机算法

收集一些top软件公司经典算法面试题

从面试题中去学习
有一个整数数组,请求出两两之差绝对值最小的值,记住,只要得出最小值即可,不需要求出是哪两个数。写一个函数,检查字符是否是整数,如果是,返回其整数值。(或者:怎样只用4行代码编写出一个从字符串到长整形的函数?)给出一个函数来输出一个字符串的所有排列。 请编写实现malloc()内存分配函数功能一样的代码。给出一个函数来复制两个字符串A和B。
2 / 6 首页 < Prev 1 2 3 4 5 Next > 尾页 页码: