标题: 算法笔记, 第十日:贪心算法
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-19 13:12 资料 短消息 只看该作者
1、算法是什么呢?
一种说法是,算法是一组明确定义了的以某些值作为输入,某些值作为输出的计算过程
  太抽象了。
其实也就是说,算法是有输入有输出的明确的计算过程
另一种说法是,算法可以看作是用于解决经过明确定义了的可计算问题的工具
该问题陈述了输入与输出间的关系,而算法则将这种关系用特定的计算过程实现出来
有一个问题,我用一段将这个问题的解决方法记录下来,这段话就是一个算法?
不一定!
这个问题有可能是可陈述、可解决但不可计算的
比如说:你爱我吗?
显然这个问题是不可计算的,但是总会有一个解  
开个玩笑。
2、那么,到底算法要解决什么样的问题呢?
一般来说,一个成功的算法都具备两个特征:
挑战性:一个问题可能会有很多的候选解,但是大部分都不是我们想要的,把我们想要的挑出来!(挑三拣四)
有人用:没人用?算法再好又如何?(市侩啊市侩)
3、如何学算法?
我认为,学算法最重要的是学思想,学会如何思考问题。
在我们需要算法实例的时候可以google,难道思想也可以google么?就算google到了,还是要学来才能用。
4、算法不能解决所有的问题
一个问题,或者可以解决,或者不能解决。真的是这样么?
世界不总是二分的。
在算法领域内,有一类问题,至今不能确定是否可以解决。
NP-hard,n的多项式时间内是否可以找到解?
NP-complete,n的多项式时间内是否可以找到所有解?
都是这种问题,我们不知道能不能找到某个可以在可忍受的有限时间内结束的算法。(好绕啊)
5、算法学了有啥用呢?
算法可以解决问题。
就算不能解决问题,它可以帮助你思考。
就算是需要解决的问题在已解决问题领域内找不到任何帮助,多学点儿东西总没坏处的。


推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-19 14:30 资料 文集 短消息 只看该作者
呵呵,我记得有本书上定义是对于任何有效输入都可以在有限步内停机的自动机,更抽象吧


推荐贴
顶部
性别:男-离线 天痕

白衣伯爵中大夫

Rank: 10Rank: 10Rank: 10Rank: 10
组别 白衣卿相
级别 右将军
好贴 4
功绩 224
帖子 1150
精华 1 点
现金 2162 通宝
编号 208
注册 2003-8-29




QUOTE:
原帖由Maxwell于2005-01-19, 14:30:53发表
呵呵,我记得有本书上定义是对于任何有效输入都可以在有限步内停机的自动机,更抽象吧  

这个好像是可计算理论里的有限自动机的可计算性(不要求结束时回到开始处)的定义  

对算法,搞竞赛的有这么个说法:给到题要求40分钟内解决,至少要花20分钟在考虑算法上                  当然过于简单的题不算
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-19 15:34 资料 文集 短消息 只看该作者


QUOTE:
原帖由天痕于2005-01-19, 15:30:15发表
这个好像是可计算理论里的有限自动机的可计算(不要求结束时回到开始处)的定义  

对算法,搞竞赛的有这么个说法:给到题要求40分钟内解决,至少要花20分钟在考虑算法上                  当然过于简单的题不算  

这是在学校图书馆借的一本老书上的定义,书不算很厚,蓝皮,我觉得写的很好,比现在某些算法书强不少。
呵呵,过于简单的题也不会给40分钟。
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-19 15:46 资料 短消息 只看该作者
呵呵,还真有人看啊,坚定了我继续写下去的信心
我现在看的这本书,是the MIT Press出的Introduction to Algorithms
这本书应该是现在比较权威的教材之一了
争取用一到两个月的时间review一下
这本笔记做完,我准备从头再来一遍C++
VC用了好久,还没仔细学习过C++呢
Maxwell到时要多指教啊...
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-19 15:55 资料 文集 短消息 只看该作者
呵呵,客气了,我虽然程序写了不少,可是算法真没仔细研究过,正要跟兄好好学习一下
推荐贴
顶部
性别:男-离线 dollbean

Rank: 4
组别 士兵
级别 裨将军
功绩 3
帖子 304
精华 0 点
现金 2600 通宝
编号 30176
注册 2005-1-13


发表于 2005-1-19 17:06 资料 短消息 只看该作者
算法是程序设计的精髓,好好学习一下
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-20 11:28 资料 短消息 只看该作者
第二日:
1、如何分析一个