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

插入排序算法学习

深入研究插入排序的实现

插入排序的基本思想是,经过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]时为止。

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

整数拆分问题的动态规划解法

其实也可以用背包来解决

输入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种拆分方法。这个题目是个比较明显的动态规划,如果想不到是背包问题,也可以写出状态转移方程如下。

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

堆排序(Heap Sort)算法学习

比较系统地学习下堆这个数据结构

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

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

求解最大公约数问题

使用C语言实现的2个解决方案

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

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

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

约瑟夫环算法解析

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

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

取几个0到1之间的随机数让其和大于1

一个简单的01背包问题

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

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

判断点是否在三角形内部

需要用到一些数学知识

给定三角形ABC和一点P(x,y,z),判断点P是否在ABC内。这是游戏设计中一个常见的问题。需要注意的是,这里假定点和三角形位于同一个平面内。连接点P和三角形的三个顶点得到三条线段PA,PB和PC,求出这三条线段与三角形各边的夹角,如果所有夹角之和为360度,那么点P在三角形内,否则不在,此法直观,但效率低下。

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

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

把一个数组的顺序打乱是很常用的算法,比如洗牌

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

发布于 2010-07-31 分类:algorithm

利用数组索引进行排序

比较有意思的一个排序算法

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

发布于 2010-07-23 分类:algorithm

裴波那契数列

这个数列的第n项的值是它前面两项之和

1, 1, 2, 3, 5, 8, 13, 21, 34, 55... 这个数列称为 fibonacci 数列。当 n 大于1的时候,这个数列的第n项的值是它前面两项之和。下面的程序用于打印出fibonacci 数列。

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

递归算法

计算阶乘

直接或间接调用自身的算法称为递归算法。使用递归往往使函数的定义和算法的描述简单易懂。另外还有一些数据结构,比如二叉树等,由于其本身固有的递归特性,特别适合用递归的形式来描述。递归算法的一个很普遍的应用就是求阶乘。

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

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

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