一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5078|回复: 65
收起左侧

UC Berkeley CS61B Homework 10

  [复制链接] |试试Instant~ |关注本帖
逃亡~ 发表于 2014-10-17 08:41:48 | 显示全部楼层 |阅读模式

[其他]CS61B Data Structures(in Java) #1 - 2014-10-16@UC Berkeley

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 逃亡~ 于 2014-10-17 08:45 编辑

CS61b的最后一次作业,终于把61b修完了!

这次作业也比较简单,但是依然难以理解+_+,可能是我英语不太好的缘故=。=。

这次作业是实现 Counting Sort 和 Radix Sort,input是一组整数,是16进制的,integer在java里面是占32个bits,如果以16进制表示的话,一共有8位(每4个bits表示一位16进制数,比如FFFFFFFF)。assume input全部是正数,对input进行radix sort,所以总共进行了8次每一次的 radix sort 用 counting sort 来实现。

下面是输出,一组是16进制的,一组的10进制的。yell方法我稍微改动了一下。
1.png 2.png

评分

1

查看全部评分

yingy4 发表于 2016-5-28 15:32:19 | 显示全部楼层
很巧妙的方法,把输出改了下可以看到每一次的结果:
hw10.png
回复 支持 1 反对 0

使用道具 举报

Chris1993 发表于 2016-5-10 17:52:01 | 显示全部楼层
一个小细节写错,对着counting sort的教程debug了好久
Screen Shot 2016-05-10 at 5.51.24 PM.png

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

imposiwind 发表于 2014-11-27 19:41:20 | 显示全部楼层
最后一次作业,从counting sort 到radix sort,按照lecture 所讲转化成代码即可。
实现counting sort时,注意在item哈希表x中,key就是截取出来的某一位,value就是原本的一长串数字。



我终于完成了cs61b!


Party time!!!!!!!

radix_result

radix_result

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

wtttt0 发表于 2014-11-28 04:10:22 | 显示全部楼层
回复 支持 反对

使用道具 举报

831128 发表于 2014-12-2 08:06:18 | 显示全部楼层
CS61B搞定,求学分
QQ截图20141201154527.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

18258170717 发表于 2014-12-9 23:57:51 | 显示全部楼层
交作业,发现lecture里面radix sort讲的不是很清楚,所以一开始弄错了一点。写下给后来人做点参考。radix sort原理是:将十进制的整数转化为16进制的整数(当然题目中是反过来输入,都差不多),其好处在于,16进制的整数可以利用(&15)取出最低4位,第二低四位,一直到最高四位进行countingSort(bucket number 和 新产生的小于16的数range比较符合,可以进行countingSort),注意countingSort传回的int[]数组不是那个4位的数组,而是原先传进去的keys[]拷贝后的数组(因为4位产生的数组传回去没有意义,需要将原先的数组的拷贝数组传回去,因为keys不能改变),然后迭代地进行8次,根据stable性质(每次低位排序后,若其高位相同,则在高位的排序中这两个数字位置关系保持不变)即可得到排序后的数组。

HW10

HW10

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

jzc007 发表于 2015-1-3 16:50:15 | 显示全部楼层
终于搞完cs61b了。。泪流满面
Screen Shot 2015-01-03 at 12.49.31 AM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bruce2045 发表于 2015-1-10 08:20:05 | 显示全部楼层
终于完成了cs61b!!好鸡冻!!
hw10.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zj45499 发表于 2015-1-24 16:25:03 | 显示全部楼层
回复 支持 反对

使用道具 举报

urekuk 发表于 2015-3-14 12:14:58 | 显示全部楼层
回复 支持 反对

使用道具 举报

neverdies 发表于 2015-4-17 09:23:14 | 显示全部楼层
还有一次hash table
HW10.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sicilianee 发表于 2015-5-30 12:25:57 | 显示全部楼层
Need to create and maintain multiple arrays, if you don't use hashtable.
keys[keys.length] --> targets[keys.length] --> buckets[16] --> scan[16] --> output[keys.length]
Sort from least significant to most significant.
hw10.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

caffery24 发表于 2015-6-4 11:45:05 | 显示全部楼层
想问下,keys数组输入是按16进制输入,但是会自动转换成10进制,这种情况,怎么提取它的某一位十六进制呢???而且数字长短是不一样的啊
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-6-4 15:03:44 | 显示全部楼层
caffery24 发表于 2015-6-4 11:45
想问下,keys数组输入是按16进制输入,但是会自动转换成10进制,这种情况,怎么提取它的某一位十六进制呢? ...

在机器里都是按二进制存储的,直接从低四位开始截取,keys & 15。然后可以用移位运算符移位来截取其它位。
回复 支持 反对

使用道具 举报

caffery24 发表于 2015-6-4 17:04:27 | 显示全部楼层
jy_121 发表于 2015-6-4 15:03
在机器里都是按二进制存储的,直接从低四位开始截取,keys & 15。然后可以用移位运算符移位来截取其它位 ...

谢谢你啊,把问题提出来自己就想通了。。。开始看错数据了,老感觉取得数字不对
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-6-5 12:52:54 | 显示全部楼层
Homework10 Done。接下来复习下61B的Homework。
Homework10.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

enirinth 发表于 2015-6-19 18:11:30 | 显示全部楼层
作业:

1111.jpg


老师介绍了两种counting sort;一种是单纯的整数key,一种是entry(key和associated value);
这一题乍看都是整数,似乎用前一种方法;实际上应该用后者:key是digit,associated value是整数本身;
然后套用后者的方法即可;

————————————
61B终于写完了,还剩14年的lab15是复习final的,懒得做了。。。以及PJ2和PJ3,看心情做吧。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ypandxy 发表于 2015-7-3 21:38:43 | 显示全部楼层
啦啦啦,做完啦~~
homework10.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

豆小凡 发表于 2015-7-29 12:16:04 | 显示全部楼层
终于把十次作业做完,还有pj3和两个lecture没看,anyway,这门课也算几乎攻下来了。最后求加分啦~
counting sort & radix sort.png
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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