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

判断一个整数是否是2的N次方

最保险的还是位运算

给定一个整数num,判断这个整数是否是2的N次方。比如,2,4,8是2的那次方,6,10不是2的N次方。因此我觉得, 最保险的还是位运算, 看多少个1, 来的最实在。当然这里存在一个负数的问题。第一位是1, 剩下全是0的问题。 不过有一位聪明的回复者提供了一个很强大的方法来避开负数的用例:他给参数定的类型是uint!

发布于 2011-03-03 分类:algorithm

如何从容面对面试时的算法题

面对一个问题,改如何下手思考将其解决

一般关于算法的文章,都是从经典算法讲起,一种一种算法介绍,见得算法多了,自然就有了感悟,但如此学习花费的时间和精力却是过于巨大,也不适合在博客里面交流。这一篇文,却是专门讲快捷思路的,很多人面对算法题的时候几乎是脑子里一片空白,这一篇文章讲的就是从题目下手,把毫无思路的题目打开一个缺口的几种常见技巧。

发布于 2011-03-02 分类:algorithm

各种进制转换的原理分析介绍

进制转换是计算机的基础

我们通常习惯的“十进制”:逢十进一。但是,在电脑中,“十进制”是不吃香的。换句话说,由于为了使电脑的物理构造更加简单可靠,电脑被设计成“只了解二进制”的工作模式。进制转换是计算机的基础,下面我们介绍下各种机制间的相互转换原理。

发布于 2011-02-26 分类:algorithm

不使用第三个变量交换两变量

不使用第三个变量互换两个变量的方法

交换两个变量,通常我们的做法是(尤其是在学习阶段):定义一个新的变量,借助它完成交换。这种算法易于理解,特别适合帮助初学者了解计算机程序的特点,是赋值语句的经典应用。在实际软件开发当中,此算法简单明了,不会产生歧义,便于程序员之间的交流,一般情况下碰到交换变量值的问题,都应采用此算法。

发布于 2011-02-25 分类:algorithm

双向队列算法的PHP实现

学习下双向队列的定义与使用

deque,全名double-ended queue,是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双向队列(双端队列)就像是一个队列,但是你可以在任何一端添加或移除元素。而双端队列是一种数据结构,定义如下……

发布于 2011-02-22 分类:algorithm

楼梯问题的一些解决方法

斐波那契数列的多种算法实现

假设一个楼梯有 N 阶台阶,人每次最多可以跨 M 阶。例如楼梯总共有3个台阶,人每次最多跨2个台阶,也就是说人每次可以走1个,也可以走2个,但最多不会超过2个,那么楼梯总共有这么3种走法。现在要求用程序实现计算台阶的所有走法的总数。其实就是个斐波那契数列。

发布于 2011-02-18 分类:algorithm

只有1/10的程序员能正确实现二分查找

二分查找出现在1946年,但1962年才有没bug的二分查找

二分查找可以解决(预排序数组的查找)问题:只要数组中包含T(即要查找的值),那么通过不断缩小包含T的范围,最终就可以找到它。一开始,范围覆盖整个数组。将数组的中间项与T进行比较,可以排除一半元素,范围缩小一半。就这样反复比较,反复缩小范围,最终就会在数组中找到T,或者确定原以为T所在的范围实际为空。

发布于 2011-02-12 分类:algorithm

二叉树中的最近公共祖先问题

寻找二叉树中两个节点的最近的公共祖先

算法思想:这道题的关键在于每个节点中包含指向父节点的指针,这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent,然后将q的所有父节点依次和p->parent作比较,如果发现两个节点相等,则该节点就是最近公共祖先,直接将其返回。如果没找到相等节点,则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。

发布于 2011-02-11 分类:algorithm

买书折扣最优惠问题解法

编程之美买书问题常数时间空间解法

题目:在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。

发布于 2011-02-09 分类:algorithm

程序员要如何提高数学水平

数学能让程序员的水平更高

程序员不认为他们需要了解数学。我常常听到这样的话,我不知道还有没有不同意的。甚至于以前是主修数学的程序员也告诉我他们真的不是常常使用到数学!他们说,更重要的是要去了解设计模式,面向对象原理,软件工具,界面设计,以及一些其他类似的东西。

发布于 2011-02-04 分类:algorithm

极大极小博弈树Minimax Game Tree介绍

常用于编写电脑之间的游戏程序

极大极小博弈树(Minimax Game Tree)用于编写电脑之间的游戏程序,这类程序由两个游戏者轮流,每次执行一个步骤。当然,所有可能的步骤构成了一个树的结构。例如下面的图就是一个MGT,它表示了Tic-Tac-Toe游戏的前两步所有可能的步骤。

发布于 2011-01-26 分类:algorithm

求能被1到20的数整除的最小正整数

一个思考的小捷径

求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这20个数的最小公倍数。求n个数的最小公倍数,以a,b,c三个数为例,他们的最小公倍数等于:先求a与b的最小公倍数m,然后m和c的最小公倍数即着三个数的最小公倍数。

发布于 2011-01-20 分类:algorithm

背包问题之硬币找零问题

解题思路:01背包,完全背包

设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中,商店里各面值的硬币有足够多。在1次购物中希望使用最少硬币个数。例如,1 次购物需要付款0.55 元,没有5 角的硬币,只好用2*20+10+5 共4 枚硬币来付款。

发布于 2010-12-24 分类:algorithm

一道蒙提霍尔问题的思考

蒙提霍尔问题,亦称为蒙特霍问题或三门问题

一个监狱看守从三个罪犯中随机选择一个予以释放,其他两个将被处死。警卫知道哪个人是否会被释放,但是不允许给罪犯任何关于其状态的信息。让我们分别称罪犯为X,Y,Z。罪犯X私下问警卫Y或Z哪个会被处死,因为他已经知道他们中至少一个人会死,警卫不能透露任何关于他本人状态的信息。警卫告诉X,Y将被处死。X感到很高兴,因为他认为他或者Z将被释放。

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

找出3个和为15的单位数组合

简单记录一下

从1-9这九个数字中任意取三个数,这三个数之和必须为15。很常见的编程题,用三重循环嵌套就可以将符合要求的组合筛选出来,这里简单记录一下。

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

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

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