以图明志

计算机算法

利用数组的索引也可以排序

比较有意思的一个排序算法
看到一道算法面试题,比较有趣,我自己用C做了一下。题目:随机生成10个100以内的整数,把数据从小到大排序,而且算法复杂度只能是1。这个算法比较有意思的地方是,首先建立一个数组B,其元素个数为数组A的最大元素值,然后用A的元素作为B的数组下标,然后给存在的B元素赋值,这样就可以用循环把下标输出出来。

计算机算法

如何将一个数组的元素顺序打乱

把一个数组的顺序打乱是很常用的算法,比如洗牌
给定一个数组,要求把数组内元素的顺序随机打乱,然后输出,主要是要保证效率。 这个算法其实简单,首先从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。

计算机算法

约瑟夫环(Josephus)问题的C++算法模拟

约瑟夫环算法解析
这个算法的时间复杂度为O(n),相对于模拟算法已经有了很大的提高。算n,m等于一百万,一千万的情况不是问题了。可见,适当地运用数学策略,不仅可以让编程变得简单,而且往往会成倍地提高算法执行效率。

计算机算法

最大公约数问题的两种方法

使用C语言实现的2个解决方案
最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, a2, ..., an] 的最大公因数。通常有两种表示方式:它们的所有公因数中最大的那一个;如果自然数 m 是这 n 个自然数的公因数,且这 n 个数的任意公因数都是 m 的因数,就称 m 是这 n 个数的最大用因数。

计算机算法

图解堆排序Heap Sort算法

比较系统地学习下堆这个数据结构
堆排序的时间复杂度是O(nlgN),与快速排序达到相同的时间复杂度。但是在实际应用中,我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现。堆排序的主要用途,是在形成和处理优先级队列方面。另外,如果计算要求是类优先级队列(比如,只要返回最大或者最小元素,只有有限的插入要求等),堆同样是很适合的数据结构。

计算机算法

整数拆分的动态规划解法

其实也可以用背包来解决
输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方法。例如:n=5,k=3 则有n=3+2, n=3+1+1, n=2+1+1+1, n=2+2+1, n=1+1+1+1+1这5种拆分方法。这个题目是个比较明显的动态规划,如果想不到是背包问题,也可以写出状态转移方程如下。

计算机算法

图解插入排序算法

深入研究插入排序的实现
插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止。

计算机算法

深入探讨各种背包算法问题

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

计算机算法

只有10%的程序员可以把二分查找写正确

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

计算机算法

哥德巴赫猜想的程序验证

任何一个充分大的偶数都可以表示为两个素数之和
Timus Online Judge 网站上有这么一道题目:1356. Something Easier。这道题目的输入是一组 2 到 109 之间整数,对于每个输入的整数,要求用最少个数的素数的和来表示。这道题目的时间限制是 1 秒。我们知道著名的哥德巴赫猜想是:任何一个充分大的偶数都可以表示为两个素数之和。

计算机算法

一道PHP冒泡排序算法笔试题

PHP实现一个有冒泡排序的类
一道PHP笔试题:请使用伪语言结合数据结构冒泡排序法对以下一组数据进行排序 10 2 36 14 10 25 23 85 99 45。关于冒泡排序大家应该都非常熟悉了,原理就不多说了,这里只做简单记录。下面是参考代码。

计算机算法

常见笔试题字符串复制strcpy()的思路

一个问题的多个误区
题目:已知strcpy函数的原型是char * strcpy(char * strDest, const char * strSrc);不调用库函数,实现strcpy函数。解释为什么要返回char *。不检查指针的有效性,说明答题者不注重代码的健壮性。检查指针的有效性时使用((!strDest)||(!strSrc))或(!(strDest&&strSrc))。

计算机算法

图解JavaScript合并排序

JavaScript也可以做算法练习
合并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。有这样一组数据,{5,4,1,22,12,32,45,21},如果对它进行合并排序的话,首先将它从中间分开,这样,它就被分成了两个数组{5,4,1,22} {12,32,45,21}。

计算机算法

[专题] 算法导论:选择排序的原理与实现

swf动画图解
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。
6 / 6 首页 < Prev 2 3 4 5 6 Next > 尾页 页码: