美文网首页
大作业(一)

大作业(一)

作者: Xindolia_Ring | 来源:发表于2019-03-12 10:31 被阅读0次

实验目的与要求:

目的:采用语言的特性来解决计算机工程问题,包括结构的设计与应用、递归和迭代的设计与应用、mapreduce的设计与应用等实验。通过语言特性的应用实验,熟练掌握编程语言的特性及其编程思想,如数据抽象、递归和迭代的设计、分而治之等思想,培养使用不同语言特性解决复杂计算机工程问题,并对结果进行分析的能力

要求:

本实验分为三部分,如下所示

第一部分:结构的设计与应用

请用你熟悉的语言实现一个简易区块链系统, 功能包括查询块长度,插入块,查找块,检查块信息等,请分别用记录结构(如C语言的struct、Java的class等)和不用记录结构实现,并比较(如可读性、可写性、可靠性、效率等)。

提示:

块结构的信息:索引,时间戳,数据,哈希值,前置哈希值(加密)

块的生成:注意首块和其他块的区别

块的存储结构(账本):块链表

检查块:前后索引一致?前后hash值一致?当前hash值正确?

第二部分:递归和迭代的设计与应用

大部分语言都提供了递归与迭代这两种机制,例如,最大公约数的计算可分别用这两种机制来实现:

/* 递归实现 */

int gcd(int a, int b) {

 /* assume a, b > 0 */

 if (a == b) return a;

 else if (a > b) return gcd(a-b, b);

 else return gcd(a, b-a);

}

/* 迭代实现 */

int gcd2(int a, int b) {

 /* assume a, b > 0 */

 while (a != b) {

 if (a > b) a = a-b;

 else b = b-a;

 }

 return a;

}

请用你熟悉的语言分别用递归和迭代这两种机制来设计和解决以下两个问题之一,并对结果进行分析:

  1. 折半查找法:在N个有序数中查找数d。

  2. 台阶问题:楼梯有N阶,上楼可以一步上一价,也可以一次上二阶。请问共有多少种不同的走法。

第三部分:mapreduce的设计与应用

Google处理大规模数据的mapreduce来源于函数语言的map函数和reduce函数,下面是map和reduce的js实现:

/* map的js实现 */

function map (f, inarray) {

 var out = [];

 for(var i = 0; i < inarray.length; i++) {

 out.push( f(inarray[i]) )

 }

 return out;

}

/* reduce的js实现 */

function reduce (f, inarray) {

 if(inarray.length <= 1) return;

 if(inarray.length == 2) return f(inarray[0],inarray[1]);

 r = inarray[0];

 for(var li = 1;li < inarray.length; li++) {

 r = f(r, inarray[li]);

 }

 return r;

}

简单来说,map将函数f分别作用到数组inarray的每个元素上,并返回由这些作用结果组成的新数组,而reduce将函数f分别从左到右地作用到数组inarray的(两个)元素,并返回最后的作用结果,如下列例子所示:

js> map(function(x){return x+1}, [1,2,3,4,5])

[2,3,4,5,6]

js> reduce( function(x,y){return x+y}, [1,2,3,4,5])

15

js> reduce( function(x,y){return x*y}, [1,2,3,4,5])

120 

一、请实现map和reduce函数(建议使用支持函数作为参数的语言,如Haskell、js、python等),并使用map和reduce来

  1. 计算数组的平方和,如[1,2,3,4]的平方和为12+22+32+42。

  2. 统计数组中正数的个数,如[-1,1,0,-2,5]的正数个数为2。

  3. 展平数组的数组,如[[1,2],[3,4,5],[6]]展平后为[1,2,3,4,5,6]。

二、现实世界中数据可能有各种不同的结构,二叉树是其中常用的一种结构。请设计能够处理二叉树数据的maptree和reducetree。

  1. 请实现maptree和reducetree

  2. 请使用maptree和reducetree为下列通讯录加上区号,并统计深圳电话的个数

Record(
            Data(N:小明,A:深圳,T:26530001)
            Record(
                        Data(N:小王,A:广州,T:26530002)
                        Record(
                                     Data(N:小丽,A:深圳,T:26530003)
                                     Data(N:小红,A:北京,T:26530004)
                         )
            )
)

提示:假设有树结构的抽象数据类型:

data Tree type = Leaf type | Node (Tree type) (Tree type)

maptree f(x){return x+1} (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3))

= (Node (Node (Leaf 2) (Leaf 3)) (Leaf 4))

reducetree f(x,y){return x+y} (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3))

= (1+2)+3 = 6

相关文章

  • 大美营作业一

    1.昵称:自信到分分钟想爆炸的舒艳 2.不自信事件 a.因病错过高考,没有上大学。 b.债务危机,负债太多 c.没...

  • 大目标作业

    一、我的理想状态 工作有成就感还能有不错的收入,能保证有高效陪孩子的时间,而不是加班多压力大到完全没心思管孩子。 ...

  • 作业:大表白

    俊榆妈,我喜欢你的灵动,喜欢你的点子多,喜欢你备课的认真,尽最大的努力来为我们提供最好的课程,让大家迅速提升,喜欢...

  • 大驰作业

    查阅下面的诡辩常用伎俩,用逻辑学三大定律,去归类,犯了哪些错误? 同一律 对象 概念 判断 同一个 矛盾律 必有一...

  • 大C-模块一作业

    1.针对最近的爆款文《就算老公一毛钱股份都没拿到,在我心里,他依然是最牛逼的创业者》,用不超过三句,说说要不要抓热...

  • KJEssay客户反馈【48期】

    客户反馈 大论文、小测试、大测试、小论文、作业、小组作业等一系列不论是啥的作业,都请找KJE。没什么,就是能这么强...

  • 关于作业三大定律!!

    作业三大定律: 第一定律: 你写数学作业, 其他作业写不完, 第二定律: 你写其他作业, 数学作业你写不完, 第三...

  • 【周末复盘】我的周复盘

    一、家庭作业 周一17:00完成作业 周二大约21:00完成作业 周三19:49完成作业(本来可以在18:40完成...

  • 超级二班的奇闻趣事

    “你,语文作业抄完没有?” “你,地理作业抄完没有?” 一大早,一群同学围着笨笨要作业。笨...

  • 三大特性作业

网友评论

      本文标题:大作业(一)

      本文链接:https://www.haomeiwen.com/subject/dshgpqtx.html