精华内容
下载资源
问答
  • 在我们生活中,算法无处不在

    算法无处不在

    在我们的生活中,算法无处不在。我们每天早上起来,刷牙、洗脸、吃早餐,都在算着时间,以免上班或上课迟到;去超市购物,在资金有限的情况下,考虑先买什么、后买什么,算算是否超额;在家中做饭,用什么食材、调料,做法、步骤,还要品尝一下咸淡,看看是否做熟。所以,不要说你不懂算法,其实你每天都在用!

    算法的定义

    写一个算法,求下面序列之和:

    当你看到这个题目时,你会怎么想?

                                                                                               算法(1-1)

    这段代码可以实现求和运算,但是为什么不这样算?

                                                                                                  算法(1-2)

    有的人看到这个代码后恍然大悟,原来可以这样啊?这不就是数学家高斯使用的算法吗?

    一共50 对数,每对之和均为101,那么总和为:

    (1+100)×50=5050

    1787 年,10 岁的高斯用了很短的时间算出了结果,而其他孩子却要算很长时间。

    可以看出,算法1-1需要运行n 次,如果n=100 00 00,就要运行100 00 00次,而算法1-2仅仅需要运行1 次!是不是有很大差别?

    我们通过计时器来看一下scratch用两种算法的不同耗时吧!

    cat代码:

    sam代码:

    cat耗时5.967秒,而sam详单于秒答几乎没有花费时间。

    高斯的方法我也知道,但遇到类似的题还是……我用的笨办法也是算法吗?

    答:是算法。

    算法是指对特定问题求解步骤的一种描述。

    算法只是对问题求解方法的一种描述,它不依赖于任何一种语言,既可以用自然语言、程序设计语言(C、C++、Java、Python 等)描述,也可以用流程图、框图来表示。

    算法的特点

    (1)有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能永不停止。

    (2)确定性:每条语句有确定的含义,无歧义。

    (3)可行性:算法在当前环境条件下可以通过有限次运算实现。

    (4)输入输出:有零个或多个输入,一个或多个输出。

    “好”算法的标准

    (1)正确性:正确性是指算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期的需求。

    (2)易读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。

    (3)健壮性:算法对非法数据及操作有较好的反应和处理。例如,在学生信息管理系统中登记学生年龄时,若将21 岁误输入为210 岁,系统应该提示出错。

    (4)高效性:高效性是指算法运行效率高,即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒钟能计算数亿次,因此不能用秒来具体计算算法消耗的时间,由于相同配置的计算机进行一次基本运算的时间是一定的,我们可以用算法基本运算的执行次数来衡量算法的效率。因此,将算法基本运算的执行次数作为时间复杂度的衡量标准。

    (5)低存储性:低存储性是指算法所需要的存储空间低。对于像手机、平板电脑这样的嵌入式设备,算法如果占用空间过大,则无法运行。算法占用的空间大小称为空间复杂度。

     

     

    展开全文
  • 最近,我参加了CSDN举办“从...在众多图书中,我选了《算法神探》,觉得这本书从名字上来看就比较有意思。拿到书之后,我分两次就把它读完了,可以毫不夸张地说,这是一本让你可以一口气就读完计算机科普类图书。

    最近,我参加了CSDN举办的“从高考到程序员”征文活动,获赠了一本图书。在众多图书中,我选了《算法神探》,觉得这本书从名字上来看就比较有意思。拿到书之后,我分两次就把它读完了,可以毫不夸张地说,这是一本让你可以一口气就读完的计算机科普类图书。
    这里写图片描述
    首先说一下这本书的大致情况。本书是Google首席工程师Jeremy Kubica的作品(当然,这个人我也没听说过),翻译者是啊哈磊和李嘉浩。对于啊哈磊这个人,IT行业的人或许听说过,他写过一本书叫《啊哈!算法》,读者挺多的。《算法神探》这本书一共二百多页,29个章节,几乎每章都涉及到一种算法或数据结构。在跌宕起伏的故事情节中,我们可以领略到算法之美。

    本书的故事情节大概是这样的:一个王国的警局总部遭遇了一起盗窃案,警长请一位被解雇的前探员Frank Runtime来将这个案子调查清楚;之所以要请一位被解雇的探员,是因为他是一位老练的私家侦探,并且非常擅长搜索;Frank Runtime利用他的搜索算法搜查走私的船、跟踪间谍、逃离监狱、开锁,并在最后揭发了一桩暗藏在深处的阴谋。这本书的每一章都是一个故事片段,同时会引入一个新的算法概念。为了加深大家对算法基础知识的了解,在每章的结尾处都会回顾并详细描述本章内出现的算法知识。

    按照章节顺序,在本书中出现的算法或数据结构包括:穷举搜索、数组、字符串、二分搜索、广度优先搜索、深度优先搜索、栈、队列、并行算法、迭代加深、逆向索引、二叉搜索树、trie树、最佳优先搜索、优先队列、启发式搜索、堆。下面是对这些概念的简单解释:

    穷举搜索:在整个搜索空间内尝试每一种可能性。
    数组:一个数组就像一排箱子一样,每个箱子可以存储一条信息。
    字符串:由一系列字符组成,这些字符可以是字母、数字、符号或空格。
    二分搜索:其工作原理是不断地将搜索空间分成两半,并且把搜索空间限制在其中的一半中。
    广度优先搜索:是一个按顺序依次尝试可能的搜索选项的算法,它每次都会选择尝试首先发现的但还没有尝试过的选项。
    深度优先搜索:优先考虑最近新遇到的搜索状态,它会沿着一条路往下走,直到遇到目标状态,或者是一条死路。
    栈:是一个后入先出的数据结构。
    队列:是一个先入先出的数据结构。
    并行算法:将一个问题分成数个小块,并同时在这些小块上执行计算,最后再将结果组合起来。
    迭代加深:是深度优先搜索的一种改版,它限制了每一次搜索的深度,在第k轮搜索的时候,这个算法会执行一次深度限制为k的深度优先搜索。
    逆向索引:它和书的索引类似,对于每一个值,逆向索引可以告诉你这个值在数据中的哪些地方出现过。
    二叉搜索树:它是一种数据结构,它存储信息的方式和二叉搜索中使用信息的方式类似,树中的每一个节点存放一个值,并且每个节点最多有两个子节点,左子节点中存放的值都比当前节点中的值小,右子节点中存放的值都比当前节点中的值大。
    trie树:是基于树的数据结构,用户可以很方便地通过某个字符串的前缀来搜索到目标字符串。
    最佳优先搜索:是基于某种估值分数或者评价函数来选择接下来探索哪个状态的算法。
    优先队列:它让你能插入数据,然后按特定的顺序删除数据。
    启发式搜索:依据经验来帮助算法快速达到目标。
    堆:是基于二叉搜索树的数据结构,它的每个节点与其子节点之间需要时刻维持有序关系;具体而言,对于最大堆,树中的任意一个节点的值都要大于(或等于)其下面的所有节点。

    看完了这本书,我的体会有这几个:
    第一,一本好的书就是要让其内容具备趣味性,让读者能够有继续读下去直到读完(甚至读好几遍)的理由。
    第二,算法不光只是存在于计算机科学的研究和实践中,在我们的生活中,算法也是无处不在的。大到做一个人生中的重要决定,小到买菜购物,背后的指导思想都是算法。
    第三,解决一个问题的方法往往不止一种,我们要根据实际情况选择合适的方法,但这个方法可能不是最优的。

    《算法神探》,一本具备趣味性和知识性的计算机科普读物,推荐给大家阅读!


    欢迎大家扫码加入我的小蜜圈:
    这里写图片描述

    展开全文
  • 先进的算法工具有时候对软件系统影响很大——减少开发时间,同时使执行速度更快。算法与其他那些深奥的思想一样重要,但在更一般的编程层面上具有更重要的影响。在《啊哈!灵机一动》一书中(本文的标题就借鉴了它),...

    研究算法给实际编程的程序员带来许多好处。先进的算法工具有时候对软件系统影响很大——减少开发时间,同时使执行速度更快。

    算法与其他那些深奥的思想一样重要,但在更一般的编程层面上具有更重要的影响。在《啊哈!灵机一动》一书中(本文的标题就借鉴了它),Martin Gardner1描述了深得我心的一个思想:“看起来很困难的问题也可以有一个简单的、意想不到的答案。”与高级的方法不同,算法的啊哈!灵机一动 并非只有在大量的研究以后才能出现;任何愿意在编程之前、之中和之后进行认真思考的程序员都有机会捕捉到这灵机一动。

    1 三个问题

    好了,泛泛的话讲得够多啦。本文将围绕三个小问题展开。在继续阅读以前,请先试着解决它们。

    A.给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数(在文件中至少缺失一个这样的数——为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节的内存,又该如何解决该问题?

    B.将一个n元一维向量向左旋转2i个位置。例如,当n=8且i=3时,向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间,在正比于n的时间内完成向量的旋转?

    C.给定一个英语字典,找出其中的所有变位词集合。例如,“pots”、“stop”和“tops”互为变位词,因为每一个单词都可以通过改变其他单词中字母的顺序来得到。

    2 无处不在的二分搜索

    我想到的一个数在1到100之间,你来猜猜看。50?太小了。75?太大了。如此,游戏进行下去,直到你猜中我想到的数为止。如果我的整数位于1到n之间,那么你可以在次之内猜中。如果n是1 000,10次就可以完成;如果n是100万,则最多20次就可以完成。

    这个例子引出了一项可以解决众多编程问题的技术:二分搜索。初始条件是已知一个对象存在于一个给定的范围内,而一次探测操作可以告诉我们该对象是否低于、等于或高于给定的位置。二分搜索通过重复探测当前范围的中点来定位对象。如果一次探测没有找到该对象,那么我们将当前范围减半,然后继续下一次探测。当找到所需要的对象或范围为空时停止。

    在程序设计中二分搜索最常见的应用是在有序数组中搜索元素。在查找项50时,算法进行如下探测。

    9285921f561f727f4f0c49521f94eaad.png

    众所周知,二分搜索程序要正确运行很困难。

    顺序搜索在搜索一个具有n个元素的表时,平均需要进行n/2次比较,而二分搜索仅仅进行不超过次的比较就可以完成。这在系统性能上会造成巨大的差异。下面的故事来自于《ACM通讯》的实例研究“TWA Reservation System”。

    我们有一个执行线性搜索的程序,可以在1秒钟内对一块非常巨大的内存块完成100次搜索。随着网络的增长,处理每条消息所需的平均CPU时间上升了0.3毫秒,这对我们来说是巨大的变化。我们发现问题的根源是线性搜索。把程序改为使用二分搜索以后,该问题消失了。

    我在许多系统中也遇到过相同的问题。程序员在开始的时候使用简单的顺序搜索数据结构,这在开始的时候通常都足够快。当搜索变得太慢的时候,对表进行排序并使用二分搜索通常可以消除瓶颈。

    但是二分搜索的故事并没有在快速搜索有序数组这里终止。Roy Weil将该技术应用于清理一个约1000行的输入文件,其中仅包含一个错误行。很不幸,肉眼看不出错误行。只能通过在程序中运行文件的一个(起始)部分并且观察到离奇错误的答案来辨别,这将会花费几分钟的时间。他的前任调试人员试图通过每次运行整个程序中的少数几行程序来找出错误行,但只在取得解决方案的道路上前进了一点点。Weil是如何仅仅运行10次程序就找到罪魁祸首的呢?

    经过前面的热身,我们现在来攻克问题A。输入为顺序文件(考虑磁带或磁盘——虽然磁盘可以随机读写,但是从头至尾读取文件通常会快得多)。文件包含最多40亿个随机排列的32位整数,而我们需要找出一个不存在于该文件中的32位整数。(至少缺少一个整数,因为一共有232也就是4 294 967 296个这样的整数。)如果有足够的内存,可以采用位图技术,使用536 870 912个8位字节形成位图来表示已看到的整数。然而,该问题还问到在仅有几百个字节内存和几个稀疏顺序文件的情况下如何找到缺失的整数?为了采用二分搜索技术,就必须定义一个范围、在该范围内表示元素的方式以及用来确定哪一半范围存在缺失整数的探测方法。如何来实现呢?

    我们采用已知包含至少一个缺失元素的一系列整数作为范围,并使用包含所有这些整数在内的文件表示这个范围。灵机一动的结果是通过统计中间点之上和之下的元素来探测范围:或者上面或者下面的范围具有至多全部范围的一半元素。由于整个范围中有一个缺失元素,因此我们所需的那一半范围中必然也包含缺失的元素。这些就是解决该问题的二分搜索算法所需要的主要想法。在翻阅答案查看Ed Reingold是如何做的以前,请尝试将这些想法组织起来。

    对于二分搜索技术在程序设计中的应用来说,这些应用仅仅是皮毛而已。求根程序使用二分搜索技术,通过连续地对分区间来求解单变量方程式(数值分析家称之为对分法)。当选择算法区分出一个随机元素以后,就对该元素一侧的所有元素递归地调用自身(这是一种随机二分搜索)。其他使用二分搜索的地方包括树数据结构和程序调试(当程序没有任何提示就意外中止时,你会从源代码中哪一部分开始探测来定位错误语句呢?)。在上述的每个例子中,分析程序并对二分搜索算法做些许修改,可以带给程序员功能强大的啊哈!灵机一动。

    3 基本操作的威力

    二分搜索是许多问题的解决方案,下面研究一个有几种解决方案的问题。问题B仅使用几十个字节的额外空间将一个n元向量x在正比于n的时间内向左旋转i个位置。该问题在应用程序中以各种不同的伪装出现。在一些编程语言中,该功能是向量的一个基本操作。更重要地,旋转操作对应于交换相邻的不同大小的内存块:每当拖动文件中的一块文字到其他地方时,就要求程序交换两块内存中的内容。在许多应用场合下,运行时间和存储空间的约束会很严格。

    可以通过如下方式解决该问题:首先将x的前i个元素复制到一个临时数组中,然后将余下的n-i个元素向左移动i个位置,最后将最初的i个元素从临时数组中复制到x中余下的位置。但是,这种办法使用的i个额外的位置产生了过大的存储空间的消耗。另一种方法是定义一个函数将x向左旋转一个位置(其时间正比于n)然后调用该函数i次。但该方法又产生了过多的运行时间消耗。

    要在有限的资源内解决该问题,显然需要更复杂的程序。有一个成功的方法有点像精巧的杂技动作:移动x[0]到临时变量t,然后移动x[i]至x[0],x[2i]至x[i],依此类推(将x中的所有下标对n取模),直至返回到取x[0]中的元素,此时改为从t取值然后终止过程。当i为3且n为12时,元素按如下顺序移动。

    00a1b46ad76d9e04f14b3c7baee876bb.png

    如果该过程没有移动全部元素,就从x[1]开始再次进行移动,直到所有的元素都已经移动为止。

    从另外一面考察这个问题,可以得到一个不同的算法:旋转向量x其实就是交换向量ab的两段,得到向量ba。这里a代表x中的前i个元素。假设a比b短,将b分为bl和br,使得br具有与a相同的长度。交换a和br,也就将ablbr转换为brbla。序列a此时已处于其最终的位置,因此现在的问题就集中到交换b的两部分。由于新问题与原来的问题具有相同的形式,我们可以递归地解决之。使用该算法可以得到优雅的程序,但是需要巧妙的代码,并且要进行一些思考才能看出它的效率足够高。

    问题看起来很难,除非最终获得了啊哈!灵机一动:我们将问题看做是把数组ab转换成ba,同时假定我们拥有一个函数可以将数组中特定部分的元素求逆。从ab开始,首先对a求逆,得到arb,然后对b求逆,得到arbr。最后整体求逆,得到(arbr)r。此时就恰好是ba。于是,我们得到了如下用于旋转的代码,其中注释部分表示abcdefgh向左旋转三个位置以后的结果。

    reverse(0,i-1)    /* cbadefgh */reverse(i,n-1)    /* cbahgfed */reverse(0,n-1)    /* defghabc */

    Doug McIlroy3给出了将十元数组向上旋转5个位置的翻手例子。初始时掌心对着我们的脸,左手在右手上面。

    20f46b3ece67646f3989970f3611bd56.png

    翻转代码在时间和空间上都很高效,而且代码非常简短,很难出错。Brian Kernighan4和P. J. Plauger5在其1981年出版的Software Tools in Pascal一书中,就使用该代码在文本编辑器中实现了行的移动。Kernighan报告称在第一次执行的时候程序就正确运行了,而他们先前基于链表的处理相似任务的代码则包含几个错误。该代码用在几个文本处理系统中,其中包括我最初用于录入本章内容的文本编辑器。Ken Thompson6在1971年编写了编辑器和这种求逆代码,甚至在那时就主张把该代码当作一种常识。

    4 排序

    现在我们来讨论问题C。给定一本英语单词字典(每个输入行是一个由小写字母组成的单词),要求找出所有的变位词分类。研究这个问题可以举出许多理由。首先是技术上的:获得这个问题的解决方案需要既具有正确的视角又能使用正确的工具。第二个理由更具有说服力:你总不想成为聚会中唯一一个不知道“deposit”、“dopiest”、“posited”和“topside”是变位词的人吧?

    解决这个问题的许多方法都出奇地低效和复杂。任何一种考虑单词中所有字母的排列的方法都注定了要失败。单词“cholecystoduodenostomy”(我的字典中单词“duodenocholecystostomy”的一个变位词)有22!种排列,少量的乘法运算表明22! ≈ 1.1241021。即使假设以闪电一样的速度每百亿分之一秒执行一种排列,这也要消耗1.1109 秒。经验法则“π秒就是一个纳世纪”指出1.1109是数十年。而比较所有单词对的任何方法在我的机器上运行至少要花费一整夜的时间——在我使用的字典里有大约230 000个单词,而即使是一个简单的变位词比较也将花费至少1 微秒的时间,因此,总时间估算起来就是

    230 000单词230 000比较/单词1微秒/比较=52 900106微秒=52 900秒≈14.7小时

    你能够找到同时避免上述缺陷的方法吗?

    我们获得的啊哈!灵机一动 就是标识字典中的每一个词,使得在相同变位词类中的单词具有相同的标识。然后,将所有具有相同标识的单词集中在一起。这将原始的变位词问题简化为两个子问题:选择标识和集中具有相同标识的单词。在进一步阅读之前,先好好想想这些问题。

    对第一个问题,我们可以使用基于排序的标识7:将单词中的字母按照字母表顺序排列。“deposit”的标识就是“deiopst”,这也是“dopiest”和其他任何在该类中的单词的标识。要解决第二个问题,我们将所有的单词按照其标识的顺序排序。我所知道的关于该算法的最好描述就是Tom Cargill的翻手表示:先用一种方式排序(水平翻手),再用另一种方式排序(垂直翻手)。

    5 原理

    排序 排序最显而易见的用处是产生有序的输出,该输出既可以是系统规范要求的一部分,也可以是另一个程序(也许是一个二分搜索程序)的前期准备工作。但是在变位词问题中,排序并不是关注的焦点。排序是为了将相等的元素(本例中为标识)集中到一起。这些标识产生了另外一个排序应用:将单词内字母排序使得同一个变位词类中的单词具有标准型。通过给每条记录添加一个额外的键,并按照这些键进行排序,排序函数可以用于重新排列磁盘文件中的数据。在第三部分,我们还会多次回顾排序这个主题。

    二分搜索 该算法在有序表中查找元素时极为高效,并且可用于内存排序或磁盘排序。唯一的缺陷就是整个表必须已知并且事先排好序。基于该简单算法的思想在许多应用程序中都有应用。

    标识 当使用等价关系来定义类时,定义一种标识使得类中的每一项都具有相同的标识,而该类以外的其他项则没有该标识,这是很有用的。对单词中的字母排序可以产生一个用于变位词类的标识。其他标识通过排序给出。然后使用一个计数来代表重复的次数(于是标识“mississippi”可以写成“i4m1p2s4”或将1省略——“i4mp2s4”)。也可以使用一个包含26个整数的数组来标识每个字母出现的次数。标识的其他应用包括:美国联邦调查局用来索引指纹的方法,以及用来识别读音相同但是拼写不同的名字的Soundex启发式方法:

    3def47a1fa627ef05fa8b7052ad8a972.png

    Knuth8在其The Art of Computer Programming, Volume 3: Sorting and Sear ching9一书的描述了Soundex方法。

    问题定义。确定用户的真实需求是程序设计的根本。本文的中心思想是问题定义的下一步:使用哪些基本操作来解决问题?在每个例子中,啊哈!灵机一动都定义了一个新的基本操作使得问题得到简化。

    问题解决者的观点。优秀程序员都有点懒:他们坐下来并等待灵机一动的出现而不急于使用最开始的想法编程。当然,这必须通过在适当的时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握,这只能来源于解决问题和反思答案所获得的经验。

    6 习题

    1.考虑查找给定输入单词的所有变位词问题。仅给定单词和字典的情况下,如何解决该问题?如果有一些时间和空间可以在响应任何查询之前预先处理字典,又会如何?

    2.给定包含4 300 000 000个32位整数的顺序文件,如何找出一个出现至少两次的整数?

    3.前面涉及了两个需要精巧代码来实现的向量旋转算法。将其分别作为独立的程序实现。在每个程序中,i和n的最大公约数如何出现?

    4.几位读者指出,既然所有的三个旋转算法需要的运行时间都正比于n,杂技算法的运行速度显然是求逆算法的两倍。杂技算法对数组中的每个元素仅存储和读取一次,而求逆算法需要两次。在实际的计算机上进行实验以比较两者的速度差异,特别注意内存引用位置附近的问题。

    5.向量旋转函数将向量ab变为ba。如何将向量abc变为cba?(这对交换非相邻内存块的问题进行了建模)。

    6.20世纪70年代末期,贝尔实验室开发出了“用户操作的电话号码簿辅助程序”,该程序允许雇员使用标准的按键电话在公司电话号码簿中查找电话号码。

    8b60a01b73423cc80d5cdd4c96b37bf4.png

    要查找该系统设计者的名字Mike Lesk10,可以按“LESKM”(也就是“53756”),随后,系统会输出他的电话号码。这样的服务现在随处可见。该系统中出现的一个问题是,不同的名字有可能具有相同的按键编码。在Lesk的系统中发生这种情况时,系统会询问用户更多的信息。给定一个大的名字文件(例如标准的大城市电话号码簿),如何定位这些“错误匹配”呢?(当Lesk在这种规模的电话号码簿上做实验时,他发现错误匹配发生的概率仅仅是0.2%。)如何实现一个以名字的按键编码为参数,并返回所有可能的匹配名字的函数?

    7.在20世纪60年代早期,Vic Vyssotsky与一个程序员一起工作,该程序员需要转置一个存储在磁带上的4 000×4 000的矩阵(每条记录的格式相同,为数十个字节)。他的同事最初提出的程序需要运行50个小时。Vyssotsky如何将运行时间减少到半小时呢?

    8.[J. Ullman]给定一个n元实数集合、一个实数t和一个整数k,如何快速确定是否存在一个k元子集,其元素之和不超过t?

    9.顺序搜索和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时,需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间?

    10.某一天,一个新研究员向托马斯·爱迪生报到。爱迪生要求他计算出一个空灯泡壳的容积。在使用测径仪和微积分进行数小时的计算后,这个新员工给出了自己的答案——150 cm3。而爱迪生在几秒钟之内就计算完毕并给出了结果“更接近155”。他是如何实现的呢?

    7 变位词程序的实现(边栏)

    我的变位词程序按三个阶段的“管道”组织,其中一个程序的输出文件作为下一个程序的输入文件。第一个程序标识单词,第二个程序排序标识后的文件,而第三个程序将这些单词压缩为每个变位词类一行的形式。下面是一个仅有6个单词的字典的处理过程。

    64b6c6bc40f8a57132fbbaeae8a303b2.png

    输出包括三个变位词类。

    下面的C语言sign程序假定没有超过100个字母的单词,并且输入文件仅包含小写字母和换行符。(因此我使用了一个一行的命令对字典进行预处理,将其中的大写字母改为小写字母。)

    int charcomp(char *x, char *y) { return *x - *y;}#define WORDMAX 100int main(void){   char word[WORDMAX], sig[WORDMAX];    while (scanf("%s", word) !=EOF) {        strcpy(sig, word);        qsort(sig, strlen(sig), sizeof(char), charcomp);        printf("%s %s", sig, word);    }    return 0;}

    while循环每次读取一个字符串到word中,直至文件末尾为止。strcpy函数复制输入单词到单词sig中,然后调用C标准库函数qsort对单词sig中的字母进行排序(参数是待排序的数组、数组的长度、每个待排序项的字节数以及比较两个项的函数名。在本例中,待比较项为单词中的字母)。最后,printf语句依次打印标识、单词本身和换行符。

    系统sort程序将所有具有相同标识的单词归拢到一起。squash程序在同一行中将其打印出来。

    int main(void){  char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX];   int linenum = 0;     strcpy(oldsig, "");   while (scanf("%s %s", sig, word) != EOF) {       if (strcmp(oldsig, sig) !=0 && linenum >0)          printf("");       strcpy(oldsig, sig);       linenum++;       printf("%s ", word);   }   printf("");   return 0;}

    大部分工作都是使用第二个printf语句来完成的。对每一个输入行,该语句输出第二个字段,后面跟一个空格。if语句捕捉标识之间的差异。如果sig与oldsig(其上一次的值)不同,那么就打印换行符(文件中的第一条记录除外)。最后一个printf输出最后一个换行符。

    在使用小输入文件对这些简单部分进行测试后,我通过下面的命令构建了变位词列表:

    sign gramlist

    该命令将文件dictionary输入到程序sign,连接sign的输出至sort,连接sort的输出至squash,并将squash的输出写入文件gramlist。程序的运行时间为18秒:sign用时4秒、sort用时11秒而squash用时3秒。

    我在一个包含230 000个单词的字典上运行了该程序。然而,不包括众多的-s和-ed后缀。以下是一些很有趣的变位词类。

    subessential suitablenesscanter creant cretan nectar recant tanrec trancecaret carte cater crate creat creta react recta tracedestain instead sainted satinedadroitly dilatory idolatry least setal slate stale steal stela talesreins resin rinse risen serin sirenconstitutionalism misconstitutional

    1Martin Gardner(1914—),美国著名的科普作家,主持《科学美国人》的数学游戏专栏25年,写作了大量文章和图书,有世界影响。——编者注

    2即循环移位。——审校者注

    3 Doug McIlroy(1932—),著名计算机科学家,美国工程院院士,现为达特茅斯学院兼职教授。他于1968年第一个提出了软件组件的概念。他参与设计了PL/I和C++语言、Multics和Unix操作系统。Unix上许多工具是他开发的,包括diff、echo、sort、spell和join等,管道实现也由他首创。他曾长期担任贝尔实验室计算技术研究部主任,并曾任ACM图灵奖主席。——编者注

    4 Brian Kernighan(1942—)著名计算机科学家,现为普林斯顿大学教授。他与人合作创造了Awk和AMPL编程语言,对Unix和C语言的设计也有很大贡献。他还与人合写了多部计算机名著,包括与Ritchie合著的The C Programming Language。——编者注

    5 P. J. Plauger,著名C/C++语言专家,现为著名标准库开发商Dinkumware总裁。他曾担任ISO C标准委员会负责人,著有名著《C标准库》(中文版由人民邮电出版社出版)。——编者注

    6 Ken Thompson(1943—),著名计算机科学家,1983年图灵奖得主。现为Google杰出工程师。他是Unix操作系统的主要设计者,并设计了C语言的前身B语言。——编者注

    7 该变位词算法是由许多人各自独立发现的,至少可以追溯到20世纪60年代中期。

    8 Don Knuth(1938—),中文名高德纳,著名计算机科学家,斯坦福大学荣休教授。因对算法分析和编程语言设计领域的贡献获1974年图灵奖。他是名著The Art of Computer Programming的作者,设计了TEX排版系统。——编者注

    9 该书第2版英文影印版已由清华大学出版社引进出版,中文书名《计算机程序设计艺术 第3卷 排序和查找》,中译版已由国防工业出版社出版,中文书名《计算机程序设计艺术 第3卷 排序与查找》。——编者注

    10 Mike Lesk,著名程序员,ACM会士,美国工程院院士,现任Rutgers大学教授兼系主任。他在贝尔实验室工作期间开发了大量工具,包括lex、uucp和stdio.h的前身。他领导了美国NSF数字图书馆计划,该计划支持了斯坦福大学搜索引擎研究项目,促生了Google。——编者注


    本文节选自《编程珠玑(第2版•修订版)》

    6144ee4ecd2140707aaa4b41ae95aae8.png

    内容简介

    本书是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程生涯中至关重要的。本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序,对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述,为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值。

    展开全文
  • Knowledge/defmix( ):本期收录新增20+NO.35#机器学习##实验课#本实验通过对糖尿病指标数值和患者性别预测,带领进行入门练习,以及总结思考。实验表明了:数...

    Knowledge

    / def mix( ):

    本期收录

    新增20+

    NO. 35

    #机器学习##实验课#

    本实验通过对糖尿病指标数值和患者性别的预测,带领进行入门练习,以及总结思考。

    实验表明了:

    数据决定了机器学习的上限,

    而算法尽可能逼近这个上限。


    #AI教练##体育#

    在判断球员的位置和运动方向后,对赛场的情况进行抽象建模,结合过往球赛的训练数据,通过AI算法给出战术建议。

    #设计##字体##智能#

    Fontjoy ,一键自动匹配同性质又有所区别的字体。能帮助设计师们提升筛选字体效率的同时,也会带来一定的惊喜感,提供源源不断的灵感。

    原理:https://fontjoy.com/pairing/

    开源:https://github.com/Jack000/fontjoy

    #图像重建##超分辨率##工具#

    AI技术产品化,一项技术就是一款产品。

    从观测到的低分辨率图像重建出相应的高分辨率图像,在监控设备、卫星图像和医学影像等领域都有重要的应用价值。

    https://icons8.com/upscaler

    #社交##推荐系统##人格分析#

    基于用户在社交媒体上发布帖子等行为数据,来预测一个人的性格。

    在内向、直觉、思维和感知能力的维度将一个人分为16 种不同的个性。

    - 全文结束 -

    转发朋友圈后截图

    加小编微信领取电子书

    《AI+Architecture Towards a New Approach》 

    Harvard university ai architecture thesis

    欢迎一起来探索未知世界

    添加小编邀您加入“AI训练营”社群

    已连续持续更新 35*7

    MixLab     上海     北京     深圳     广州

    更多资料请查阅:Mix+ 人工智能专刊   ????

    每期由mixlab社区精选、收录人工智能的相关内容。包括AI产品、AI技术、AI场景、AI投资事件、AI的思维方式等。MIX的主题包括:AR、VR、计算设计、计算广告、智能设计、智能写作、虚拟偶像等。

    付费加入星球后,即可免费加入科技前沿外刊群:《新科学家杂志》、《英国金融时报》、《华尔街日报》、《经济学人》、《纽约时报》、《泰晤士报》等当日最新外刊。

    展开全文
  • 迷茫的旅行商:一个无处不在的计算机算法问题,高清原版电子书,非扫描版。
  • 《迷茫的旅行商:一个无处不在的计算机算法问题》概述了旅行商问题的起源和历史,并阐述了其许多重要的应用范围,如基因组测序、计算机处理器设计、音乐整理、行星寻找,等等。此外还探讨了人类如何在不借助计算机的...
  • 《迷茫的旅行商: 一个无处不在的计算机算法问题》概述了旅行商问题的起源和历史,并阐述了其许多重要的应用范围,如基因组测序、计算机处理器设计、音乐整理、行星寻找,等等。此外还探讨了人类如何在不借助计算机的...
  • 副标题: 一个无处不在的计算机算法问题 原作名: In pursuit of the traveling salesman:Mathematics at the limits of computation 译者: 隋春宁 内容简介 · · · · · · 假设一名旅行商打算拜访一张城市列表中...
  • 假设一名旅行商打算拜访一张城市列表中所有城市,每座城市只去一次,最后回到出发地。要怎么走才能让路线最短呢?这就是旅行商问题,乍一听很简单,在应用数学界却是一道研究极其热烈难题,时至今日仍无人能解。...
  • 优化算法 无处不在

    千次阅读 2015-04-17 15:51:45
    一:起因 (0)优化算法...(1)优化算法无处不在 —— 实际生活中 物资调配,一定生产资料如何得到最大产出,一定投资如何得到最佳收益等等,都可以转化为最优化问题求解;就连我们平常生活中
  • 作者:WilliamJ.Cook 本书概述了旅行商问题起源和历史, 并阐述了其许多重要应用范围, 如基因组测序、计算机处理器设计、音乐整理、行星寻找,等等。此外还探讨了人类如何在不借助计算机
  • TSP问题总结,能够帮助理解TSP问题前身及发展,对于初学者帮助较大
  • 迷茫的旅行商 一个无处不在的计算机算法问题-高清-完整目录-2013年10月
  • 注意:结果是顺序排序后第 K 个最大元素,而不是第 K 个不同最大元素。 示例 输入:A=[3, 7, 1, 6, 9, 1, 2], K=4 输出:6 答案解析 这道题目实际就是数组排序变种。只要将数组排序好,就能找到对应值...
  • 互联网无处不在的“推荐算法”解析摘要: 数据显示,三分之一的用户会根据电子商务网站的推荐买东西,这是任何广告都不可能做到的成绩。媒体上播放的大众化广告对消费者的影响已经越来越低,于是有人做出预见——个性...
  • 推荐算法无处不在

    2014-04-17 20:17:27
    大家现在一定有很深体会:当我们在baidu上搜索过一个产品后,以后不管到哪里有广告页面都会弹出那件产品广告。如我写过一篇博文【2分钟问卷】海大在校学生计算机使用、学习习惯情况调查(6题-2分钟),里面...
  • 4.3.4 翻煎饼、比尔·盖茨和大步搜索LKH算法 93 4.4 借鉴物理和生物思想 95 4.4.1 局部搜索与爬山算法 95 4.4.2 模拟退火算法 97 4.4.3 链式局部最优化 97 4.4.4 遗传算法 99 4.4.5 蚁群算法 101 ...
  • 我们知道,目前linux内核使用调度算法是CFS(Completely Fair Scheduler:完全公平调度程序),它作者是Ingo Molnar,Ingo Molnar本人也是linux内核调度模块负责人。 但在CFS调度算法引入之前,linux使用...
  • 我们一起走入阿里技术,探索云计算,寻找无处不在的算法与机器智能。进入算法应用的新蓝海。看AI如何落地,改变世界!
  • 请查看原文:   ...   ...在我读严蔚敏版的《数据结构》的时候,...也让我明白了一个道理,在设计好的算法之前,一定要设计好的数据结构,当你设计了好的数据结构之后,反而会为你写算法有很大的帮助,这是我深有体...
  • WOT,Word Of Tech峰会,是由51CTO重磅打造高端技术盛会,关注趋势与变革,洞察创新与实践,推动发展与创新,搭建技术与思想自由交流平台
  • 主宰世界十大算法

    2016-10-02 01:05:05
    但是,相比于其他算法,其中有一些算法更大程度上改变并控制着我们的世界——本文列举了其中十种最为重要的算法。 在正式介绍算法内容之前,让我们来迅速复习一些基本内容。虽然,没有明确的定义,但是计算机科学家...
  • 既然要用到并且用好subword,这里就重点捋一遍关于subword的算法以及几个开源的实现。1.word、subword和character在神经机器翻译中,通常有一个固定的词表,并且模型的训练和预测都非常依赖这个词表。在神经网络的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 754
精华内容 301
关键字:

无处不在的算法