以图明志

计算机算法

在数字前面补0的几个实现思路

一个问题的多个思路
要求1-9的数字前面加0,如01 02 ....10 11....,就是用 JavaScript 代码实现空位补零,比如 pad(12, 3) => 012之类的。这里介绍四种javascript的方法,顺便也给出PHP的方法。

计算机算法

算法导论中一个蒙提霍尔问题

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

计算机算法

C/MFC 折半查找(二分查找)

分治的思想
折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。二分搜索法的应用极其广泛,而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了,但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。

计算机算法

多少个0到1之间的随机数之和大于1?

一个简单的01背包问题
数学常数最令人着迷的就是,它们常常出现在一些看似与之毫不相干的场合中。 随便取一个 0 到 1 之间的数,再加上另一个 0 到 1 之间的随机数,然后再加上一个 0 到 1 之间的随机数⋯⋯直到和超过 1 为止。一个有趣的问题:平均需要加多少次,才能让和超过 1 呢?答案是 e 次,自然对数。

计算机算法

大整数相加的实现思路

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

计算机算法

C语言/MFC 选择排序

MFC的Edit Control用法
本文的目的是了解C语言下的选择排序,并分别在C与MFC下实现选择排序。关于MFC下Edit Control的换行,可以用下面的方法:sort_result = sort_result + _T("~ \r\n"); 除了使用 \r\n 之外,还要对 CEdit 的属性进行设置: Auto HScroll 设置为 False, MultiLine 设置为 True,Want Return 设置为 True。

计算机算法

C语言与MFC随机数组生成

rand()/nMax
C语言/C++产生随机数问题,这里要用到的是rand()函数, srand()函数,C语言/C++里没有自带的random(int number)函数。用按钮触发事件,先生成10个随机数字,装入数组,再将数组元素转换成CString类型拼接后在Edit Control控件上显示。

计算机算法

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

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

计算机算法

寻找和最大的连续子串

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

计算机算法

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

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

计算机算法

一些关于字符串的面试题

几道很值得参考的字符串问题
计算机笔试和面试最常考察的就是字符串的各种操作。字符串处理是我们程序员日常工作最常遇到的问题,能够体现程序员的基本功。google笔试:编码实现求给定字符串(全为小写英文字母)的最小后继、中兴:编码实现字符串右移n位、新邮通:字符串反转……

计算机算法

求大数阶乘的算法

介绍一种非常规方法
在很多C/C++的书上,都给出了两种阶乘的计算方法,一种为利用递归进行计算;一种利用阶乘的定义进行计算。下面给出这两种算法的C程序源代码。1. 利用阶乘的定义进行计算。2. 利用递归进行计算。但是,由于阶乘的结果随着n的增大将急剧增加。最终导致即使是unsigned long类型的整数也无法保存计算结果。那么,这时候,我们应该怎么办呢?

计算机算法

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

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

计算机算法

丑数Ugly Number查找算法

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

计算机算法

用分治法求数组中的最值

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

计算机算法

JavaScript排序算法之归并排序

归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。
4 / 6 首页 < Prev 2 3 4 5 6 Next > 尾页 页码: