• 关于

    计算算法可以做什么

    的搜索结果

问题

推荐引擎的离线算法和在线算法初探

福利达人 2019-12-01 21:21:15 2707 浏览量 回答数 0

问题

【直播回顾】21天搭建推荐系统:实现“千人千面”个性化推荐(含视频)

小柒2012 2019-12-01 21:21:27 7489 浏览量 回答数 1

回答

“程序设计 = 算法 + 数据结构”是瑞士计算机科学家Niklaus Wirth于1976年出版的一本书的书名,很快就成了在计算机工作者之间流传的一句名言。斗转星移,尽管新技术方法不断涌现,这句名言依然焕发着无限的生命力,它借助面向对象知识的普及,使数据结构技术更加完善和易于使用。由此,也说明了数据结构在计算机学科中的地位和不可替代的独特作用。 然而,在可视化程序设计的今天,借助于集成开发环境我们可以很方便、快捷地开发部署应用程序,程序设计似乎不再只是计算机专业的人员的专利,很多人以为,只要掌握了几种开发工具就可以成为编程高手了,其实这是一个误区。纵然,我们可以很熟练地掌握一门程序设计语言、熟练地运用各种IDE开发应用程序,但是我们写出的代码是否是优良的。我们的设计是否合理。代码执行是否是高效的。代码风格是否是有美感的。更甚的说我们所写出代码的是否是艺术。 在长达几年的时间内,我总是陷在了一个误区里面:即认为工程能力和算法能力是不相干的两回事,我们似乎可以很轻松地完成一个工程项目,至少我在做一些MIS系统的时候一直都是这么认为的,甚至觉得根本不需要所谓的算法或数据结构。当时一直想不通的是为什么Google、百度这样牛的公司却对ACMer们如此青睐,对于这种招聘的标准感到疑惑不解。为什么他们不在技术(多线程、网络编程、分布式系统等)上做要求,却偏偏只关注这么一小块的算法设计。 我曾经反复地告诉自己“程序设计 = 算法 + 数据结构”在70年代提出是受限于计算机硬件,当时的内存不足、计算能力不强,程序需要设计足够精巧细致。再看当前主流的计算机配置,比70年代的大型机运算能力还要强大,我们好像完全不用担心算法设计的问题。报着这样的想法,我向来都不太重视算法,而且工程中对算法的需求并不多。 只是有一天,我突然发现我只是片面地关注其中一个方面,硬件能力是提升了,但同时人们所面对的信息、数据、运算任务的规模也是极大的膨胀了,而且膨胀的规模比硬件本身运算能力提升的规模还要大很多。算法和数据结构不仅没有贬值,反而比之前那个时代显得更为重要。试想,在互联网迅猛发展的今天,一个中等规模的企业每天所产生的数据量能达到GB级甚至TB级。要处理这样的海量数据不是说单纯的硬件运算能力上来就解决了的,设计优良的算法和数据结构设计能够在1分钟之内完成任务,而一个糟糕的设计则可能需要1个小时的运行。 一般认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的,这种对数据元素间逻辑关系的描述称为数据结构。许多大型系统的构造经验表明,系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候,确定了数据结构后,算法就容易得到了。当然,有些情况下事情也会反过来,我们根据特定算法来选择数据结构与之适应。算法则可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤,或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。 总的来说,数据结构和算法并不是一门教你编程的课,它们可以脱离任何的计算机程序设计语言,而只需要从抽象意义上去概括描述。说的简单一点,数据结构是一门告诉你数据在计算机里如何组织的课程,而算法是一门告诉你数据在计算机里如何运算的课程,前者是结构学、后者是数学。程序设计就像盖房子,数据结构是砖、瓦,而算法则是设计图纸。你若想盖房子首先必须要有原材料(数据结构),但这些原材料并不能自动地盖起你想要的房子,你必须按照设计图纸(算法)一砖一瓦地去砌,这样你才能拥有你想要的房子。数据结构是程序设计这座大厦的基础,没有基础,无论设计有多么高明,这座大厦不可能建造起来。算法则是程序设计之灵魂,它是程序设计的思想所在,没有灵魂没有思想那不叫程序,只是一堆杂乱无章的符号而已。在程序设计中,数据结构就像物质,而算法则是意识,这在哲学上可以理解为:意识是依赖与物质而存在的,物质是由意识而发展的。双方相互依赖,缺一不可。 当然最经典的数据结构是有限的,包括线性表、栈、队列、串、数组、二叉树、树、图、查找表等,而算法则是琳琅满目的,多种多样的。就好像数据结构是人体的各种组织、器官,算法则是人的思想。你可以用自己的思想去支配你的身体各个可以运动的器官随意运动。如果你想吃苹果,你可以削皮吃,可以带皮吃,只要你愿意,甚至你可以不洗就吃。但无论如何,你的器官还是你的器官,就那么几样,目的只有一个就是吃苹果,而方式却是随心所欲的。这就是算法的灵活性、不固定性。因此可以这样说:数据结构是死的,而算法是活的。 我花了四年时间才走出这个误区,值得庆幸的是不算太晚,而我的梦想是要做一名优秀的架构师,缺乏数据结构和算法的深厚功底,很难设计出高水平的具有专业水准的架构和应用,数据结构和算法则是我实现梦想最坚实的基石。现在,也正是我需要开始沉淀的时刻。程序设计这项伟大的工程,教授于我的将不仅仅是技术这么简单,我期待它能给我以更深的思考与感悟,激发我对生命的热爱,对理想的执着,对卓越的追求。

琴瑟 2019-12-02 01:22:02 0 浏览量 回答数 0

阿里云试用中心,为您提供0门槛上云实践机会!

0元试用32+款产品,最高免费12个月!拨打95187-1,咨询专业上云建议!

回答

  算法,数据结构是关键,另外还有组合数学,特别是集合与图论,概率论也重要。推荐买一本《算法导论》,那本书行,看起来超爽。。。基本掌握语法还不行啊,语法的超熟练掌握,不然出了错误很难调试的。。。最重要的是超牛皮的头脑啦,分析能力,逻辑推理能力很重要。ACM很好玩啦,祝你成功。。。   acm是3人一组的,以学校为单位报名的,也就是说要得到学校同意,还要有2个一起搞的。其实可能是你不知道你们学校搞acm的地方,建议你好好询问下你们学校管科技创新方面的人。建议你找几个兴趣相同的一起做,互相探讨效果好多了,团队合作也是acm要求的3大能力之一。   数据结构远远不够的,建议你看算法导论,黑书,oj的话个人觉得还是poj好,有水题有好题,而且做的人多,要解题报告什么的也好找。我们就是一些做acm的学生一起搞,也没老师,这样肯定能行的。   基础的话是语言,然后数据结构,然后算法。   ACM有三个方向:算法,数学,实现   要求三种能力:英文,自学,团队协作   简单的说,你要能读懂英文的题意描述,要有一门acm能使用的编程语言,要会数据结构,有一点数学基础,一点编程方面天赋,要有兴趣和毅力(最重要),就具有做ACM的基本条件了。   做acm我推荐c,c++也可以,java在某些情况下好用,但是大多数情况的效率和代码量都不大好,所以建议主用c++,有些题目用java   还有什么问题,可以问我啊。   不好意思,没见过用java描述的acm书籍,大多数是用伪命令,其他有的用的c,c++,老一些的用pascal。java只是用来做高精度的一些题的,个人觉得不用专门看这方面的书,java的基本部分学好就够用了。所以我还是推荐主用c++,在高精度和个别题再用java。你可以找找java描述的算法设计与分析,这个好像有   数据结构:C语言版 清华大学出版社 严蔚敏 《数据结构》   算法:清华大学出版社 王晓东 《算法设计与分析》   麻省理工大学 中译本:机械工业出版社 《算法导论》   基本上这三本书就已经足够了,建议一般水平的人先不要看算法导论,待另外两本书看的差不多的时候,再看算法导论加深理解。   另外还有很多针对性更强的书籍,不过针对性太强,这里就不多介绍了。   以上一些都是些算法方面的书,最好的方式就是做题与看书相结合,很多在线做题的网站,PKU,ZOJ很多,推荐PKU,题目比较多,参与的人比较多。做一段时间的题,然后看书,研究算法,再做题,这样进步比较快。   还有关于ACM竞赛,我有自己的一点话说。   首先说下ACM/ICPC是个团队项目,最后的参赛名额是按照学校为单位的,所以找到志同道合的队友和学校的支持是很重要的。   刚刚接触信息学领域的同学往往存在很多困惑,不知道从何入手学习,在这篇文章里,我希望能将自己不多的经验与大家分享,希望对各位有所帮助。   一、语言是最重要的基本功   无论侧重于什么方面,只要是通过计算机程序去最终实现的竞赛,语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA,众所周知,作为面向对象的王牌语言,JAVA在大型工程的组织与安全性方面有着自己独特的优势,但是对于信息学比赛的具体场合,JAVA则显得不那么合适,它对于输入输出流的操作相比于C++要繁杂很多,更为重要的是JAVA程序的运行速度要比C++慢10倍以上,而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽,这无疑对算法设计提出了更高的要求,是相当不利的。其实,笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维,因为对于小程序来说这不旦需要花费更多的时间去编写代码,也会降低程序的执行效率。   接着说C和C++。许多现在参加讲座的同学还在上大一,C的基础知识刚刚学完,还没有接触过C++,其实在赛场上使用纯C的选手还是大有人在的,它们主要是看重了纯C在效率上的优势,所以这部分同学如果时间有限,并不需要急着去学习新的语言,只要提高了自己在算法设计上的造诣,纯C一样能发挥巨大的威力。   而C++相对于C,在输入输出流上的封装大大方便了我们的操作,同时降低了出错的可能性,并且能够很好地实现标准流与文件流的切换,方便了调试的工作。如果有些同学比较在意这点,可以尝试C和C++的混编,毕竟仅仅学习C++的流操作还是不花什么时间的。   C++的另一个支持来源于标准模版库(STL),库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度,这可以节省一些时间。但是,与此相对的,使用STL要在效率上做出一些牺牲,对于输入规模很大的题目,有时候必须放弃STL,这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法;另外,熟练和恰当地使用STL必须经过一定时间的积累,准确地了解各种操作的时间复杂度,切忌对STL中不熟悉的部分滥用,因为这其中蕴涵着许多初学者不易发现的陷阱。   通过以上的分析,我们可以看出仅就信息学竞赛而言,对语言的掌握并不要求十分全面,但是对于经常用到的部分,必须十分熟练,不允许有半点不清楚的地方,下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍,都有可能酿成错误:   在去年清华的赛区上,有一个队在做F题的时候使用了cout和printf的混合输出,由于一个带缓冲一个不带,所以输出一长就混乱了。只是因为当时judge team中负责F题的人眼睛尖,看出答案没错只是顺序不对(答案有一页多,是所有题目中最长的一个输出),又看了看程序发现只是输出问题就给了个Presentation error(格式错)。如果审题的人不是这样而是直接给一个 Wrong Answer,相信这个队是很难查到自己错在什么地方的。   现在我们转入第二个方面的讨论,基础学科知识的积累。   二、以数学为主的基础知识十分重要   虽然被定性为程序设计竞赛,但是参赛选手所遇到的问题更多的是没有解决问题的思路,而不是有了思路却死活不能实现,这就是平时积累的基础知识不够。今年World Final的总冠军是波兰华沙大学,其成员出自于数学系而非计算机系,这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学,此外对于物理、电路等等也可能有一定应用,但是不多。因此,大一的同学也不必为自己还没学数据结构而感到不知从何入手提高,把数学捡起来吧。下面我来谈谈在竞赛中应用的数学的主要分支。   1、离散数学——作为计算机学科的基础,离散数学是竞赛中涉及最多的数学分支,其重中之重又在于图论和组合数学,尤其是图论。   图论之所以运用最多是因为它的变化最多,而且可以轻易地结合基本数据结构和许多算法的基本思想,较多用到的知识包括连通性判断、DFS和BFS,关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大,但是往往也是竞赛中的难题所在,如果有初学者对于这部分的某些具体内容暂时感到力不从心,也不必着急,可以慢慢积累。   竞赛中设计的组合计数问题大都需要用组合数学来解决,组合数学中的知识相比于图论要简单一些,很多知识对于小学上过奥校的同学来说已经十分熟悉,但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现,但是如果积累不够,任何一道这方面的题目却都有可能成为难题。   2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决,这部分在竞赛中的比重并不大,但只要来上一道,也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现,在运用密码学常识确定大概的过程之后,核心算法往往要涉及数论的内容。   3、计算几何——计算几何相比于其它部分来说是比较独立的,就是说它和其它的知识点很少有过多的结合,较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大,但也永远不会成为最弱的题。   4、线性代数——对线性代数的应用都是围绕矩阵展开的,一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。   5、概率论——竞赛是以黑箱来判卷的,这就是说你几乎不能动使用概率算法的念头,但这也并不是说概率就没有用。关于这一点,只有通过一定的练习才能体会。   6、初等数学与解析几何——这主要就是中学的知识了,用的不多,但是至少比高等数学多,我觉得熟悉一下数学手册上的相关内容,至少要知道在哪儿能查到,还是必要的。   7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道,但是一些题目的叙述背景往往需要和这部分有一定联系,掌握得牢固一些总归没有坏处。   以上就是竞赛所涉及的数学领域,可以说范围是相当广的。我认识的许多人去搞信息学的竞赛就是为了逼着自己多学一点数学,因为数学是一切一切的基础。   三、数据结构与算法是真正的核心   虽然数学十分十分重要,但是如果让三个只会数学的人参加比赛,我相信多数情况下会比三个只会数据结构与算法的人得到更为悲惨的结局。   先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的,至于树,我个人觉得需要建树的问题有但是并不多。(但是树往往是很重要的分析工具)除此之外,排序和查找并不需要对所有方式都能很熟练的掌握,但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度,就又该说说哈希表了,竞赛时对时间的限制远远多于对空间的限制,这要求大家尽快掌握“以空间换时间”的原则策略,能用哈希表来存储的数据一定不要到时候再去查找,如果实在不能建哈希表,再看看能否建二叉查找树等等——这都是争取时间的策略,掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。   接着说说算法。算法中最基本和常用的是搜索,主要是回溯和分支限界法的使用。这里要说的是,有些初学者在学习这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。   常用算法中的另一类是以“相似或相同子问题”为核心的,包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划,如何抽象出重复的子问题是很多题目的难点所在,笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法(比如Floyd-Warshall算法),并且多阅读一些定理的证明,这虽然不能有什么直接的帮助,但是长期坚持就会对思维很有帮助。   四、团队配合   通过以上的介绍大家也可以看出,信息学竞赛对于知识面覆盖的非常广,想凭一己之力全部消化这些东西实在是相当困难的,这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间,具体的情况因成员的组成不同而不同,这里我就不再多说了。   五、练习、练习、再练习   知识的积累固然重要,但是信息学终究不是看出来的,而是练出来的,这是多少前人最深的一点体会,只有通过具体题目的分析和实践,才能真正掌握数学的使用和算法的应用,并在不断的练习中增加编程经验和技巧,提高对时间复杂度的感性认识,优化时间的分配,加强团队的配合。总之,在这里光有纸上谈兵是绝对不行的,必须要通过实战来锻炼自己。   大家一定要问,我们去哪里找题做,又如何检验程序是否正确呢。这大可不必担心,现在已经有了很多网上做题的站点,这些站点提供了大量的题库并支持在线判卷,你只需要把程序源码提交上去,马上就可以知道自己的程序是否正确,运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点,笔者不建议大家在所有这些站点上做题,选择一个就可以了,因为每个站点的题都有一定的难易比例,系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。   1、Ural:   Ural是中国学生对俄罗斯的Ural州立大学的简称 ,那里设立了一个Ural Online Problem Set,并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强,得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计,Ural的题目类型大概呈如下的分布:   题型   搜索   动态规划   贪心   构造   图论   计算几何   纯数学问题   数据结构   其它   所占比例   约10%   约15%   约5%   约5%   约10%   约5%   约20%   约5%   约25%   这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。   2、UVA:   UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ,并且支持ONLINE JUDGE,形式和Ural大学的题库类似。不过和Ural不同的是,UVA题目多的多,而且比较杂,而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从,要么难以找到合适的题目,要么Wrong Answer了很多次以后仍然不知道错在那里。 如果说做Ural题目主要是为了训练算法,那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛,因此那里强人无数,不过你先要使自己具有听懂他们在说什么的素质:)   3、ZOJ:   ZOJ是浙江大学建立的ONLINE JUDGE,是中国大学建立的第一个同类站点,也是最好和人气最高的一个,笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站,但是这里的中国学生比较多,因此让人觉得很亲切。这里目前有500多道题目,难易分配适中,且涵盖了各大洲的题目类型并配有索引,除此之外,ZOJ的JUDGE系统是几个网站中表现得比较好的一个,很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛,只要是注册的用户都可以参加。   说起中国的ONLINE JUDGE,去年才开始参加ACM竞赛的北京大学现在也建立了自己的提交系统;而我们学校也是去年开始参加比赛,现在也有可能推出自己的提交系统,如果能够做成,到时候大家就可以去上面做题了。同类网站的飞速发展标志着有越来越多的同学有兴趣进入信息学的领域探索,这是一件好事,同时也意味着更激烈的竞争。

小旋风柴进 2019-12-02 01:20:20 0 浏览量 回答数 0

回答

学计算机的算法很重要的大哥,可以说你只会c语言可以,但是你不会算法就靠边儿。做程序设计语言什么的都是小问题,不会算法没有人会雇用你的哦。

小旋风柴进 2019-12-02 01:20:04 0 浏览量 回答数 0

问题

阿里云校招对应届生基本要求是啥?

琛琛轴子 2020-09-06 21:15:09 11 浏览量 回答数 0

回答

HTTPS基本原理 一、http为什么不安全。 http协议没有任何的加密以及身份验证的机制,非常容易遭遇窃听、劫持、篡改,因此会造成个人隐私泄露,恶意的流量劫持等严重的安全问题。 国外很多网站都支持了全站https,国内方面目前百度已经在年初完成了搜索的全站https,其他大型的网站也在跟进中,百度最先完成全站https的最大原因就是百度作为国内最大的流量入口,劫持也必然是首当其冲的,造成的有形的和无形的损失也就越大。关于流量劫持问题,我在另一篇文章中也有提到,基本上是互联网企业的共同难题,https也是目前公认的比较好的解决方法。但是https也会带来很多性能以及访问速度上的牺牲,很多互联网公司在做大的时候都会遇到这个问题:https成本高,速度又慢,规模小的时候在涉及到登录和交易用上就够了,做大以后遇到信息泄露和劫持,想整体换,代价又很高。 2、https如何保证安全 要解决上面的问题,就要引入加密以及身份验证的机制。 这时我们引入了非对称加密的概念,我们知道非对称加密如果是公钥加密的数据私钥才能解密,所以我只要把公钥发给你,你就可以用这个公钥来加密未来我们进行数据交换的秘钥,发给我时,即使中间的人截取了信息,也无法解密,因为私钥在我这里,只有我才能解密,我拿到你的信息后用私钥解密后拿到加密数据用的对称秘钥,通过这个对称密钥来进行后续的数据加密。除此之外,非对称加密可以很好的管理秘钥,保证每次数据加密的对称密钥都是不相同的。 但是这样似乎还不够,如果中间人在收到我的给你公钥后并没有发给你,而是自己伪造了一个公钥发给你,这是你把对称密钥用这个公钥加密发回经过中间人,他可以用私钥解密并拿到对称密钥,此时他在把此对称密钥用我的公钥加密发回给我,这样中间人就拿到了对称密钥,可以解密传输的数据了。为了解决此问题,我们引入了数字证书的概念。我首先生成公私钥,将公钥提供给相关机构(CA),CA将公钥放入数字证书并将数字证书颁布给我,此时我就不是简单的把公钥给你,而是给你一个数字证书,数字证书中加入了一些数字签名的机制,保证了数字证书一定是我给你的。 所以综合以上三点: 非对称加密算法(公钥和私钥)交换秘钥 + 数字证书验证身份(验证公钥是否是伪造的) + 利用秘钥对称加密算法加密数据 = 安全 3、https协议简介 为什么是协议简介呢。因为https涉及的东西实在太多了,尤其是一些加密算法,非常的复杂,对于这些算法面的东西就不去深入研究了,这部分仅仅是梳理一下一些关于https最基本的原理,为后面分解https的连接建立以及https优化等内容打下理论基础。 3.1 对称加密算法 对称加密是指加密和解密使用相同密钥的加密算法。它要求发送方和接收方在安全通信之前,商定一个密钥。对称算法的安全性依赖于密钥,泄漏密钥就意味着任何人都可以对他们发送或接收的消息解密,所以密钥的保密性对通信至关重要。 对称加密又分为两种模式:流加密和分组加密。 流加密是将消息作为位流对待,并且使用数学函数分别作用在每一个位上,使用流加密时,每加密一次,相同的明文位会转换成不同的密文位。流加密使用了密钥流生成器,它生成的位流与明文位进行异或,从而生成密文。现在常用的就是RC4,不过RC4已经不再安全,微软也建议网络尽量不要使用RC4流加密。 分组加密是将消息划分为若干位分组,这些分组随后会通过数学函数进行处理,每次一个分组。假设需要加密发生给对端的消息,并且使用的是64位的分组密码,此时如果消息长度为640位,就会被划分成10个64位的分组,每个分组都用一系列数学公式公式进行处理,最后得到10个加密文本分组。然后,将这条密文消息发送给对端。对端必须拥有相同的分组密码,以相反的顺序对10个密文分组使用前面的算法解密,最终得到明文的消息。比较常用的分组加密算法有DES、3DES、AES。其中DES是比较老的加密算法,现在已经被证明不安全。而3DES是一个过渡的加密算法,相当于在DES基础上进行三重运算来提高安全性,但其本质上还是和DES算法一致。而AES是DES算法的替代算法,是现在最安全的对称加密算法之一。分组加密算法除了算法本身外还存在很多种不同的运算方式,比如ECB、CBC、CFB、OFB、CTR等,这些不同的模式可能只针对特定功能的环境中有效,所以要了解各种不同的模式以及每种模式的用途。这个部分后面的文章中会详细讲。 对称加密算法的优、缺点: 优点:算法公开、计算量小、加密速度快、加密效率高。 缺点:(1)交易双方都使用同样钥匙,安全性得不到保证; (2)每对用户每次使用对称加密算法时,都需要使用其他人不知道的惟一钥匙,这会使得发收信双方所拥有的钥匙数量呈几何级数增长,密钥管理成为用户的负担。 (3)能提供机密性,但是不能提供验证和不可否认性。 3.2 非对称加密算法 在非对称密钥交换算法出现以前,对称加密一个很大的问题就是不知道如何安全生成和保管密钥。非对称密钥交换过程主要就是为了解决这个问题,使得对称密钥的生成和使用更加安全。 密钥交换算法本身非常复杂,密钥交换过程涉及到随机数生成,模指数运算,空白补齐,加密,签名等操作。 常见的密钥交换算法有RSA,ECDHE,DH,DHE等算法。涉及到比较复杂的数学问题,下面就简单介绍下最经典的RSA算法。RSA:算法实现简单,诞生于1977年,历史悠久,经过了长时间的破解测试,安全性高。缺点就是需要比较大的素数也就是质数(目前常用的是2048位)来保证安全强度,很消耗CPU运算资源。RSA是目前唯一一个既能用于密钥交换又能用于证书签名的算法。我觉得RSA可以算是最经典的非对称加密算法了,虽然算法本身都是数学的东西,但是作为最经典的算法,我自己也花了点时间对算法进行了研究,后面会详细介绍。 非对称加密相比对称加密更加安全,但也存在两个明显缺点: 1,CPU计算资源消耗非常大。一次完全TLS握手,密钥交换时的非对称解密计算量占整个握手过程的90%以上。而对称加密的计算量只相当于非对称加密的0.1%,如果应用层数据也使用非对称加解密,性能开销太大,无法承受。 2,非对称加密算法对加密内容的长度有限制,不能超过公钥长度。比如现在常用的公钥长度是2048位,意味着待加密内容不能超过256个字节。 所以公钥加密(极端消耗CPU资源)目前只能用来作密钥交换或者内容签名,不适合用来做应用层传输内容的加解密。 3.3 身份认证 https协议中身份认证的部分是由数字证书来完成的,证书由公钥、证书主体、数字签名等内容组成,在客户端发起SSL请求后,服务端会将数字证书发给客户端,客户端会对证书进行验证(验证查看这张证书是否是伪造的。也就是公钥是否是伪造的),并获取用于秘钥交换的非对称密钥(获取公钥)。 数字证书有两个作用: 1,身份授权。确保浏览器访问的网站是经过CA验证的可信任的网站。 2,分发公钥。每个数字证书都包含了注册者生成的公钥(验证确保是合法的,非伪造的公钥)。在SSL握手时会通过certificate消息传输给客户端。 申请一个受信任的数字证书通常有如下流程: 1,终端实体(可以是一个终端硬件或者网站)生成公私钥和证书请求。 2,RA(证书注册及审核机构)检查实体的合法性。如果个人或者小网站,这一步不是必须的。 3,CA(证书签发机构)签发证书,发送给申请者。 4,证书更新到repository(负责数字证书及CRL内容存储和分发),终端后续从repository更新证书,查询证书状态等。 数字证书验证: 申请者拿到CA的证书并部署在网站服务器端,那浏览器发起握手接收到证书后,如何确认这个证书就是CA签发的呢。怎样避免第三方伪造这个证书。答案就是数字签名(digital signature)。数字签名是证书的防伪标签,目前使用最广泛的SHA-RSA(SHA用于哈希算法,RSA用于非对称加密算法)数字签名的制作和验证过程如下: 1,数字签名的签发。首先是使用哈希函数对待签名内容进行安全哈希,生成消息摘要,然后使用CA自己的私钥对消息摘要进行加密。 2,数字签名的校验。使用CA的公钥解密签名,然后使用相同的签名函数对待签名证书内容进行签名并和服务端数字签名里的签名内容进行比较,如果相同就认为校验成功。 需要注意的是: 1)数字签名签发和校验使用的密钥对是CA自己的公私密钥,跟证书申请者提交的公钥没有关系。 2)数字签名的签发过程跟公钥加密的过程刚好相反,即是用私钥加密,公钥解密。 3)现在大的CA都会有证书链,证书链的好处一是安全,保持根CA的私钥离线使用。第二个好处是方便部署和撤销,即如果证书出现问题,只需要撤销相应级别的证书,根证书依然安全。 4)根CA证书都是自签名,即用自己的公钥和私钥完成了签名的制作和验证。而证书链上的证书签名都是使用上一级证书的密钥对完成签名和验证的。 5)怎样获取根CA和多级CA的密钥对。它们是否可信。当然可信,因为这些厂商跟浏览器和操作系统都有合作,它们的公钥都默认装到了浏览器或者操作系统环境里。 3.4 数据完整性验证 数据传输过程中的完整性使用MAC算法来保证。为了避免网络中传输的数据被非法篡改,SSL利用基于MD5或SHA的MAC算法来保证消息的完整性。 MAC算法是在密钥参与下的数据摘要算法,能将密钥和任意长度的数据转换为固定长度的数据。发送者在密钥的参与下,利用MAC算法计算出消息的MAC值,并将其加在消息之后发送给接收者。接收者利用同样的密钥和MAC算法计算出消息的MAC值,并与接收到的MAC值比较。如果二者相同,则报文没有改变;否则,报文在传输过程中被修改,接收者将丢弃该报文。 由于MD5在实际应用中存在冲突的可能性比较大,所以尽量别采用MD5来验证内容一致性。SHA也不能使用SHA0和SHA1,中国山东大学的王小云教授在2005年就宣布破解了 SHA-1完整版算法。微软和google都已经宣布16年及17年之后不再支持sha1签名证书。MAC算法涉及到很多复杂的数学问题,这里就不多讲细节了。 专题二--【实际抓包分析】 抓包结果: fiddler: wireshark: 可以看到,百度和我们公司一样,也采用以下策略: (1)对于高版本浏览器,如果支持 https,且加解密算法在TLS1.0 以上的,都将所有 http请求重定向到 https请求 (2)对于https请求,则不变。 【以下只解读https请求】 1、TCP三次握手 可以看到,我们访问的是 http://www.baidu.com/ , 在初次建立 三次握手的时候, 用户是去 连接 8080端口的(因为公司办公网做了代理,因此,我们实际和代理机做的三次握手,公司代理机再帮我们去连接百度服务器的80端口) 2、CONNECT 建立 由于公司办公网访问非腾讯域名,会做代理,因此,在进行https访问的时候,我们的电脑需要和公司代理机做 " CONNECT " 连接(关于 " CONNECT " 连接, 可以理解为虽然后续的https请求都是公司代理机和百度服务器进行公私钥连接和对称秘钥通信,但是,有了 " CONNECT " 连接之后,可以认为我们也在直接和百度服务器进行公私钥连接和对称秘钥通信。 ) fiddler抓包结果: CONNECT之后, 后面所有的通信过程,可以看做是我们的机器和百度服务器在直接通信 3、 client hello 整个 Secure Socket Layer只包含了: TLS1.2 Record Layer内容 (1)随机数 在客户端问候中,有四个字节以Unix时间格式记录了客户端的协调世界时间(UTC)。协调世界时间是从1970年1月1日开始到当前时刻所经历的秒数。在这个例子中,0x2516b84b就是协调世界时间。在他后面有28字节的随机数( random_C ),在后面的过程中我们会用到这个随机数。 (2)SID(Session ID) 如果出于某种原因,对话中断,就需要重新握手。为了避免重新握手而造成的访问效率低下,这时候引入了session ID的概念, session ID的思想很简单,就是每一次对话都有一个编号(session ID)。如果对话中断,下次重连的时候,只要客户端给出这个编号,且服务器有这个编号的记录,双方就可以重新使用已有的"对话密钥",而不必重新生成一把。 因为我们抓包的时候,是几个小时内第一次访问 https://www.baodu.com 首页,因此,这里并没有 Session ID. (稍会儿我们会看到隔了半分钟,第二次抓包就有这个Session ID) session ID是目前所有浏览器都支持的方法,但是它的缺点在于session ID往往只保留在一台服务器上。所以,如果客户端的请求发到另一台服务器,就无法恢复对话。session ticket就是为了解决这个问题而诞生的,目前只有Firefox和Chrome浏览器支持。 (3) 密文族(Cipher Suites): RFC2246中建议了很多中组合,一般写法是"密钥交换算法-对称加密算法-哈希算法,以“TLS_RSA_WITH_AES_256_CBC_SHA”为例: (a) TLS为协议,RSA为密钥交换的算法; (b) AES_256_CBC是对称加密算法(其中256是密钥长度,CBC是分组方式); (c) SHA是哈希的算法。 浏览器支持的加密算法一般会比较多,而服务端会根据自身的业务情况选择比较适合的加密组合发给客户端。(比如综合安全性以及速度、性能等因素) (4) Server_name扩展:( 一般浏览器也支持 SNI(Server Name Indication)) 当我们去访问一个站点时,一定是先通过DNS解析出站点对应的ip地址,通过ip地址来访问站点,由于很多时候一个ip地址是给很多的站点公用,因此如果没有server_name这个字段,server是无法给与客户端相应的数字证书的,Server_name扩展则允许服务器对浏览器的请求授予相对应的证书。 还有一个很好的功能: SNI(Server Name Indication)。这个的功能比较好,为了解决一个服务器使用多个域名和证书的SSL/TLS扩展。一句话简述它的工作原理就是,在连接到服务器建立SSL连接之前先发送要访问站点的域名(Hostname),这样服务器根据这个域名返回一个合适的CA证书。目前,大多数操作系统和浏览器都已经很好地支持SNI扩展,OpenSSL 0.9.8已经内置这一功能,据说新版的nginx也支持SNI。) 4、 服务器回复(包括 Server Hello, Certificate, Certificate Status) 服务器在收到client hello后,会回复三个数据包,下面分别看一下: 1)Server Hello 1、我们得到了服务器的以Unix时间格式记录的UTC和28字节的随机数 (random_S)。 2、Seesion ID,服务端对于session ID一般会有三种选择 (稍会儿我们会看到隔了半分钟,第二次抓包就有这个Session ID) : 1)恢复的session ID:我们之前在client hello里面已经提到,如果client hello里面的session ID在服务端有缓存,服务端会尝试恢复这个session; 2)新的session ID:这里又分两种情况,第一种是client hello里面的session ID是空值,此时服务端会给客户端一个新的session ID,第二种是client hello里面的session ID此服务器并没有找到对应的缓存,此时也会回一个新的session ID给客户端; 3)NULL:服务端不希望此session被恢复,因此session ID为空。 3、我们记得在client hello里面,客户端给出了21种加密族,而在我们所提供的21个加密族中,服务端挑选了“TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256”。 (a) TLS为协议,RSA为密钥交换的算法; (b) AES_256_CBC是对称加密算法(其中256是密钥长度,CBC是分组方式); (c) SHA是哈希的算法。 这就意味着服务端会使用ECDHE-RSA算法进行密钥交换,通过AES_128_GCM对称加密算法来加密数据,利用SHA256哈希算法来确保数据完整性。这是百度综合了安全、性能、访问速度等多方面后选取的加密组合。 2)Certificate 在前面的https原理研究中,我们知道为了安全的将公钥发给客户端,服务端会把公钥放入数字证书中并发给客户端(数字证书可以自签发,但是一般为了保证安全会有一个专门的CA机构签发),所以这个报文就是数字证书,4097 bytes就是证书的长度。 我们打开这个证书,可以看到证书的具体信息,这个具体信息通过抓包报文的方式不是太直观,可以在浏览器上直接看。 (点击 chrome 浏览器 左上方的 绿色 锁型按钮) 3)Server Hello Done 我们抓的包是将 Server Hello Done 和 server key exchage 合并的包: 4)客户端验证证书真伪性 客户端验证证书的合法性,如果验证通过才会进行后续通信,否则根据错误情况不同做出提示和操作,合法性验证包括如下: 证书链的可信性trusted certificate path,方法如前文所述; 证书是否吊销revocation,有两类方式离线CRL与在线OCSP,不同的客户端行为会不同; 有效期expiry date,证书是否在有效时间范围; 域名domain,核查证书域名是否与当前的访问域名匹配,匹配规则后续分析; 5)秘钥交换 这个过程非常复杂,大概总结一下: (1)首先,其利用非对称加密实现身份认证和密钥协商,利用非对称加密,协商好加解密数据的 对称秘钥(外加CA认证,防止中间人窃取 对称秘钥) (2)然后,对称加密算法采用协商的密钥对数据加密,客户端和服务器利用 对称秘钥 进行通信; (3)最后,基于散列函数验证信息的完整性,确保通信数据不会被中间人恶意篡改。 此时客户端已经获取全部的计算协商密钥需要的信息:两个明文随机数random_C和random_S与自己计算产生的Pre-master(由客户端和服务器的 pubkey生成的一串随机数),计算得到协商对称密钥; enc_key=Fuc(random_C, random_S, Pre-Master) 6)生成 session ticket 如果出于某种原因,对话中断,就需要重新握手。为了避免重新握手而造成的访问效率低下,这时候引入了session ID的概念, session ID的思想很简单,就是每一次对话都有一个编号(session ID)。如果对话中断,下次重连的时候,只要客户端给出这个编号,且服务器有这个编号的记录,双方就可以重新使用已有的"对话密钥",而不必重新生成一把。 因为我们抓包的时候,是几个小时内第一次访问 https://www.baodu.com 首页,因此,这里并没有 Session ID. (稍会儿我们会看到隔了半分钟,第二次抓包就有这个Session ID) session ID是目前所有浏览器都支持的方法,但是它的缺点在于session ID往往只保留在一台服务器上。所以,如果客户端的请求发到另一台服务器,就无法恢复对话。session ticket就是为了解决这个问题而诞生的,目前只有Firefox和Chrome浏览器支持。 后续建立新的https会话,就可以利用 session ID 或者 session Tickets , 对称秘钥可以再次使用,从而免去了 https 公私钥交换、CA认证等等过程,极大地缩短 https 会话连接时间。 7) 利用对称秘钥传输数据 【半分钟后,再次访问百度】: 有这些大的不同: 由于服务器和浏览器缓存了 Session ID 和 Session Tickets,不需要再进行 公钥证书传递,CA认证,生成 对称秘钥等过程,直接利用半分钟前的 对称秘钥 加解密数据进行会话。 1)Client Hello 2)Server Hello

玄学酱 2019-12-02 01:27:08 0 浏览量 回答数 0

回答

1.如果是一般的话只有32&162.本来在理论上不可破解,但好像被人破解了,你可以看下参考 目前网上的dm5破解都是通过建立数据库进行查询的方法进行破解的 好像还没有直接破解的工具,网上的都属于类似穷举的方法MD5简介MD5的全称是Message-digest Algorithm 5(信息-摘要算法),用于确保信息传输完整一致。在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc,的Ronald L. Rivest开发出来,经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式(就是把一个任意长度的字节串变换成一定长的大整数)。不管是MD2、MD4还是MD5,它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似,但MD2的设计与MD4和MD5完全不同,那是因为MD2是为8位机器做过设计优化的,而MD4和MD5却是面向32位的电脑。这三个算法的描述和c语言源代码在Internet RFC 1321中有详细的描述( ,这是一份最权威的文档,由Ronald L. Rivest在1992年8月向IETF提交。 Rivest在1989年开发出MD2算法。在这个算法中,首先对信息进行数据补位,使信息的字节长度是16的倍数。然后,以一个16位的检验和追加到信息末尾。并且根据这个新产生的信息计算出散列值。后来,Rogier和Chauvaud发现如果忽略了检验和将产生MD2冲突。MD2算法的加密后结果是唯一的--即没有重复。 为了加强算法的安全性,Rivest在1990年又开发出MD4算法。MD4算法同样需要填补信息以确保信息的字节长度加上448后能被512整除(信息字节长度mod 512 = 448)。然后,一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位damg?rd/merkle迭代结构的区块,而且每个区块要通过三个不同步骤的处理。Den boer和Bosselaers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。Dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版本中的冲突(这个冲突实际上是一种漏洞,它将导致对不同的内容进行加密却可能得到相同的加密后结果)。毫无疑问,MD4就此被淘汰掉了。 尽管MD4算法在安全上有个这么大的漏洞,但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了MD5以外,其中比较有名的还有sha-1、RIPEMD以及Haval等。 一年以后,即1991年,Rivest开发出技术上更为趋近成熟的md5算法。它在MD4的基础上增加了"安全-带子"(safety-belts)的概念。虽然MD5比MD4稍微慢一些,但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中,信息-摘要的大小和填充的必要条件与MD5完全相同。Den boer和Bosselaers曾发现MD5算法中的假冲突(pseudo-collisions),但除此之外就没有其他被发现的加密后结果了。 Van oorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数(brute-force hash function),而且他们猜测一个被设计专门用来搜索MD5冲突的机器(这台机器在1994年的制造成本大约是一百万美元)可以平均每24天就找到一个冲突。但单从1991年到2001年这10年间,竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一点,我们就可以看出这个瑕疵并没有太多的影响MD5的安全性。上面所有这些都不足以成为MD5的在实际应用中的问题。并且,由于MD5算法的使用不需要支付任何版权费用的,所以在一般的情况下(非绝密应用领域。但即便是应用在绝密领域内,MD5也不失为一种非常优秀的中间技术),MD5怎么都应该算得上是非常安全的了。 2004年8月17日的美国加州圣巴巴拉的国际密码学会议(Crypto’2004)上,来自中国山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告,公布了MD系列算法的破解结果。宣告了固若金汤的世界通行密码标准MD5的堡垒轰然倒塌,引发了密码学界的轩然大波。 令世界顶尖密码学家想象不到的是,破解MD5之后,2005年2月,王小云教授又破解了另一国际密码SHA-1。因为SHA-1在美国等国际社会有更加广泛的应用,密码被破的消息一出,在国际社会的反响可谓石破天惊。换句话说,王小云的研究成果表明了从理论上讲电子签名可以伪造,必须及时添加限制条件,或者重新选用更为安全的密码标准,以保证电子商务的安全。MD5破解工程权威网站 是为了公开征集专门针对MD5的攻击而设立的,网站于2004年8月17日宣布:“中国研究人员发现了完整MD5算法的碰撞;Wang, Feng, Lai与Yu公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术,在数个小时内就可以找到MD5碰撞。……由于这个里程碑式的发现,MD5CRK项目将在随后48小时内结束”。 MD5用的是哈希函数,在计算机网络中应用较多的不可逆加密算法有RSA公司发明的MD5算法和由美国国家技术标准研究所建议的安全散列算法SHA.[编辑本段]算法的应用 MD5的典型应用是对一段信息(Message)产生信息摘要(Message-Digest),以防止被篡改。比如,在UNIX下有很多软件在下载的时候都有一个文件名相同,文件扩展名为.md5的文件,在这个文件中通常只有一行文本,大致结构如: MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息,通过其不可逆的字符串变换算法,产生了这个唯一的MD5信息摘要。为了让读者朋友对MD5的应用有个直观的认识,笔者以一个比方和一个实例来简要描述一下其工作过程: 大家都知道,地球上任何人都有自己独一无二的指纹,这常常成为公安机关鉴别罪犯身份最值得信赖的方法;与之类似,MD5就可以为任何文件(不管其大小、格式、数量)产生一个同样独一无二的“数字指纹”,如果任何人对文件做了任何改动,其MD5值也就是对应的“数字指纹”都会发生变化。 我们常常在某些软件下载站点的某软件信息中看到其MD5值,它的作用就在于我们可以在下载该软件后,对下载回来的文件用专门的软件(如Windows MD5 Check等)做一次MD5校验,以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。 MD5的典型应用是对一段Message(字节串)产生fingerprint(指纹),以防止被“篡改”。举个例子,你将一段话写在一个叫 readme.txt文件中,并对这个readme.txt产生一个MD5的值并记录在案,然后你可以传播这个文件给别人,别人如果修改了文件中的任何内容,你对这个文件重新计算MD5时就会发现(两个MD5值不相同)。如果再有一个第三方的认证机构,用MD5还可以防止文件作者的“抵赖”,这就是所谓的数字签名应用。 所以,要遇到了md5密码的问题,比较好的办法是:你可以用这个系统中的md5()函数重新设一个密码,如admin,把生成的一串密码覆盖原来的就行了。 MD5还广泛用于操作系统的登陆认证上,如Unix、各类BSD系统登录密码、数字签名等诸多方。如在UNIX系统中用户的密码是以MD5(或其它类似的算法)经Hash运算后存储在文件系统中。当用户登录的时候,系统把用户输入的密码进行MD5 Hash运算,然后再去和保存在文件系统中的MD5值进行比较,进而确定输入的密码是否正确。通过这样的步骤,系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。MD5将任意长度的“字节串”映射为一个128bit的大整数,并且是通过该128bit反推原始字符串是困难的,换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说,是因为原始的字符串有无穷多个,这有点象不存在反函数的数学函数。所以,要遇到了md5密码的问题,比较好的办法是:你可以用这个系统中的md5()函数重新设一个密码,如admin,把生成的一串密码的Hash值覆盖原来的Hash值就行了。 正是因为这个原因,现在被黑客使用最多的一种破译密码的方法就是一种被称为"跑字典"的方法。有两种方法得到字典,一种是日常搜集的用做密码的字符串表,另一种是用排列组合方法生成的,先用MD5程序计算出这些字典项的MD5值,然后再用目标的MD5值在这个字典中检索。我们假设密码的最大长度为8位字节(8 Bytes),同时密码只能是字母和数字,共26+26+10=62个字符,排列组合出的字典的项数则是P(62,1)+P(62,2)….+P(62,8),那也已经是一个很天文的数字了,存储这个字典就需要TB级的磁盘阵列,而且这种方法还有一个前提,就是能获得目标账户的密码MD5值的情况下才可以。这种加密技术被广泛的应用于UNIX系统中,这也是为什么UNIX系统比一般操作系统更为坚固一个重要原因。

祁同伟 2019-12-02 01:27:09 0 浏览量 回答数 0

回答

1.如果是一般的话只有32&162.本来在理论上不可破解,但好像被人破解了,你可以看下参考 目前网上的dm5破解都是通过建立数据库进行查询的方法进行破解的 好像还没有直接破解的工具,网上的都属于类似穷举的方法MD5简介MD5的全称是Message-digest Algorithm 5(信息-摘要算法),用于确保信息传输完整一致。在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc,的Ronald L. Rivest开发出来,经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式(就是把一个任意长度的字节串变换成一定长的大整数)。不管是MD2、MD4还是MD5,它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似,但MD2的设计与MD4和MD5完全不同,那是因为MD2是为8位机器做过设计优化的,而MD4和MD5却是面向32位的电脑。这三个算法的描述和c语言源代码在Internet RFC 1321中有详细的描述( ,这是一份最权威的文档,由Ronald L. Rivest在1992年8月向IETF提交。 Rivest在1989年开发出MD2算法。在这个算法中,首先对信息进行数据补位,使信息的字节长度是16的倍数。然后,以一个16位的检验和追加到信息末尾。并且根据这个新产生的信息计算出散列值。后来,Rogier和Chauvaud发现如果忽略了检验和将产生MD2冲突。MD2算法的加密后结果是唯一的--即没有重复。 为了加强算法的安全性,Rivest在1990年又开发出MD4算法。MD4算法同样需要填补信息以确保信息的字节长度加上448后能被512整除(信息字节长度mod 512 = 448)。然后,一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位damg?rd/merkle迭代结构的区块,而且每个区块要通过三个不同步骤的处理。Den boer和Bosselaers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。Dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版本中的冲突(这个冲突实际上是一种漏洞,它将导致对不同的内容进行加密却可能得到相同的加密后结果)。毫无疑问,MD4就此被淘汰掉了。 尽管MD4算法在安全上有个这么大的漏洞,但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了MD5以外,其中比较有名的还有sha-1、RIPEMD以及Haval等。 一年以后,即1991年,Rivest开发出技术上更为趋近成熟的md5算法。它在MD4的基础上增加了"安全-带子"(safety-belts)的概念。虽然MD5比MD4稍微慢一些,但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中,信息-摘要的大小和填充的必要条件与MD5完全相同。Den boer和Bosselaers曾发现MD5算法中的假冲突(pseudo-collisions),但除此之外就没有其他被发现的加密后结果了。 Van oorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数(brute-force hash function),而且他们猜测一个被设计专门用来搜索MD5冲突的机器(这台机器在1994年的制造成本大约是一百万美元)可以平均每24天就找到一个冲突。但单从1991年到2001年这10年间,竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一点,我们就可以看出这个瑕疵并没有太多的影响MD5的安全性。上面所有这些都不足以成为MD5的在实际应用中的问题。并且,由于MD5算法的使用不需要支付任何版权费用的,所以在一般的情况下(非绝密应用领域。但即便是应用在绝密领域内,MD5也不失为一种非常优秀的中间技术),MD5怎么都应该算得上是非常安全的了。 2004年8月17日的美国加州圣巴巴拉的国际密码学会议(Crypto’2004)上,来自中国山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告,公布了MD系列算法的破解结果。宣告了固若金汤的世界通行密码标准MD5的堡垒轰然倒塌,引发了密码学界的轩然大波。 令世界顶尖密码学家想象不到的是,破解MD5之后,2005年2月,王小云教授又破解了另一国际密码SHA-1。因为SHA-1在美国等国际社会有更加广泛的应用,密码被破的消息一出,在国际社会的反响可谓石破天惊。换句话说,王小云的研究成果表明了从理论上讲电子签名可以伪造,必须及时添加限制条件,或者重新选用更为安全的密码标准,以保证电子商务的安全。MD5破解工程权威网站 是为了公开征集专门针对MD5的攻击而设立的,网站于2004年8月17日宣布:“中国研究人员发现了完整MD5算法的碰撞;Wang, Feng, Lai与Yu公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术,在数个小时内就可以找到MD5碰撞。……由于这个里程碑式的发现,MD5CRK项目将在随后48小时内结束”。 MD5用的是哈希函数,在计算机网络中应用较多的不可逆加密算法有RSA公司发明的MD5算法和由美国国家技术标准研究所建议的安全散列算法SHA.[编辑本段]算法的应用 MD5的典型应用是对一段信息(Message)产生信息摘要(Message-Digest),以防止被篡改。比如,在UNIX下有很多软件在下载的时候都有一个文件名相同,文件扩展名为.md5的文件,在这个文件中通常只有一行文本,大致结构如: MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息,通过其不可逆的字符串变换算法,产生了这个唯一的MD5信息摘要。为了让读者朋友对MD5的应用有个直观的认识,笔者以一个比方和一个实例来简要描述一下其工作过程: 大家都知道,地球上任何人都有自己独一无二的指纹,这常常成为公安机关鉴别罪犯身份最值得信赖的方法;与之类似,MD5就可以为任何文件(不管其大小、格式、数量)产生一个同样独一无二的“数字指纹”,如果任何人对文件做了任何改动,其MD5值也就是对应的“数字指纹”都会发生变化。 我们常常在某些软件下载站点的某软件信息中看到其MD5值,它的作用就在于我们可以在下载该软件后,对下载回来的文件用专门的软件(如Windows MD5 Check等)做一次MD5校验,以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。 MD5的典型应用是对一段Message(字节串)产生fingerprint(指纹),以防止被“篡改”。举个例子,你将一段话写在一个叫 readme.txt文件中,并对这个readme.txt产生一个MD5的值并记录在案,然后你可以传播这个文件给别人,别人如果修改了文件中的任何内容,你对这个文件重新计算MD5时就会发现(两个MD5值不相同)。如果再有一个第三方的认证机构,用MD5还可以防止文件作者的“抵赖”,这就是所谓的数字签名应用。 所以,要遇到了md5密码的问题,比较好的办法是:你可以用这个系统中的md5()函数重新设一个密码,如admin,把生成的一串密码覆盖原来的就行了。 MD5还广泛用于操作系统的登陆认证上,如Unix、各类BSD系统登录密码、数字签名等诸多方。如在UNIX系统中用户的密码是以MD5(或其它类似的算法)经Hash运算后存储在文件系统中。当用户登录的时候,系统把用户输入的密码进行MD5 Hash运算,然后再去和保存在文件系统中的MD5值进行比较,进而确定输入的密码是否正确。通过这样的步骤,系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。MD5将任意长度的“字节串”映射为一个128bit的大整数,并且是通过该128bit反推原始字符串是困难的,换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说,是因为原始的字符串有无穷多个,这有点象不存在反函数的数学函数。所以,要遇到了md5密码的问题,比较好的办法是:你可以用这个系统中的md5()函数重新设一个密码,如admin,把生成的一串密码的Hash值覆盖原来的Hash值就行了。 正是因为这个原因,现在被黑客使用最多的一种破译密码的方法就是一种被称为"跑字典"的方法。有两种方法得到字典,一种是日常搜集的用做密码的字符串表,另一种是用排列组合方法生成的,先用MD5程序计算出这些字典项的MD5值,然后再用目标的MD5值在这个字典中检索。我们假设密码的最大长度为8位字节(8 Bytes),同时密码只能是字母和数字,共26+26+10=62个字符,排列组合出的字典的项数则是P(62,1)+P(62,2)….+P(62,8),那也已经是一个很天文的数字了,存储这个字典就需要TB级的磁盘阵列,而且这种方法还有一个前提,就是能获得目标账户的密码MD5值的情况下才可以。这种加密技术被广泛的应用于UNIX系统中,这也是为什么UNIX系统比一般操作系统更为坚固一个重要原因。

青衫无名 2019-12-02 01:27:08 0 浏览量 回答数 0

回答

1.如果是一般的话只有32&162.本来在理论上不可破解,但好像被人破解了,你可以看下参考 目前网上的dm5破解都是通过建立数据库进行查询的方法进行破解的 好像还没有直接破解的工具,网上的都属于类似穷举的方法MD5简介MD5的全称是Message-digest Algorithm 5(信息-摘要算法),用于确保信息传输完整一致。在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc,的Ronald L. Rivest开发出来,经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式(就是把一个任意长度的字节串变换成一定长的大整数)。不管是MD2、MD4还是MD5,它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似,但MD2的设计与MD4和MD5完全不同,那是因为MD2是为8位机器做过设计优化的,而MD4和MD5却是面向32位的电脑。这三个算法的描述和c语言源代码在Internet RFC 1321中有详细的描述( ,这是一份最权威的文档,由Ronald L. Rivest在1992年8月向IETF提交。 Rivest在1989年开发出MD2算法。在这个算法中,首先对信息进行数据补位,使信息的字节长度是16的倍数。然后,以一个16位的检验和追加到信息末尾。并且根据这个新产生的信息计算出散列值。后来,Rogier和Chauvaud发现如果忽略了检验和将产生MD2冲突。MD2算法的加密后结果是唯一的--即没有重复。 为了加强算法的安全性,Rivest在1990年又开发出MD4算法。MD4算法同样需要填补信息以确保信息的字节长度加上448后能被512整除(信息字节长度mod 512 = 448)。然后,一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位damg?rd/merkle迭代结构的区块,而且每个区块要通过三个不同步骤的处理。Den boer和Bosselaers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。Dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版本中的冲突(这个冲突实际上是一种漏洞,它将导致对不同的内容进行加密却可能得到相同的加密后结果)。毫无疑问,MD4就此被淘汰掉了。 尽管MD4算法在安全上有个这么大的漏洞,但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了MD5以外,其中比较有名的还有sha-1、RIPEMD以及Haval等。 一年以后,即1991年,Rivest开发出技术上更为趋近成熟的md5算法。它在MD4的基础上增加了"安全-带子"(safety-belts)的概念。虽然MD5比MD4稍微慢一些,但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中,信息-摘要的大小和填充的必要条件与MD5完全相同。Den boer和Bosselaers曾发现MD5算法中的假冲突(pseudo-collisions),但除此之外就没有其他被发现的加密后结果了。 Van oorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数(brute-force hash function),而且他们猜测一个被设计专门用来搜索MD5冲突的机器(这台机器在1994年的制造成本大约是一百万美元)可以平均每24天就找到一个冲突。但单从1991年到2001年这10年间,竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一点,我们就可以看出这个瑕疵并没有太多的影响MD5的安全性。上面所有这些都不足以成为MD5的在实际应用中的问题。并且,由于MD5算法的使用不需要支付任何版权费用的,所以在一般的情况下(非绝密应用领域。但即便是应用在绝密领域内,MD5也不失为一种非常优秀的中间技术),MD5怎么都应该算得上是非常安全的了。 2004年8月17日的美国加州圣巴巴拉的国际密码学会议(Crypto’2004)上,来自中国山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告,公布了MD系列算法的破解结果。宣告了固若金汤的世界通行密码标准MD5的堡垒轰然倒塌,引发了密码学界的轩然大波。 令世界顶尖密码学家想象不到的是,破解MD5之后,2005年2月,王小云教授又破解了另一国际密码SHA-1。因为SHA-1在美国等国际社会有更加广泛的应用,密码被破的消息一出,在国际社会的反响可谓石破天惊。换句话说,王小云的研究成果表明了从理论上讲电子签名可以伪造,必须及时添加限制条件,或者重新选用更为安全的密码标准,以保证电子商务的安全。MD5破解工程权威网站 是为了公开征集专门针对MD5的攻击而设立的,网站于2004年8月17日宣布:“中国研究人员发现了完整MD5算法的碰撞;Wang, Feng, Lai与Yu公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术,在数个小时内就可以找到MD5碰撞。……由于这个里程碑式的发现,MD5CRK项目将在随后48小时内结束”。 MD5用的是哈希函数,在计算机网络中应用较多的不可逆加密算法有RSA公司发明的MD5算法和由美国国家技术标准研究所建议的安全散列算法SHA.[编辑本段]算法的应用 MD5的典型应用是对一段信息(Message)产生信息摘要(Message-Digest),以防止被篡改。比如,在UNIX下有很多软件在下载的时候都有一个文件名相同,文件扩展名为.md5的文件,在这个文件中通常只有一行文本,大致结构如: MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息,通过其不可逆的字符串变换算法,产生了这个唯一的MD5信息摘要。为了让读者朋友对MD5的应用有个直观的认识,笔者以一个比方和一个实例来简要描述一下其工作过程: 大家都知道,地球上任何人都有自己独一无二的指纹,这常常成为公安机关鉴别罪犯身份最值得信赖的方法;与之类似,MD5就可以为任何文件(不管其大小、格式、数量)产生一个同样独一无二的“数字指纹”,如果任何人对文件做了任何改动,其MD5值也就是对应的“数字指纹”都会发生变化。 我们常常在某些软件下载站点的某软件信息中看到其MD5值,它的作用就在于我们可以在下载该软件后,对下载回来的文件用专门的软件(如Windows MD5 Check等)做一次MD5校验,以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。 MD5的典型应用是对一段Message(字节串)产生fingerprint(指纹),以防止被“篡改”。举个例子,你将一段话写在一个叫 readme.txt文件中,并对这个readme.txt产生一个MD5的值并记录在案,然后你可以传播这个文件给别人,别人如果修改了文件中的任何内容,你对这个文件重新计算MD5时就会发现(两个MD5值不相同)。如果再有一个第三方的认证机构,用MD5还可以防止文件作者的“抵赖”,这就是所谓的数字签名应用。 所以,要遇到了md5密码的问题,比较好的办法是:你可以用这个系统中的md5()函数重新设一个密码,如admin,把生成的一串密码覆盖原来的就行了。 MD5还广泛用于操作系统的登陆认证上,如Unix、各类BSD系统登录密码、数字签名等诸多方。如在UNIX系统中用户的密码是以MD5(或其它类似的算法)经Hash运算后存储在文件系统中。当用户登录的时候,系统把用户输入的密码进行MD5 Hash运算,然后再去和保存在文件系统中的MD5值进行比较,进而确定输入的密码是否正确。通过这样的步骤,系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。MD5将任意长度的“字节串”映射为一个128bit的大整数,并且是通过该128bit反推原始字符串是困难的,换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说,是因为原始的字符串有无穷多个,这有点象不存在反函数的数学函数。所以,要遇到了md5密码的问题,比较好的办法是:你可以用这个系统中的md5()函数重新设一个密码,如admin,把生成的一串密码的Hash值覆盖原来的Hash值就行了。 正是因为这个原因,现在被黑客使用最多的一种破译密码的方法就是一种被称为"跑字典"的方法。有两种方法得到字典,一种是日常搜集的用做密码的字符串表,另一种是用排列组合方法生成的,先用MD5程序计算出这些字典项的MD5值,然后再用目标的MD5值在这个字典中检索。我们假设密码的最大长度为8位字节(8 Bytes),同时密码只能是字母和数字,共26+26+10=62个字符,排列组合出的字典的项数则是P(62,1)+P(62,2)….+P(62,8),那也已经是一个很天文的数字了,存储这个字典就需要TB级的磁盘阵列,而且这种方法还有一个前提,就是能获得目标账户的密码MD5值的情况下才可以。这种加密技术被广泛的应用于UNIX系统中,这也是为什么UNIX系统比一般操作系统更为坚固一个重要原因。-------------------------就低频来说我认为是EX71好,如果你没有太高的要求EX71 吧 EX71是目前最好的 价钱也便宜 。最重要的是性价比超高。。。我就买了部

行者武松 2019-12-02 01:27:09 0 浏览量 回答数 0

问题

ODPS大讲堂之概述篇

halcyon 2019-12-01 21:51:22 21648 浏览量 回答数 19

问题

rsync 的核心算法:报错

kun坤 2020-06-14 11:17:55 0 浏览量 回答数 1

回答

1、 你这个问题我感觉提的不专业。我感觉你对名词的概念定义有点混乱。 2、 算法是一系列解决问题的步骤,可以画个流程图出来,分为伪代码的定义描述 和真代码的实现。 3、 如果你是志在创造算法,青史留名的话(比如什么逆波兰,迪克斯特拉算法什么的),我想你应该读到博士。做个真正的计算机科学家,努力发表几篇论文,这样对你青史留名可能会有帮助。 4、我个人认为,为了就业的话,理解现有数据结构和算法的代码实现,并且做到工程化应用,企业的工程项目上面不提倡重复造轮子,一般是拿来主义,看懂别人的轮子,会拆除,会重组轮子,是最重要的。

祁同伟 2019-12-02 01:20:13 0 浏览量 回答数 0

问题

终于开始没日没夜加班了,可是笑不出来了。。。啊哈哈哈哈哈哈 400 请求报错 

kun坤 2020-05-30 14:23:06 0 浏览量 回答数 1

回答

回 2楼(ldl) 的帖子 S1用什么语言关系不大,熟悉和顺手的就行。很快就会开放ODPS相关的文档(当然也包括XLib和XLab),那个时候再学习来得及。 ------------------------- 回 4楼(test010) 的帖子 天池是一个分布式计算的集群,程序语言倒是次要,更多的变化是模式上的,从单机处理的模式转化到MapReduce,很多数据与处理的工作用类似SQL的方式做很多预处理,或者通过MR的方式做处理,训练阶段的算法可以用天池提供的高性能的算法包,或者自己基于MR/Graph开发。S1更多的是熟悉数据、探索数据。

jxu 2019-12-02 02:53:28 0 浏览量 回答数 0

回答

曾经因为看不懂数据结构和算法,而一度怀疑是自己太笨,实际上,很多人在第一次接触这门课时,都会有这种感觉,觉得数据结构和算法很抽象,晦涩难懂,宛如天书。正是这个原因,让很多初学者对这门课望而却步,希望以下分享能为初学者排忧解难。 我个人觉得,其实真正的原因是你没有找到好的学习方法,没有抓住学习的重点。实际上,数据结构和算法的东西并不多,常用的、基础的知识点更是屈指可数。只要掌握了正确的学习方法,学起来并没有看上去那么难,更不需要什么高智商、厚底子。 还记得大学里每次考前老师都要划重点吗?今天,我就给你划划我们这门课的重点,再告诉你一些我总结的学习小窍门。相信有了这些之后,你学起来就会有的放矢、事半功倍了。 什么是数据结构?什么是算法? 大部分数据结构和算法教材,在开篇都会给这两个概念下一个明确的定义。但是,这些定义都很抽象,对理解这两个概念并没有实质性的帮助,反倒会让你陷入死抠定义的误区。毕竟,我们现在学习,并不是为了考试,所以,概念背得再牢,不会用也就没什么用。 虽然我们说没必要深挖严格的定义,但是这并不等于不需要理解概念。下面我就从广义和狭义两个层面,来帮你理解数据结构与算法这两个概念。 从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。 图书馆储藏书籍你肯定见过吧?为了方便查找,图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号,就是书籍这种“数据”的存储结构。 那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都是算法。 从狭义上讲,是指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶,我们可以直接拿来用。我们要讲的这些经典数据结构和算法,都是前人从很多实际操作场景中抽象出来的,经过非常多的求证和检验,可以高效地帮助我们解决很多实际的开发问题。 那数据结构和算法有什么关系呢?为什么大部分书都把这两个东西放到一块儿来讲呢? 这是因为,数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。 比如,因为数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表并不支持随机访问。 数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法,孤立存在的数据结构就是没用的。 现在你对数据结构与算法是不是有了比较清晰的理解了呢?有了这些储备,下面我们来看看,究竟该怎么学数据结构与算法。 看到数据结构和算法里的“算法”两个字,很多人就会联想到“数学”,觉得算法会涉及到很多深奥的数学知识。那我数学基础不是很好,学起来会不会很吃力啊? 数据结构和算法课程确实会涉及一些数学方面的推理、证明,尤其是在分析某个算法的时间、空间复杂度的时候,但是这个你完全不需要担心。 学习的重点在什么地方? 提到数据结构和算法,很多人就很头疼,因为这里面的内容实在是太多了。这里,我就帮你梳理一下,应该先学什么,后学什么。你可以对照看看,你属于哪个阶段,然后有针对地进行学习。 想要学习数据结构与算法,首先要掌握一个数据结构与算法中最重要的概念——复杂度分析。 这个概念究竟有多重要呢?可以这么说,它几乎占了数据结构和算法这门课的半壁江山,是数据结构和算法学习的精髓。 数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。所以,如果你只掌握了数据结构和算法的特点、用法,但是没有学会复杂度分析,那就相当于只知道操作口诀,而没掌握心法。只有把心法了然于胸,才能做到无招胜有招! 所以,复杂度分析这个内容,你也一定要花大力气来啃,必须要拿下,并且要搞得非常熟练。否则,后面的数据结构和算法也很难学好。 搞定复杂度分析,下面就要进入数据结构与算法的正文内容了。 为了让你对数据结构和算法能有个全面的认识,我画了一张图,里面几乎涵盖了所有数据结构和算法书籍中都会讲到的知识点。 但是,作为初学者,或者一个非算法工程师来说,你并不需要掌握图里面的所有知识点。很多高级的数据结构与算法,比如二分图、最大流等,这些在我们平常的开发中很少会用到。所以,你暂时可以不用看。我还是那句话,咱们学习要学会找重点。如果不分重点地学习,眉毛胡子一把抓,学起来肯定会比较吃力。 所以,结合我自己的学习心得,还有这些年的面试、开发经验,我总结了20个最常用的、最基础数据结构与算法,不管是应付面试还是工作需要,只要集中精力逐一攻克这20个知识点就足够了。 这里面有10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树;10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。 掌握了这些基础的数据结构和算法,再学更加复杂的数据结构和算法,就会非常容易、非常快。 与此同时,为了帮助大家学习算法,准备了一份学习资料,获取方式:关注我的公众号“程序媛不是程序猿”,回复“算法”即可弹出领取地址。对于新手来说很适用。 在学习数据结构和算法的过程中,你也要注意,不要只是死记硬背,不要为了学习而学习,而是要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”。对于每一种数据结构或算法,我都会从这几个方面进行详细讲解。只要你掌握了《数据结构与算法之美》每节课里讲的内容,就能在开发中灵活应用。 学习数据结构和算法的过程,是非常好的思维训练的过程,所以,千万不要被动地记忆,要多辩证地思考,多问为什么。如果你一直这么坚持做,你会发现,等你学完之后,写代码的时候就会不由自主地考虑到很多性能方面的事情,时间复杂度、空间复杂度非常高的垃圾代码出现的次数就会越来越少。你的编程内功就真正得到了修炼。 一些可以让你事半功倍的学习技巧 前面我给你划了学习的重点,作为一个过来人,现在我就给你分享一下,学习的一些技巧。掌握了这些技巧,可以让你化被动为主动,学起来更加轻松,更加有动力! 边学边练,适度刷题 “边学边练”这一招非常有用。建议你每周花1~2个小时的时间,集中把这周的三节内容涉及的数据结构和算法,全都自己写出来,用代码实现一遍。这样一定会比单纯地看或者听的效果要好很多! 有面试需求的同学,可能会问了,那我还要不要去刷题呢? 我个人的观点是可以“适度”刷题,但一定不要浪费太多时间在刷题上。我们学习的目的还是掌握,然后应用。除非你要面试Google、Facebook这样的公司,它们的算法题目非常非常难,必须大量刷题,才能在短期内提升应试正确率。如果是应对国内公司的技术面试,即便是BAT这样的公司,你只要彻底掌握这个专栏的内容,就足以应对。 多问、多思考、多互动 学习最好的方法是,找到几个人一起学习,一块儿讨论切磋,有问题及时寻求老师答疑。但是,离开大学之后,既没有同学也没有老师,这个条件就比较难具备了。 打怪升级学习法 学习的过程中,我们碰到最大的问题就是,坚持不下来。是的,很多基础课程学起来都非常枯燥。为此,我自己总结了一套“打怪升级学习法”。 游戏你肯定玩过吧?为什么很多看起来非常简单又没有乐趣的游戏,你会玩得不亦乐乎呢?这是因为,当你努力打到一定级别之后,每天看着自己的经验值、战斗力在慢慢提高,那种每天都在一点一点成长的成就感就不由自主地产生了。 知识需要沉淀,不要想试图一下子掌握所有 在学习的过程中,一定会碰到“拦路虎”。如果哪个知识点没有怎么学懂,不要着急,这是正常的。因为,想听一遍、看一遍就把所有知识掌握,这肯定是不可能的。学习知识的过程是反复迭代、不断沉淀的过程。 这些内容是我根据平时的学习和工作、面试经验积累,精心筛选出来的。只要掌握这些内容,应付日常的面试、工作,基本不会有问题。 以上内容出自近70000+程序员的算法课堂《数据结构与算法之美》,这个专栏是市面上唯一一门真正适用于工程师的专栏,专栏中列举大量实际软件开发中的场景,给你展示如何利用数据结构和算法解决真实的问题。整个专栏会涵盖100 多个算法真实项目场景案例,更难得的是它跟市面上晦涩的算法书籍不同的是,还手绘了一些清晰易懂的详解图(总共有 300 多张)。 手绘图—出自《数据结构与算法之美》 专栏已经更新完毕,72 篇文章,27 万字,这个专栏作者并非只是单纯地把某个知识点讲清楚,而是结合作者的理解、实践和经验来讲解,我相信它是一个跟所有国内、国外经典书籍都不一样的专栏,一个可以长期影响一些人的专栏。 这个专栏不会像《算法导论》那样,里面有非常复杂的数学证明和推理。作者会由浅入深,从概念到应用,一点一点给你解释清楚。你只要有高中数学水平,就完全可以学习。 当然,当然希望你最好有些编程基础,如果有项目经验就更好了。这样给你讲数据结构和算法如何提高效率、如何节省存储空间,你就会有很直观的感受。因为,对于每个概念和实现过程,作者都会从实际场景出发,不仅教你“是什么”,还会教你“为什么”,并且告诉你遇到同类型问题应该“怎么做”。 强烈推荐这个专栏给想攻克算法的同学,它改变了无数对算法恐惧的同学,我整理了一些专栏的评价给大家参考。

游客arp6khj2dsufi 2019-12-02 03:09:08 0 浏览量 回答数 0

问题

时间复杂度 7月1日 【今日算法】

游客ih62co2qqq5ww 2020-07-02 23:54:51 6 浏览量 回答数 1

问题

程序为什么会超时? 7月4日 【今日算法】

游客ih62co2qqq5ww 2020-07-06 23:15:34 113 浏览量 回答数 1

回答

迭代法  迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。   迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。   利用迭代算法解决问题,需要做好以下三个方面的工作:   一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。   二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。   三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。   例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。   分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有   u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,……   根据这个规律,可以归纳出下面的递推公式:   u n = u n - 1 × 2 (n ≥ 2)   对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系:   y=x*2   x=y   让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下:   cls   x=1   for i=2 to 12   y=x*2   x=y   next i   print y   end   例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。   分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。   设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有   x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)   因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式:   x=x/2 ( x 的初值为第 15 次分裂之后的个数 2^20 )   让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下:   cls   x=2^20   for i=1 to 15   x=x/2   next i   print x   end   ps:java中幂的算法是Math.pow(2, 20);返回double,稍微注意一下   例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。   要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。   分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是:   if n 为偶数 then   n=n/2   else   n=n*3+1   end if   这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下:   cls   input "Please input n=";n   do until n=1   if n mod 2=0 then   rem 如果 n 为偶数,则调用迭代公式 n=n/2   n=n/2   print "—";n;   else   n=n*3+1   print "—";n;   end if   loop   end   迭代法   迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:   (1) 选一个方程的近似根,赋给变量x0;   (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;   (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。   若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:   【算法】迭代法求方程的根   { x0=初始近似根;   do {   x1=x0;   x0=g(x1); /*按特定的方程计算新的近似根*/   } while ( fabs(x0-x1)>Epsilon);   printf(“方程的近似根是%f\n”,x0);   }   迭代算法也常用于求方程组的根,令   X=(x0,x1,…,xn-1)   设方程组为:   xi=gi(X) (I=0,1,…,n-1)   则求方程组根的迭代算法可描述如下:   【算法】迭代法求方程组的根   { for (i=0;i   x=初始近似根;   do {   for (i=0;i   y=x;   for (i=0;i   x=gi(X);   for (delta=0.0,i=0;i   if (fabs(y-x)>delta) delta=fabs(y-x);   } while (delta>Epsilon);   for (i=0;i   printf(“变量x[%d]的近似根是 %f”,I,x);   printf(“\n”);   }   具体使用迭代法求根时应注意以下两种可能发生的情况:   (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;   (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。   递归   递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。   能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。   【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。   斐波那契数列为:0、1、1、2、3、……,即:   fib(0)=0;   fib(1)=1;   fib(n)=fib(n-1)+fib(n-2) (当n>1时)。   写成递归函数有:   int fib(int n)   { if (n==0) return 0;   if (n==1) return 1;   if (n>1) return fib(n-1)+fib(n-2);   }   递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。   在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。   在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。   由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。   【问题】 组合问题   问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1   (4)5、3、2 (5)5、3、1 (6)5、2、1   (7)4、3、2 (8)4、3、1 (9)4、2、1   (10)3、2、1   分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。   【程序】   # include   # define MAXN 100   int a[MAXN];   void comb(int m,int k)   { int i,j;   for (i=m;i>=k;i--)   { a[k]=i;   if (k>1)   comb(i-1,k-1);   else   { for (j=a[0];j>0;j--)   printf(“%4d”,a[j]);   printf(“\n”);   }   }   }   void main()   { a[0]=3;   comb(5,3);   }   【问题】 背包问题   问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。   设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。   对于第i件物品的选择考虑有两种可能:   (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。   (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。   按以上思想写出递归算法如下:   try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)   { /*考虑物品i包含在当前方案中的可能性*/   if(包含物品i是可以接受的)   { 将物品i包含在当前方案中;   if (i   try(i+1,tw+物品i的重量,tv);   else   /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   恢复物品i不包含状态;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (不包含物品i仅是可男考虑的)   if (i   try(i+1,tw,tv-物品i的价值);   else   /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   }

沉默术士 2019-12-02 01:25:10 0 浏览量 回答数 0

回答

在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结构,但是在jdk1.8里 加入了红黑树的实现,当链表的长度大于8时,转换为红黑树的结构。这里写图片描述从上图中可以看出,Java中HashMap采用了链地址法。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。 */ static class Node<K,V> implements Map.Entry<K,V> { final int hash;//用于定位数组索引的位置 final K key; V value; Node<K,V> next;//链表的下一个Node Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。这里存在一个问题,即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。于是,在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法

wangccsy 2019-12-02 01:47:22 0 浏览量 回答数 0

回答

首先说结论:你的后端部门不够硬。把后端的事情推给前端了。 前端后端是程序产业化发生的分工。 首先对比传统开发模式:一人模式。即做前端又做后端。设计者决定表现方式,用表现方式决定前端,从而决定后端。前端后端除了可视化以外并无明显分别。你可以把后端代码放前端里(跟计算有关的。)。也可以把前端代码放后端里(跟查看有关的。)。 产业化后,人们发现,一人模式, 由于返工特点,在大程序(姑且这么说)合作时,产生的返工成本无法接受。于是人们引入工业模式:设计论证差不多了以后,拿出一个不需要改的可行方案。分配给各部具化。这不但减少返工,还能提高人力利用率。(每个人都干起来,不闲着) 前后之分就是从这里开始的。姑且分为设计阶段和实行阶段。设计阶段就是通篇考虑,保证可行(不行就自己上)。实行阶段就是做自己能做的,按设计要求具化。可以看出,两个阶段需要的人的编程能力是不一样的。实行阶段可以换人,而设计阶段需要总体负责,需要的经验肯定不一样。 于是产业化分工降成本的有势就体现出来了:训练专业化工人的成本,小于掌握所有环节的工人的成本。(全是工人,这么说没错) 于是把工作分为前后端,可以大致的对应到设计和具化分类上。其实是设计和具化。(具化就是已经有大致路径,需要精确细化。并且不能偏离路径) 所以后端的人最讨厌前端的人谈论算法。这等于说他的算法是拉gi。但是他的设计书确实有毛病,或者根本是业务需求——根本什么都不是。直接挑战了他的存在意义。所以先喷你没毛病。

晚来风急 2019-12-02 01:22:17 0 浏览量 回答数 0

问题

【精品问答】大数据技术、大数据计算五十问第一期

问问小秘 2019-12-01 21:51:57 100 浏览量 回答数 1

回答

有编程能力和数据挖掘能力的工程师最火,包括:数据挖掘工程师、机器学习工程师,算法工程师。 今年3月份时,谷歌开发的人工智能AlphaGo打败了全球最顶尖的围棋高手,轰动全世界,AI时代正式拉开序幕。实际上,人工智能这一概念早在上世纪一大批科幻小说陆续发表时,就已被人们接受,而随着科技的发展,人工智能的发展前景更是日益清晰。一个人工智能的诞生需要无数个工程师挥洒汗水。其中,负责开发学习算法、使机器能像人类一样思考问题的数据挖掘工程师更是无比重要。什么人能完成人工智能的开发任务呢。必须指出,人工智能和一般的计算机程序有极大的差别,它应当具有“能够自主学习知识”这一特点,这一特点也被称为“机器学习”。而自学习模型(或者说机器学习能力开发)正是数据挖掘工程师的强项,人工智能的诞生和普及需要一大批数据挖掘工程师。  那么在AI时代,如何才能掌握相关的技能,成为企业需要的数据挖掘人才呢。 第一个门槛是数学 首先,机器学习的第一个门槛是数学知识。机器学习算法需要的数学知识集中在微积分、线性代数和概率与统计当中,具有本科理工科专业的同学对这些知识应该不陌生,如果你已经还给了老师,我还是建议你通过自学或大数据学习社区补充相关知识。所幸的是如果只是想合理应用机器学习算法,而不是做相关方向高精尖的研究,需要的数学知识啃一啃教科书还是基本能理解下来的。 第二个门槛是编程 跨过了第一步,就是如何动手解决问题。所谓工欲善其事必先利其器,如果没有工具,那么所有的材料和框架、逻辑、思路都给你,也寸步难行。因此我们还是得需要合适的编程语言、工具和环境帮助自己在数据集上应用机器学习算法。对于有计算机编程基础的初学者而言,Python是很好的入门语言,很容易上手,同时又活跃的社区支持,丰富的工具包帮助我们完成想法。没有编程基础的同学掌握R或者平台自带的一些脚本语言也是不错的选择。 Make your hands dirty 接下来就是了解机器学习的工作流程和掌握常见的算法。一般机器学习步骤包括: 数据建模:将业务问题抽象为数学问题; 数据获取:获取有代表性的数据,如果数据量太大,需要考虑分布式存储和管理; 特征工程:包括特征预处理与特征选择两个核心步骤,前者主要是做数据清洗,好的数据清洗过程可以使算法的效果和性能得到显著提高,这一步体力活多一些,也比较耗时,但也是非常关键的一个步骤。特征选择对业务理解有一定要求,好的特征工程会降低对算法和数据量的依赖。 模型调优:所谓的训练数据都是在这个环节处理的,简单的说就是通过迭代分析和参数优化使上述所建立的特征工程是最优的。 这些工作流程主要是工程实践上总结出的一些经验。并不是每个项目都包含完整的一个流程,只有大家自己多实践,多积累项目经验,才会有自己更深刻的认识。 翻过了数学和编程两座大山,就是如何实践的问题,其中一个捷径就是积极参加国内外各种数据挖掘竞赛。国外的Kaggle和国内的阿里天池比赛都是很好的平台,你可以在上面获取真实的数据和队友们一起学习和进行竞赛,尝试使用已经学过的所有知识来完成这个比赛本身也是一件很有乐趣的事情。 另外就是企业实习,可以先从简单的统计分析和数据清洗开始做起,积累自己对数据的感觉,同时了解企业的业务需求和生产环境。我们通常讲从事数据科学的要”Make your hands dirty”,就是说要通过多接触数据加深对数据和业务的理解,好厨子都是食材方面的专家,你不和你的“料”打交道,怎么能谈的上去应用好它。 摆脱学习的误区 初学机器学习可能有一个误区,就是一上来就陷入到对各种高大上算法的追逐当中。动不动就讨论我能不能用深度学习去解决这个问题啊。实际上脱离业务和数据的算法讨论是毫无意义的。上文中已经提到,好的特征工程会大大降低对算法和数据量的依赖,与其研究算法,不如先厘清业务问题。任何一个问题都可以用最传统的的算法,先完整的走完机器学习的整个工作流程,不断尝试各种算法深挖这些数据的价值,在运用过程中把数据、特征和算法搞透。真正积累出项目经验才是最快、最靠谱的学习路径。 自学还是培训 很多人在自学还是参加培训上比较纠结。我是这么理解的,上述过程中数学知识需要在本科及研究生阶段完成,离开学校的话基本上要靠自学才能补充这方面的知识,所以建议那些还在学校里读书并且有志于从事数据挖掘工作的同学在学校把数学基础打好,书到用时方恨少,希望大家珍惜在学校的学习时间。 除了数学以外,很多知识的确可以通过网络搜索的方式自学,但前提是你是否拥有超强的自主学习能力,通常拥有这种能力的多半是学霸,他们能够跟据自己的情况,找到最合适的学习资料和最快学习成长路径。如果你不属于这一类人,那么参加职业培训也许是个不错的选择,在老师的带领下可以走少很多弯路。另外任何学习不可能没有困难,也就是学习道路上的各种沟沟坎坎,通过老师的答疑解惑,可以让你轻松迈过这些障碍,尽快实现你的“小”目标。 机器学习这个领域想速成是不太可能的,但是就入门来说,如果能有人指点一二还是可以在短期内把这些经典算法都过一遍,这番学习可以对机器学习的整体有个基本的理解,从而尽快进入到这个领域。师傅领进门,修行靠个人,接下来就是如何钻进去了,好在现在很多开源库给我们提供了实现的方法,我们只需要构造基本的算法框架就可以了,大家在学习过程中应当尽可能广的学习机器学习的经典算法。 学习资料 至于机器学习的资料网上很多,大家可以找一下,我个人推荐李航老师的《统计机器学习》和周志华老师的《机器学习》这两门书,前者理论性较强,适合数学专业的同学,后者读起来相对轻松一些,适合大多数理工科专业的同学。

管理贝贝 2019-12-02 01:21:46 0 浏览量 回答数 0

问题

【精品问答】大数据计算技术1000问

问问小秘 2019-12-01 21:57:13 6895 浏览量 回答数 2

回答

一股脑的后端计算的,写代码都不考虑性能问题吗?还是自己想偷懒不想做一点儿交互效果 1、购物车里面的实时变动统计数据可以交给前端统计,**但是加减数量是必须要加减库存的,所以这一步必须要调用后端接口,这里包含了邮费计算价格,会选择地址有接口处理这个运费,这些跟统计没关系,前端莫非是根据定义好的价格 加减统计 总价格 优惠价格 那些 ** 2、至于什么优惠券 那些 它有一个额度, 莫非就是在选择的时候 规定只能选择那些 核心的就是 你提交订单的时候,后端是不会让你提交你算的价格,也不会采纳你的提交价格,会根据购买的产品 优惠券重新计算出来 这个才最后的总价格 也是支付价格 如果购物车立即购买也让后端计算,又要走数据库,如果你说不走数据库,你把你的价格提交给后端,然后 + - 吗?意义何在?而算法跟你的一模一样,而你前端也要多调接口处理。这不是脱裤子放屁吗?

崩溃的油条 2020-02-09 11:04:31 0 浏览量 回答数 0

回答

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 利用迭代算法解决问题,需要做好以下三个方面的工作: 一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。 例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。 分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 根据这个规律,可以归纳出下面的递推公式: u n = u n - 1 × 2 (n ≥ 2) 对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: cls x=1 for i=2 to 12 y=x*2 x=y next i print y end 例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2 20 个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。 分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴 2 20 个”,即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2 20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 ( x 的初值为第 15 次分裂之后的个数 2 20 ) 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: cls x=2^20 for i=1 to 15 x=x/2 next i print x end 例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是: if n 为偶数 then n=n/2 else n=n*3+1 end if 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下: cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 如果 n 为偶数,则调用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end 迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: (1) 选一个方程的近似根,赋给变量x0; (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon); for (i=0;i printf(“变量x[%d]的近似根是 %f”,I,x); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 递归 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 斐波那契数列为:0、1、1、2、3、……,即: fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 写成递归函数有: int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 【问题】 组合问题 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1 (4)5、3、2 (5)5、3、1 (6)5、2、1 (7)4、3、2 (8)4、3、1 (9)4、2、1 (10)3、2、1 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int a[MAXN]; void comb(int m,int k) { int i,j; for (i=m;i>=k;i--) { a[k]=i; if (k>1) comb(i-1,k-1); else { for (j=a[0];j>0;j--) printf(“%4d”,a[j]); printf(“\n”); } } } void main() { a[0]=3; comb(5,3); } 【问题】 背包问题 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 对于第i件物品的选择考虑有两种可能: (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 按以上思想写出递归算法如下: try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) { /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) { 将物品i包含在当前方案中; if (i try(i+1,tw+物品i的重量,tv); else /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可男考虑的) if (i try(i+1,tw,tv-物品i的价值); else /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; } 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 物品 0 1 2 3 重量 5 3 2 1 价值 4 4 3 1 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 按上述算法编写函数和程序如下: 【程序】 # include # define N 100 double limitW,totV,maxV; int option[N],cop[N]; struct { double weight; double value; }a[N]; int n; void find(int i,double tw,double tv) { int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+a.weight<=limitW) { cop=1; if (i else { for (k=0;k option[k]=cop[k]; maxv=tv; } cop=0; } /*考虑物品i不包含在当前方案中的可能性*/ if (tv-a.value>maxV) if (i else { for (k=0;k option[k]=cop[k]; maxv=tv-a.value; } } void main() { int k; double w,v; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入各物品的重量和价值\n”); for (totv=0.0,k=0;k { scanf(“%1f%1f”,&w,&v); a[k].weight=w; a[k].value=v; totV+=V; } printf(“输入限制重量\n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int ; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.=1; twv.tw=tw; twv.tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.; tw=twv.tw; tv=twv.tv; switch(f) { case 1: twv.++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].!=0; } break; case 0: i--; break; default: twv.=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入限制重量\n”); scanf(“%1f”,&limitW); printf(“输入各物品的重量和价值\n”); for (k=0;k scanf(“%1f%1f”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\n选中的物品为\n”); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 递归的基本概念和特点 程序调用自身的编程技巧称为递归( recursion)。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。 注意: (1) 递归就是在过程或函数里调用自身; (2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。

马铭芳 2019-12-02 01:24:44 0 浏览量 回答数 0

回答

  迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。   利用迭代算法解决问题,需要做好以下三个方面的工作:   一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。   二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。   三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。   例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。   分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有   u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,……   根据这个规律,可以归纳出下面的递推公式:   u n = u n - 1 × 2 (n ≥ 2)   对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系:   y=x*2   x=y   让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下:   cls   x=1   for i=2 to 12   y=x*2   x=y   next i   print y   end   例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2 20 个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。   分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴 2 20 个”,即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2 20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。   设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有   x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)   因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式:   x=x/2 ( x 的初值为第 15 次分裂之后的个数 2 20 )   让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下:   cls   x=2^20   for i=1 to 15   x=x/2   next i   print x   end   例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。   要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。   分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是:   if n 为偶数 then   n=n/2   else   n=n*3+1   end if   这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下:   cls   input "Please input n=";n   do until n=1   if n mod 2=0 then   rem 如果 n 为偶数,则调用迭代公式 n=n/2   n=n/2   print "—";n;   else   n=n*3+1   print "—";n;   end if   loop   end   迭代法   迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:   (1) 选一个方程的近似根,赋给变量x0;   (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;   (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。   若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:   【算法】迭代法求方程的根   { x0=初始近似根;   do {   x1=x0;   x0=g(x1); /*按特定的方程计算新的近似根*/   } while ( fabs(x0-x1)>Epsilon);   printf(“方程的近似根是%f\n”,x0);   }   迭代算法也常用于求方程组的根,令   X=(x0,x1,…,xn-1)   设方程组为:   xi=gi(X) (I=0,1,…,n-1)   则求方程组根的迭代算法可描述如下:   【算法】迭代法求方程组的根   { for (i=0;i   x=初始近似根;   do {   for (i=0;i   y=x;   for (i=0;i   x=gi(X);   for (delta=0.0,i=0;i   if (fabs(y-x)>delta) delta=fabs(y-x);   } while (delta>Epsilon);   for (i=0;i   printf(“变量x[%d]的近似根是 %f”,I,x);   printf(“\n”);   }   具体使用迭代法求根时应注意以下两种可能发生的情况:   (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;   (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。   递归   递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。   能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。   【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。   斐波那契数列为:0、1、1、2、3、……,即:   fib(0)=0;   fib(1)=1;   fib(n)=fib(n-1)+fib(n-2) (当n>1时)。   写成递归函数有:   int fib(int n)   { if (n==0) return 0;   if (n==1) return 1;   if (n>1) return fib(n-1)+fib(n-2);   }   递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。   在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。   在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。   由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。   【问题】 组合问题   问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1   (4)5、3、2 (5)5、3、1 (6)5、2、1   (7)4、3、2 (8)4、3、1 (9)4、2、1   (10)3、2、1   分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。   【程序】   # include   # define MAXN 100   int a[MAXN];   void comb(int m,int k)   { int i,j;   for (i=m;i>=k;i--)   { a[k]=i;   if (k>1)   comb(i-1,k-1);   else   { for (j=a[0];j>0;j--)   printf(“%4d”,a[j]);   printf(“\n”);   }   }   }   void main()   { a[0]=3;   comb(5,3);   }   【问题】 背包问题   问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。   设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。   对于第i件物品的选择考虑有两种可能:   (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。   (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。   按以上思想写出递归算法如下:   try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)   { /*考虑物品i包含在当前方案中的可能性*/   if(包含物品i是可以接受的)   { 将物品i包含在当前方案中;   if (i   try(i+1,tw+物品i的重量,tv);   else   /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   恢复物品i不包含状态;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (不包含物品i仅是可男考虑的)   if (i   try(i+1,tw,tv-物品i的价值);   else   /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   }   为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表:   物品 0 1 2 3   重量 5 3 2 1   价值 4 4 3 1   并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。   按上述算法编写函数和程序如下:   【程序】   # include   # define N 100   double limitW,totV,maxV;   int option[N],cop[N];   struct { double weight;   double value;   }a[N];   int n;   void find(int i,double tw,double tv)   { int k;   /*考虑物品i包含在当前方案中的可能性*/   if (tw+a.weight<=limitW)   { cop=1;   if (i   else   { for (k=0;k   option[k]=cop[k];   maxv=tv;   }   cop=0;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (tv-a.value>maxV)   if (i   else   { for (k=0;k   option[k]=cop[k];   maxv=tv-a.value;   }   }   void main()   { int k;   double w,v;   printf(“输入物品种数\n”);   scanf((“%d”,&n);   printf(“输入各物品的重量和价值\n”);   for (totv=0.0,k=0;k   { scanf(“%1f%1f”,&w,&v);   a[k].weight=w;   a[k].value=v;   totV+=V;   }   printf(“输入限制重量\n”);   scanf(“%1f”,&limitV);   maxv=0.0;   for (k=0;k find(0,0.0,totV);   for (k=0;k   if (option[k]) printf(“%4d”,k+1);   printf(“\n总价值为%.2f\n”,maxv);   }   作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。   【程序】   # include   # define N 100   double limitW;   int cop[N];   struct ele { double weight;   double value;   } a[N];   int k,n;   struct { int ;   double tw;   double tv;   }twv[N];   void next(int i,double tw,double tv)   { twv.=1;   twv.tw=tw;   twv.tv=tv;   }   double find(struct ele *a,int n)   { int i,k,f;   double maxv,tw,tv,totv;   maxv=0;   for (totv=0.0,k=0;k   totv+=a[k].value;   next(0,0.0,totv);   i=0;   While (i>=0)   { f=twv.;   tw=twv.tw;   tv=twv.tv;   switch(f)   { case 1: twv.++;   if (tw+a.weight<=limitW)   if (i   { next(i+1,tw+a.weight,tv);   i++;   }   else   { maxv=tv;   for (k=0;k   cop[k]=twv[k].!=0;   }   break;   case 0: i--;   break;   default: twv.=0;   if (tv-a.value>maxv)   if (i   { next(i+1,tw,tv-a.value);   i++;   }   else   { maxv=tv-a.value;   for (k=0;k   cop[k]=twv[k].!=0;   }   break;   }   }   return maxv;   }   void main()   { double maxv;   printf(“输入物品种数\n”);   scanf((“%d”,&n);   printf(“输入限制重量\n”);   scanf(“%1f”,&limitW);   printf(“输入各物品的重量和价值\n”);   for (k=0;k   scanf(“%1f%1f”,&a[k].weight,&a[k].value);   maxv=find(a,n);   printf(“\n选中的物品为\n”);   for (k=0;k   if (option[k]) printf(“%4d”,k+1);   printf(“\n总价值为%.2f\n”,maxv);   }   递归的基本概念和特点   程序调用自身的编程技巧称为递归( recursion)。   一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。   一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。   注意:   (1) 递归就是在过程或函数里调用自身;   (2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。

小哇 2019-12-02 01:25:19 0 浏览量 回答数 0

问题

如何构建机器学习算法?

问问小秘 2020-04-15 14:07:23 0 浏览量 回答数 1

回答

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法,即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法(Iterative Method)。 一般可以做如下定义:对于给定的线性方程组x=Bx+f(这里的x、B、f同为矩阵,任意线性方程组都可以变换成此形式),用公式x(k+1)=Bx(k)+f(括号中为上标,代表迭代k次得到的x,初始时k=0)逐步带入求近似解的方法称为迭代法(或称一阶定常迭代法)。如果k趋向无穷大时limx(k)存在,记为x*,称此迭代法收敛。显然x*就是此方程组的解,否则称为迭代法发散。 跟迭代法相对应的是直接法(或者称为一次解法),即一次性的快速解决问题,例如通过开方解决方程x +3= 4。一般如果可能,直接解法总是优先考虑的。但当遇到复杂问题时,特别是在未知量很多,方程为非线性时,我们无法找到直接解法(例如五次以及更高次的代数方程没有解析解,参见阿贝耳定理),这时候或许可以通过迭代法寻求方程(组)的近似解。 最常见的迭代法是牛顿法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。 利用迭代算法解决问题,需要做好以下三个方面的工作: 确定迭代变量 在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以顺推或倒推的方法来完成。 对迭代过程进行控制 在 什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数 是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需 要进一步分析出用来结束迭代过程的条件。 举例 例 1 :一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。 分析:这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 根据这个规律,可以归纳出下面的递推公式: u n = u(n - 1)× 2 (n ≥ 2) 对应 u n 和 u(n - 1),定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: cls x=1 for i=2 to 12 y=x*2 x=y next i print y end 例 2 :阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。 分析:根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 (x 的初值为第 15 次分裂之后的个数 2^20) 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: cls x=2^20 for i=1 to 15 x=x/2 next i print x end ps:java中幂的算法是Math.pow(2,20);返回double,稍微注意一下 例 3 :验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1。如此经过有限次运算后,总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 分析:定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1。用 QBASIC 语言把它描述出来就是: if n 为偶数 then n=n/2 else n=n*3+1 end if 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为:n=1。参考程序如下: cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 如果 n 为偶数,则调用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end 迭代法开平方: #include<stdio.h> #include<math.h> void main() { double a,x0,x1; printf("Input a:\n"); scanf("%lf",&a);//为什么在VC6.0中不能写成“scanf("%f",&a);”。 if(a<0) printf("Error!\n"); else { x0=a/2; x1=(x0+a/x0)/2; do { x0=x1; x1=(x0+a/x0)/2; }while(fabs(x0-x1)>=1e-6); } printf("Result:\n"); printf("sqrt(%g)=%g\n",a,x1); } 求平方根的迭代公式:x1=1/2*(x0+a/x0)。 算法:1.先自定一个初值x0,作为a的平方根值,在我们的程序中取a/2作为a的初值;利用迭代公式求出一个x1。此值与真正的a的平方根值相比,误差很大。 ⒉把新求得的x1代入x0中,准备用此新的x0再去求出一个新的x1. ⒊利用迭代公式再求出一个新的x1的值,也就是用新的x0又求出一个新的平方根值x1,此值将更趋近于真正的平方根值。 ⒋比较前后两次求得的平方根值x0和x1,如果它们的差值小于我们指定的值,即达到我们要求的精度,则认为x1就是a的平方根值,去执行步骤5;否则执行步骤2,即循环进行迭代。 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: ⑴ 选一个方程的近似根,赋给变量x0; ⑵ 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; ⑶ 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤⑵的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while (fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon); for (i=0;i printf(“变量x[%d]的近似根是 %f”,I,x); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: ⑴ 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; ⑵ 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 递归 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 斐波那契数列为:0、1、1、2、3、……,即: fib(0)=0; fib⑴=1; fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 写成递归函数有: int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问 题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算 fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib⑴和fib(0),分别能 立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib⑴和fib(0)后,返回得到fib⑵的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 【问题】 组合问题 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为:⑴5、4、3 ⑵5、4、2 ⑶5、4、1 ⑷5、3、2 ⑸5、3、1 ⑹5、2、1 ⑺4、3、2 ⑻4、3、1 ⑼4、2、1 ⑽3、2、1 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递 归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int a[MAXN]; void comb(int m,int k) { int i,j; for (i=m;i>=k;i--) { a[k]=i; if (k>1) comb(i-1,k-1); else { for (j=a[0];j>0;j--) printf(“%4d”,a[j]); printf(“\n”); } } } void main() { a[0]=3; comb(5,3); } 【问题】 背包问题 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并 保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达 到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止 当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 对于第i件物品的选择考虑有两种可能: ⑴ 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 ⑵ 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 按以上思想写出递归算法如下: try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) { /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) { 将物品i包含在当前方案中; if (i try(i+1,tw+物品i的重量,tv); else /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可男考虑的) if (i try(i+1,tw,tv-物品i的价值); else /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; } 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 物品 0 1 2 3 重量 5 3 2 1 价值 4 4 3 1 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 按上述算法编写函数和程序如下: 【程序】 # include # define N 100 double limitW,totV,maxV; int option[N],cop[N]; struct { double weight; double value; }a[N]; int n; void find(int i,double tw,double tv) { int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+a.weight<=limitW) { cop=1; if (i else { for (k=0;k option[k]=cop[k]; maxv=tv; } cop=0; } /*考虑物品i不包含在当前方案中的可能性*/ if (tv-a.value>maxV) if (i else { for (k=0;k option[k]=cop[k]; maxv=tv-a.value; } } void main() { int k; double w,v; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入各物品的重量和价值\n”); for (totv=0.0,k=0;k { scanf(“%1f%1f”,&w,&v); a[k].weight=w; a[k].value=v; totV+=V; } printf(“输入限制重量\n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是 从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选 解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在 候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。 对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int ; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.=1; twv tw=tw; twv tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.; tw=twv tw; tv=twv tv; switch(f) { case 1: twv.++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].!=0; } break; case 0: i--; break; default: twv.=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入限制重量\n”); scanf(“%1f”,&limitW); printf(“输入各物品的重量和价值\n”); for (k=0;k scanf(“%1f%1f”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\n选中的物品为\n”); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); }

云篆 2019-12-02 01:25:10 0 浏览量 回答数 0

回答

Java之JVM垃圾回收 内存结构以及垃圾回收算法前言:由于小组技术分享的需要,懂的不是很多所以我就找了这个我自己感兴趣的知识点给大家做个简单的介绍。由于是新人,算不了很懂,只是总结性的讲了些概念性的东西。给大家分享的同时,算是给自己做个笔记吧。作为Java语言的核心之一,JVM垃圾回收帮我们解决了让我们很头疼的垃圾回收问题。我们不需要像VC++一样,作为内存管理的统治者需要我们对我们分配的每一块内存进行回收,否则就会造成内存泄露问题。是不是只要有JVM存在我们就不会出现内存泄露问题,出现内存泄露问题我们又该怎么办,如果我们想提高我们程序的稳定性和其他性能我们能从什么地方下手!!!相信这些问题是我们程序过程中不可逾越的。了解JVM的内存分配及其相应的垃圾回收机制,不仅仅是可以了解底层的JVM运行机制,而且对于程序性能的优化和提升还是很有必要的。一、JVM内存分配区域结构图一从图一可以看出JVM中的内存分配包括PC Register(PC寄存器) JVM栈 堆(Heap) 方法区域(MethodArea)运行时常量池(RuntimeConstant Pool) 本地方法堆栈(NativeMethod Stacks),这几部分区域但是从程序员的角度来看我们只关注JVM Heap和JVM Stack,因为这两部分是直接关系程序运行期间的内存状态,所以我会主要介绍这两部分内存,其他的我只是给出了简单的一些概念性解释:PC Register(Program Counter 寄存器):主要作用是记录当前线程所执行的字节码的行号。方法区域(MethodArea):方法区域存放了所加载的类的信息(名称、修饰符等)、类中的静态变量、类中定义为final类型的常量、类中的Field信息、类中的方法信息,法区域也是全局共享的,它在虚拟机启动时在一定的条件下它也会被GC,当方法区域需要使用的内存超过其允许的大小时,会抛出OutOfMemory的错误信息。运行时常量池(RuntimeConstant Pool):存放的为类中的固定的常量信息、方法和Field的引用信息等,其空间从方法区域中分配。本地方法堆栈(NativeMethod Stacks):JVM采用本地方法堆栈来支持native方法的执行,此区域用于存储每个native方法调用的状态。JVM栈:主要存放一些基本类型的变量和对象的引用变量。JVM堆:用来存放由 new 创建的对象和数组Java 虚拟机的自动垃圾回收器来管理(注意数组也是对象,所以说数组也是存放在JVM堆中)。由于栈中存放的是主要存放一些基本类型的变量和对象的引用变量,所以当过了变量的作用区域或者是当程序运行结束后它所占用的内存会自动的释放掉,所以不用来关心,下面我们主要来说的是堆内存的分配以及回收的算法。二、JVM堆内存介绍工欲善其事,必先利其器。所以了解堆内存的内部结构是很必要的。在Jvm中堆空间划分为三个代:年轻代(Young Generation)、年老代(Old Generation)和永久代(Permanent Generation)。年轻带主要是动态的存储,年轻带主要储存新产生的对象,年老代储存年龄大些的对象,永久带主要是存储的是java的类信息,包括解析得到的方法、属性、字段等。永久带基本不参与垃圾回收。所以说我们说的垃圾回收主要是针对年轻代和年老代。图二年轻代又分成3个部分,一个eden区和两个相同的survior区。刚开始创建的对象都是放置在eden区的。分成这样3个部分,主要是为了生命周期短的对象尽量留在年轻带。当eden区申请不到空间的时候,进行minorGC,把存活的对象拷贝到survior。年老代主要存放生命周期比较长的对象,比如缓存对象。(经过IBM的一个研究机构研究数据表明,基本上80%-98%的对象都会在年轻代的Eden区死掉从而本回收掉,所以说真正进入到老年代的对象很少,这也是为什么MinorGC比MajorGC更加频繁的原因)具体JVM内存垃圾回收过程描述如下 :1、对象在Eden区完成内存分配2、当Eden区满了,再创建对象,会因为申请不到空间,触发minorGC,进行young(eden+1survivor)区的垃圾回收3、minorGC时,Eden不能被回收的对象被放入到空的survivor(Eden肯定会被清空),另一个survivor里不能被GC回收的对象也会被放入这个survivor,始终保证一个survivor是空的4、当做第3步的时候,如果发现survivor满了,则这些对象被copy到old区,或者survivor并没有满,但是有些对象已经足够Old,也被放入Old区 XX:MaxTenuringThreshold5、当Old区被放满的之后,进行fullGC补充: MinorGC:年轻代所进行的垃圾回收,非常频繁,一般回收速度也比较快。 MajorGC:老年代进行的垃圾回收,发生一次MajorGC至少伴随一次MinorGC,一般比MinorGC速度慢十倍以上。 FullGC:整个堆内存进行的垃圾回收,很多时候是MajorGC 以后就是堆内存结构已经大致的垃圾回收过程。三、对象分配原则1.对象优先分配在Eden区,如果Eden区没有足够的空间时,虚拟机执行一次Minor GC。2.大对象直接进入老年代(大对象是指需要大量连续内存空间的对象)。这样做的目的是避免在Eden区和两个Survivor区之间发生大量的内存拷贝(新生代采用复制算法收集内存)。3.长期存活的对象进入老年代。虚拟机为每个对象定义了一个年龄计数器,如果对象经过了1次Minor GC那么对象会进入Survivor区,之后每经过一次Minor GC那么对象的年龄加1,知道达到阀值对象进入老年区。4.动态判断对象的年龄。如果Survivor区中相同年龄的所有对象大小的总和大于Survivor空间的一半,年龄大于或等于该年龄的对象可以直接进入老年代。5.空间分配担保。每次进行Minor GC时,JVM会计算Survivor区移至老年区的对象的平均大小,如果这个值大于老年区的剩余值大小则进行一次Full GC,如果小于检查HandlePromotionFailure设置,如果true则只进行Monitor GC,如果false则进行Full GC。四、垃圾收集器作为JVM中的核心之一垃圾收集器,主要完成的功能包括:(1)发现无用信息对象;(2)回收被无用对象占用的内存空间,使该空间可被程序再次使用。所以说我们在实现垃圾收集器的同时就要实现两个算法一个是发现无用的对象第二就是回收该对象的内存。收集器主要分为引用计数器和跟踪收集器两种,Sun JDK中采用跟踪收集器作为GC实现策略。发现无用对象只要的实现算法包括引用计数法和根搜索算法,引用计数法主要是JVM的早期实现方法,因为引用计数无法解决循环引用的问题,所以现在JVM实现的主要是根搜索算法,引用计数法:堆中的每个对象对应一个引用计数器。当每一次创建一个对象并赋给一个变量时,引用计数器置为1。当对象被赋给任意变量时,引用计数器每次加1当对象出了作用域后(该对象丢弃不再使用),引用计数器减1,一旦引用计数器为0,对象就不可用从而可以被回收。 根搜索算法:通过一系列的名为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链(Reference Chain),当一个对象到GC Roots没有任何引用链相连(用图论的话来说就是从GC Roots到这个对象不可达)时,则证明此对象是不可用的。目前的收集器主要有三种:串行收集器:使用单线程处理所有垃圾回收工作,因为无需多线程交互,所以效率比较高并行收集器:对年轻代进行并行垃圾回收,因此可以减少垃圾回收时间。一般在多线程多处理器机器上使用并发收集器:可以保证大部分工作都并发进行(应用不停止),垃圾回收只暂停很少的时间,此收集器适合对响应时间要求比较高的中、大规模应用五、垃圾收集器的回收算法Copying算法:算法:复制采用的方式为从根集合扫描出存活的对象,并将找到的存活对象复制到一块新的完全未使用的空间中。 过程: 此算法把内存空间划为两个相等的区域,每次只使用其中一个区域。垃圾回收时,遍历当前使用区域,把正在使用中的对象复制到另外一个区域中。次算法每次只处理正在使用中的对象,因此复制成本比较小,同时复制过去以后还能进行相应的内存整理,不过出现“碎片”问题。当然,此算法的缺点也是很明显的,就是需要两倍内存空间。Mark-Sweep算法: 算法:标记-清除采用的方式为从根集合开始扫描,对存活的对象进行标记,标记完毕后,再扫描整个空间中未标记的对象,并进行回收。 过程: 第一阶段从引用根节点开始标记所有被引用的对象,第二阶段遍历整个堆,把未标记的对象清除。它停止所有工作,收集器从根开始访问每一个活跃的节点,标记它所访问的每一个节点。走过所有引用后,收集就完成了,然后就对堆进行清除(即对堆中的每一个对象进行检查),所有没有标记的对象都作为垃圾回收并返回空闲列表。Mark-Compact算法: 算法:标记阶段与“Mark-Sweep”算法相同,但在清除阶段有所不同。在回收不存活对象所占用的内存空间后,会将其他所有存活对象都往左端空闲的空间进行移动,并更新引用其对象指针。过程:此算法结合了“标记-清除”和“复制”两个算法的优点。也是分两阶段,第一阶段从根节点开始标记所有被引用对象,第二阶段遍历整个堆,把清除未标记对象并且把存活对象“压缩”到堆的其中一块,按顺序排放。此算法避免了“标记-清除”的碎片问题,同时也避免了“复制”算法的空间问题。Sun JDK GC策略:新生代算法实现:Copying,Copying,Copying旧生代算发实现:Mark-Sweep-Compact,Mark –Compact,Mark –Sweep!!六、JvisuaVM 工具如果我们想优化自己的程序,那么我们就必须清楚的了解不同代码程序所消耗的性能多少,作为JDK的一部分,这个工具给我们提供了很大的帮助。这个工具可以在JDK的bin目录下找到,功能很强大,可以注意利用

auto_answer 2019-12-02 01:56:35 0 浏览量 回答数 0
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 企业信息查询 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站