Category Archives: 算法之道

数组面试题总结

学习笔记。来自七月算法公开课视频(https://www.julyedu.com/video/play/25/29)。

 
Continue reading

Python 逻辑斯特回归做二分类

最近做的泰坦尼克生还人员预测,这里给出逻辑斯特回归的代码,主要包含两部分(梯度计算和模型的简单评估,其中包括 accuracy , precision , recall , f1 )。同时也可以对梯度计算和预测的函数进行修改,实现多项式的决策边界。

有点遗憾的是,

  1. 没有实现 plot_decision_bondary 函数;
  2. 要修改特征的话有点麻烦,要同时修改梯度计算和预测的函数(懒得改了);
  3. 没有实现随机梯度下降;
  4. 梯度计算的函数想要实现一个最优解,但没有实现,懒得删了=。=

由于原本是类内函数,所以要单独使用的话需要去掉每个函数的第一个参数 self (特别地,在计算梯度时候会调用到 self.sigmoid_function)。

Continue reading

回溯法解决子集和问题代码剖析

和上一篇一样,算法实验课的产物。具体来说应该是搜出来的代码,对代码做简单分析。

【Description】

  • 子集和问题的一个实例为〈S,t〉。其中,S={ 1 x , 2 x ,…, n x }是一个正整数的集合,c是一个正整数。
  • 子集和问题判定是否存在S的一个子集S1,使得 S1中的所有元素之和等于c。试设计一个解子集和问题的回溯法。

Continue reading

多处最优服务次序问题代码剖析

这个是某次算法实验课上的实验内容,老师让我们使用贪心算法来计算这个问题。也是最近在忙别的事情,自己就在网上搜了一篇文章讲这个(多处最优服务次序)的问题(使用贪心算法)。下面是对原本文章代码的剖析(由于很多代码都一样,我也找不到之前是从哪个blog上找的代码了,这里就不给原博文地址了)。

【Description】
设有 n 个顾客同时等待一项服务。顾客 i 需要的服务时间为ti,1≤i≤n。共有 s 处可以提供此项服务。应如何安排 n 个顾客的服务次序才能使平均等待时间达到最小平均等待时间是 n 个顾客等待服务时间的总和除以 n 。

对于给定的 n 个顾客需要的服务时间和 s 的值,计算最优服务次序。 Continue reading

二分法猜价格策略的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