Tag Archives: Algorithm

二分法猜价格策略的C语言实现

之前看书上的一个例程写的程序,不过例程类似于《幸运52》节目中的猜价格,主持人让参与者猜测商品的价格,如果猜测的结果高了,主持人给出高了的提示,低了同理,直至参与者猜出正确的价格。

而本例程并非给出这样的程序,而是给定设定好的价格(假定参与者不知情,只有主持人知道),参与者给出初始价格,根据获知主持人的提示,参与者根据二分法的策略猜测价格,直至才到正确价格停止。

Continue reading

动态规划的精华体现——Floyd算法

今天下午老师讲了图相关算法(Prim和Kruskal两个求最小生成树的,还有Dijkstra,SPFA,Bellman-Ford,Floyd算法等)和内容,其实这么说很不准确,一直从第一天开始就一直在讲图的相关内容,毕竟个人感觉树也是图的一种罢了。下面这个四句话摘自某百度知道:

  • 图——实际上是关系的直观表示;
  • 树——实际上是一种有层次的特殊的关系;
  • 表——实际上是线性关系,可以看作特殊的图(每个节点只和唯一的节点有关系),特殊的树(每个节点只有一个儿子);
  • 他们之间是可以相互转换的,因为复杂度低的数据结构是可以用复杂度高的数据结构表示的

本节做Floyd算法的记录。部分内容来自网络,以及代码在别人的基础上改了不少。

Continue reading

漫谈穷举和枚举的关系和异同

说道枚举,大家可能想到的都是枚举变量,枚举类型。前两天,不知为何就把他的一个好兄弟联想到了一起,他的好兄弟是谁?——哈哈,那就是穷举。

那他们到底有什么关系呢?让我们一言以蔽之:

  • 【枚举】一般是指一种构造类型——枚举(类型)。这个好多人和他等同于穷举(法),但我在写本篇日志的时候,搜索到的很少说枚举法,但也有不少将两者都视为同一种方法。
  • 【穷举】是一种算法,也可以说是一种思想

Continue reading

并查集补充:Ackerman函数及C语言实现(递归方法和非递归方法)

第二天数据结构讲的是并查集,这里是补充并查集的补充内容:Ackerman函数。想看并查集内容,请移步→谈并查集思想——基础入门

【1.Ackerman函数定义】

  • 当两个连续函数都趋于无穷时,我们常用洛必达法则来比较它们趋向无穷的快慢。
  • 函数的阶越高,它趋向无穷的速度就越快。
  • 在定义在正整数域上的函数中,n!趋向于正无穷的速度非常快,所以在算法设计中如果出现这样的时间复杂度就太糟糕了。logn趋向无穷的速度则非常慢。

Continue reading