📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: dreamingrobot
跳转到指定楼层
上一主题 下一主题
收起左侧

[入门|算法|数据结构] [HomeWork] Algorithms, Part I (week 1)

 
🔗
littlelab 2015-6-29 12:15:42 | 只看该作者
全局:
a0106660 发表于 2015-6-29 10:56
我的做法就是 参照report,一一修改bug。这样只要成功修改好了,就可以不用提交很多次了

谢谢指点,有些简单的问题可以从report中一次性更正,但是需要动程序结构的改动还是得测试一下才知道新改的对不对,要是有个本地测试的方法就好了。

再次感谢哈!
回复

使用道具 举报

🔗
a0106660 2015-6-29 13:27:08 | 只看该作者
全局:
littlelab 发表于 2015-6-29 12:15
谢谢指点,有些简单的问题可以从report中一次性更正,但是需要动程序结构的改动还是得测试一下才知道新改 ...

其实有JUnit 测试方法,CS61B 2015spring里有类似本地测试的方法,不过貌似只能测试一些挑选出来的单个数据,对于这个练习来说不是很适用https://berkeley-cs61b.github.io ... /lab/lab2/lab2.html
回复

使用道具 举报

🔗
littlelab 2015-6-29 13:50:34 | 只看该作者
全局:
a0106660 发表于 2015-6-29 13:27
其实有JUnit 测试方法,CS61B 2015spring里有类似本地测试的方法,不过貌似只能测试一些挑选出来的单个数 ...

学习了,多谢!
回复

使用道具 举报

🔗
eggburger 2015-6-30 05:21:28 | 只看该作者
全局:

学分
回复

使用道具 举报

🔗
大成若缺 2015-7-4 13:43:22 | 只看该作者
全局:


这个内存通不过。我在Percolation里面定义了一个新的数据类型叫做Site,它包含id和布尔变量open, which indicates if it's open,在Percolation构造函数中创建了一个N*N+1的Site数组,估计这不必要。

另外我想请教一下, 为什么代码风格中禁止用hard tab呢?我觉得这个很方便很利于对齐啊。
回复

使用道具 举报

🔗
a0106660 2015-7-4 23:44:49 | 只看该作者
全局:
大成若缺 发表于 2015-7-4 13:43
这个内存通不过。我在Percolation里面定义了一个新的数据类型叫做Site,它包含id和布尔变量open, which ...

你用布尔矩阵可以不用设ID,更节省空间
回复

使用道具 举报

🔗
大成若缺 2015-7-5 00:30:39 | 只看该作者
全局:
a0106660 发表于 2015-7-4 23:44
你用布尔矩阵可以不用设ID,更节省空间

有道理,数组行不行?会不会比矩阵更省空间?
回复

使用道具 举报

🔗
a0106660 2015-7-5 01:00:40 | 只看该作者
全局:
大成若缺 发表于 2015-7-5 00:30
有道理,数组行不行?会不会比矩阵更省空间?

我口误了。就是数组,矩阵可以映射到数组上的。
回复

使用道具 举报

🔗
wynnforce 2015-7-5 11:28:26 | 只看该作者
全局:
rilegoule.....终于过了bonus test....







解决backwash的两种方法:
1. 一个UF object 控制percolate(),另一个UF object控制isFull()
前者有virtual bottom和virtual top, 后者只有virtual top;
fields:UF object1 (N * N + 2); UF object2 (N * N + 1); boolean array (N * N) 控制isOpen()
2. 一个UF object控制isFull(), percolates()是每次open()的最后做一个DFS找所有unfilled sites,(找到一个fill一个),如果找到深度为N的的说明percolates了.
只有virtual top;
fields: UF obejct (N * N + 1)控制isFull(); boolean array1 (N * N) 控制isOpen(); boolean array2 (N * N)作为isFull的矩阵标记; boolean percolates单一布尔值做percolates与否的标记

只有方法2可以避免backwash的同时通过bonus memory test

为什么方法2可以通过timing test?
因为虽然对某个site来说, open它之后做的DFS最坏需要O(N^2)的时间,但是amortized running time一定是O(1) 的:
证明:
从sites全部blocked开始,进行M次open;每个open()最后都有一个DFS,所以一共是M次DFS;
DFS的时间取决于它经过的sites的个数;
每个DFS经过的sites都会fill掉;
设第i个open()中的DFS,经过了T(i)个sites,那么它一定也fill了T(i)个sites;
DFS只找unfilled sites,所以任意两次DFS fill的sites是没有重叠的,因而前M次fill的总数是它们直接相加: 一共fill了 T(1) + T(2) + ... + T(M)个site
而filled sites的总数不会超过当前open sites的总数,每次只open一个sites,所以第M次open()的最后open sites总数为M; 从而T(1) + T(2) + ... + T(M) ≤ M
这是M次DFS的总和,那平均每次DFS就 ≤ M/M = 1了


故平均每次open花的时间为O(1) (除了union()等UF操作之外)

评分

参与人数 3大米 +13 学分 +1 收起 理由
Simy1130 + 3 回答的很好!
hurricane_e + 1
南方的狼 + 10 回答的很好!

查看全部评分

回复

使用道具 举报

🔗
asd55178608 2015-7-6 12:31:52 | 只看该作者
本楼:
全局:
快due了。。

Screen Shot 2015-07-05 at 9.31.03 PM.png (112.22 KB, 下载次数: 0)

Screen Shot 2015-07-05 at 9.31.03 PM.png
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表