iBlog@zihua

--

  • 首页
  • 标签
  • 云空间
  • 原创
  • 分类
  • 归档
  • 关于我

  • 搜索
paxos polarfs codebase ask knowledge chatgpt openai 毕业论文 网络安全 共识 分布式 Raft 科研 设计模式 RPC 高并发 多线程 算法设计 碎片技术 Dobbo 吃的 区块链 参考 练习 语言的艺术 SpringCloud 生活 Spring SpringMVC 算法 antic Java MyBatis 书籍细读 JVM 项目教学 SpringBoot Netty

《计算机算法基础》课程记录

发表于 2019-09-02 | 分类于 大三课程 | 0 | 阅读次数 532

课程介绍

任课教师:李皞(hào),华中科技大学博士,香港城市大学博士后,主要从事智能算法及其在红外光谱、农业信息与环境遥感领域的应用研究,办公室:东 7-505,答疑辅导时间:周四下午。建议提前通过电话、、邮件、QQ联系(电话:暂匿,QQ:暂匿,mail:暂匿)群号:739265561.

2019年9月2日笔记

题目1:

农夫需要把狼、羊、菜和自己运到河对岸去,只有农夫能够划船,而且船比较小,除农夫之外每次只能运一种东西,还有一个棘手问题,就是如果没有农夫看着,羊会偷吃菜,狼会偷吃羊。

请考虑一种方法,让农夫能够安全地安排这些东西和他自己过河。

......

题目2:

你请一个工人为你工作七天,用一根金条作为报酬。金条被分为7小块,可以每天支付一块儿。但是,如果你只能将金条切割两次。

请问你如何切割金条,能满足每天支付一块给工人呢?

(面试过的原题)

可以将金条切两刀,分成3份,1/7份、2/7份和4/7份。

第一天,支付工人1/7的报酬。

第二天,支付2/7并让工人找回1/7。

第三天,支付1/7的金条。

第四天,支付4/7的金条,并收回1/7和2/7份的。

第五天,支付1/7份的金条。

第六天,支付2/7份金条,并收回1/7份的金条。

第七天,支付1/7的金条。

题目3:

有5个外观没有区别的物品,重量各不相同。你只有一个天平。请问:

至少需要用天平称多少次,才能将它们按重量的升序排序?

......

算法实例:最大公约数

问:最大公约数算法,可以怎样实现?

顺序实现(辗转相除法):

int Gcd (int a, int b) {
    int r = 0;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

递归形式:

int Gcd(int a, int b) {
    if(b == 0) return a;
    return Gcd(b, a % b);
}

2019年9月9日笔记

如何证明一个算法可行?

数学归纳法

1、如何证明 "n^3-n" 能被3整除? 证明1

2、证明:前n个奇数之和是一个完全平方数 证明2

3、反驳:所有的马颜色一样?

......

反证法

1、 如何证明"根号二"是无理数?

......

2、如何证明质数的个数有无穷多个?

......

练习

夜过吊桥

问题:晚上有四个人ABCD要过河,过河必须有手电筒,但只有一个手电筒,有一艘船每次能乘两个人,如果结对过河,快的人要迁就慢的人,求最快过河方法。手电筒只能送不能扔。 过桥速度:A:1min B:2min C:5min D:10min

  1. 方法一:贪心算法。每次都让最快的人过。先让最快的AB过,然后由快一点的A将手电筒带回来,再让快一点的AC过,再由A带回来,最后AD过。 花费了2+1+5+1+10=19分钟

  2. 方法二:可以这样考虑:每次两个不同时间的人过河,慢一点的人所需时间减去快一点的人的时间,就是快一点的人浪费的时间。 所以,首先考虑过河(忽略回来的过程),过河要两两搭配(节省时间),一共有四个人,通过遍历找到浪费时间最少的组合,即AB和CD。 然后考虑回来送手电筒的人,因为尽量节省时间,所以首先让AB过河,以便让快的A回来送手电筒,这时,让CD过河,再由B将手电筒送回,AB同时过河。 时间总计:2+1+10+2+2=17分钟

  3. 如果要最快,最少需要5次运输。

  4. 在五次运输中,过河成对,回来单人。人数分别是2 1 2 1 2。

  5. 过河时尽量两两过。

  6. 有三次两个人过,浪费最少时间的搭配是两次AB和一次CD。

  7. 回来时让快的一个人送。

  8. 先让AB过,既是考虑到最少过河时间,也是为了送回时间少(因为有A)。

@子华 wechat
欢迎友联!
Donate comment here.
@子华 微信支付

微信支付

  • 本文作者: @子华
  • 本文链接: https://liuzihua.top/archives/1567425381094
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
蚂蚁金服笔试(个人愚见)
关于网站问题(2019年9月9日12:33:52)
  • 文章目录
  • 站点概览
@子华

@子华

嗯(⊙_⊙)?

66 日志
6 分类
37 标签
RSS
Creative Commons
Links
  • 爱敲代码的猫
  • ?雨苁ℒ?
  • biezhi(魔王不造反)
  • TyCoding
  • 猿码优创
  • 薛勤的博客
  • 阿里中间件团队博客
  • 沐雨的博客
  • 龙哥的博客
  • Quinn Tian's Blog
  • 方志鹏
  • 在线图片工具
  • jenkov(java很全)
  • 小新の窝
  • 游剑辉
  • Bo Zhou
  • STAR 皆空
0%
© 2018 — 2023 鄂ICP备18029580号-1
主题 - NexT.Muse v5.1.4
as we know, there are known knowns; there are things we know we know. We also know there are known unknowns; that is to say we know there are some things we do not know. But there are also unknown unknowns—the ones we don't know we don't know.