Apollo Connecting the World

Diligence and Intelligence

Archive for the ‘Algorithms’ Category

[zz]常用算法经典代码(C++版)

leave a comment »

常用算法经典代码(C++版)

一、快速排序

void qsort(int x,int y) //待排序的数据存放在a[1]..a[n]数组中

{int h=x,r=y;

int m=a[(x+y)>>1]; //取中间的那个位置的值

Read the rest of this entry »

Written by apollozhao

2012/10/24 at 04:05

[zz]知其所以然(三):为什么算法这么难?-刘未鹏

leave a comment »

from: http://blog.renren.com/blog/322702581/738734136

作者:刘未鹏  原帖地址  《编程之美》微博

不知不觉《知其所以然》系列竟然也写到第三篇了,虽然前面两篇也说了不少,但是总觉得还有东西没有说“透”,或者说没有说“好”。所以这篇试图从不同的角度用更好的例子来继续深入阐述。(感谢silwile对本文的review和意见)


广大码农同学们大多都有个共识,认为算法是个硬骨头,很难啃,悲剧的是啃完了还未必有用——除了面试的时候。实际工程中一般都是用现成的模块,一般只需了解算法的目的和时空复杂度即可。

不过话说回来,面试的时候面算法,包括面项目中几乎不大可能用到的算法,其实并不能说是毫无道理的。算法往往是对学习和理解能力的一块试金石,难的都能掌握,往往容易的事情不在话下。志于高者得于中。反之则不成立。另一方面,虽说教科书算法大多数都是那些即便用到也是直接拿模块用的,但不幸的是,我们这群搬砖头的有时候还非得做些发明家的事情:要么是得把算法当白盒加以改进以满足手头的特定需求;要么干脆就是要发明轮子。所以,虽说面试的算法本身未必用得到,但熟悉各种算法的人通常更可能熟悉算法的思想,从而更可能具备这里说的两种能力。

那么,为什么说算法很难呢?这个问题只有两种可能的原因:

Read the rest of this entry »

Written by apollozhao

2011/07/15 at 09:55

算法和数据结构的可视化演示

leave a comment »

Written by apollozhao

2011/06/16 at 12:31

鸡兔同笼问题新解

leave a comment »

博客作者注:

可以如此计算:

直接算鸡和兔抬起两只脚,则现在还有40-15*2=10只脚,都是兔子的。

则兔子有10/2=5只,鸡有15-5=10只。

 

部分答案转载自:http://blog.renren.com/share/230742523/6619322508

大家想必还记得鸡兔同笼问题吧?(给定鸡和兔的总个数和脚的总数,求分别有多少支鸡和兔)。。。当时为了绕过解方程。。我们的解题思路貌似是,假设所有的都是鸡,然后脚数少了若干只。。所以应该有些兔被误认为了是鸡,所以。。blablabla…

嗯,今天刷google buzz的时候无意间看到一个新的算法,更人性化,更容易理解:

       现在问题是,已知共有鸡和兔15只,共有40只脚,问鸡和兔各有几只。

算法:

  1. 假设鸡和兔训练有素
  2. 吹一声哨,它们抬起一只脚,(40-15=25)
  3. 再吹一声哨,它们又抬起一只脚,(25-15=10)
  4. 这时鸡都一屁股坐地上了,兔子还两只脚立着
  5. 所以,兔子有10/2=5只,鸡有15-5=10只。

哈哈哈~~~~太有趣了~~~ 要是当年就有这么先进的算法,会有更多人喜欢数学滴~~~

Written by apollozhao

2011/05/22 at 16:49

[zz]可视化数据结构和算法

leave a comment »

from: http://blog.renren.com/share/1780465771/6408297826

友情提示,一下链接,建议用chrome浏览器打开!

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下面并翻译了一下,大家可以直接点击了。

不知道国内的教育有没有相关的教学课件,至少在我大学的时候是没有的。

基础

索引 Read the rest of this entry »

Written by apollozhao

2011/05/10 at 21:44

[zz]最大公约数(Gcd)两种算法(Euclid && Stein) [整理]

leave a comment »

from: http://www.cnblogs.com/drizzlecrj/archive/2007/09/14/892340.html

很老的东东了,其实也没啥好整理的,网上很多资料了,就当备用把:-)

1. 欧几里德算法和扩展欧几里德算法

欧几里德算法
欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:

定理:gcd(a,b) = gcd(b,a mod b)

证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a, d|b,而r = a – kb,因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数,则
d | b , d |r ,但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

Read the rest of this entry »

Written by apollozhao

2010/12/14 at 21:29

[zz]ACM学习教材

leave a comment »

from: http://dking94.blog.51cto.com/528254/150031

 

入门三本:《数据结构与算法》(傅清祥,王晓东编著,我所见过的最好的算法教材)
程序设计导引及在线实践  作者: 李文新
ACM程序设计培训教程 吴昊
基础提高:
算法艺术与信息学竞赛 第二版 刘汝佳
算法设计与分析  王晓东
算法设计与试验题解 王晓东
科曼:《算法导论》
组合数学 第三版 冯舜玺 译
计算几何-算法设计与分析 周培德
国际信息学奥林匹克竞赛指导— — 实用算法的分析与程序设计   吴文虎 王建德
网络算法与复杂性理论  谢政 李建平
《Concrete Mathematics — A Foundation For Computer Science》 Ronald L. Graham , Donald E. Knuth , Oren Patashnik《具体数学》(能买到中文版最好)
《计算机程序设计艺术》三卷  Knuth
组合数学的算法与程序设计
《程序设计中的组合数学》 吴文虎
图论的算法与程序设计
图、网络与算法
国际大学生程序设计竞赛辅导教程  郭嵩山 崔昊
《ACM国际大学生程序设计竞赛试题与解析》全部册(吴文虎著,清华大学出版社)
C算法.第1卷,基础、数据结构、排序和搜索(第三版)
C算法(第2卷图算法第3版中文版)译者:周良忠 (美国)塞奇威克著
国际大学生程序设计竞赛例题解 四本  郭嵩山

Written by apollozhao

2010/11/29 at 10:23