现在的位置: 首页 > 综合 > 正文

西邮Linux兴趣小组13级纳新免试题浅析(下)

2019年05月18日 ⁄ 综合 ⁄ 共 2575字 ⁄ 字号 评论关闭

        哈哈 , 继续坚持哦 ! 到了第三关了, 这关考验你的耐心~观察。 好了 , 不多废话了。看看吧 !~!~

        上一关提交了key之后,会出来这样一个网页 :

       

        Original:原始的(PS:小编的英语不敢直言(太水)) 后面有一个串, Sorted:排序了的, 看来和排序有关了。下面估计又让我们提交什么东西。暂时没有头绪, 挖掘信息,咱们来看看网页源码:

       

        看来这里让提交这6个字符串对应使用了哪个排序算法。 我了个神, 这么多,很多都没有见过。但是何不从简单开始呢。从我们最熟悉的冒泡开始。好好观察一下这6个串,并不是完全排序的,我们发现第三个串只是前两个发生了变化,多刷新几次,找到规律,这个应该是一次简单插入排序。从首开始找插入位置。可以自己写一个冒泡试试对这个串进行一次排序,发现第一个串是冒泡排序,一次冒泡将最大的沉底。写一个简单选择排序排一排, 发现第二个串是一次选择排序的结果,一次选择排序将最小的放在了首位置。这样,我们已经确定了三个序号了。

        考验你耐心和观察力的时候到了,第四个串,多刷几次,发现源字符串第一个串,在第四个串中出现的位置左都比它小, 右边都比它大,这个是一次简单快速排序的特征。真的需要仔细,耐心,实在不行就自己写出代码亲自跑跑,结果绝对一目了然。

        剩下两个了, 比较难理解的,其实小编在做这道题的时候真的是傻的去写所有自己知道的排序的代码的,就当锻炼了自己吧,小编就是这样确定了前4个串的排序算法,剩下的两个自己也没有搞定,后来问了问出这道题的大神,他给个我提示,才明白剩下的两个串是怎么回事。

       观察一下第5个串, 多刷新几组数据,发现最大的每次都在最末尾,最小的每次都在最开始。这个是升级版的冒泡排序,叫鸡尾酒排序。cocktailsort。

       第6个串, 最难了,直接告诉大家吧,这是shellsort,在这道题里面是用的3为步长,意思是相隔3个的两个数进行比较。shell排序是升级版的插入排序,是一个逐步缩小步长的跳跃排序算法,保证全部数字有序,所以最后一次循环是对全数组的一次插入排序,由于前面的跳跃比较已经确定大部分的数字有序,所以最后一次虽然是一次插入排序,但是要排序的数字已经很少了。这样加快了效率。这是小编的理解,详细的,大家可以看wiki或者其它,shellsort代码,在K&R C 书上62页。有兴趣的朋友可以看看啦~(ps:排序可是很重要的哦!
一定花些时间对常用的排序理解一下!)

       好了,这道题看似简单, 但是让你也废了些努力吧。不过,若是你脑筋转的快,在知道了前4个对应的算法名字时,还可以穷举剩下的两种排序算法。很多大神做这道题的时候就是用的穷举。呵呵,又是暴力算法,但是这个很解决问题的,在我们一时半会想不到好的方法时,就可一试试穷举!!!由于小编没有写这个穷举的代码,这里就不贴了,大家应该有想法了吧~~~

       终于到了第四关了,这一关啊,可以说是最难的喽,会考查你写代码的能力,和一点点数据结构的知识。一点点就够喽!~ 我们看一下第四关:

       

       

        看起来什么信息都没有给,直接就是问题,好了,你是不是想到了什么??? 当然是看它网页源码喽~! :

       

        既然它有example , 那么下免的quiz就一定和这个类似的解法,否则它就没有存在的价值。

        发现string1 ,是一些16进制数(这个就不用小编提示大家了吧),总共有20个, 每一个16进制数都有5个数位,我们知道每个16进制数位都可以转换成4个2进制位,那么这20*5个16进制数位可以转换成400个2进制位。

        string2,是一串字母,中共有400 个,我们观察一下这些数字特征,发现20*20就是400 。

        为什么要5个16进制数位组成一起呢,5个16进制数位刚好能转换成20个2进制位。难道这有什么玄机?如果把这20个二进制放在一行,那么就有20行,刚好string2也有400个字符,也可以弄成这样的形式,毕竟我们观察key的时候前4个字符和string2一样后面一个字符就已经在string2里距离了至少20个吧。转一下试试 (代码就不贴了,相信16进制转2进制对路过的朋友来说,应该是很简单的):       

        对应16进制数位转换陈二进制的矩阵

        

        string2对应的 20*20 矩阵

       

       

        我们在来对比一下key 和这个字母矩阵还有01矩阵有什么猫腻:

        我们对照着key和字母矩阵,对应一下,发现类似一条路,再看看01矩阵,走过的都是1,再看看结尾部分,刚好是最右下角的字符。看来是个走迷宫的问题啊,从左上角沿着1走到右下角。 key就是对应每一行走过的地方的下标对应字母矩阵中的字母 ! 好的 , 有了这个思路,我们来干掉下面的quiz ! COME ON !

        上面有4096个十六进制数位,下面字母串有16384个, 刚好是128*128 的矩阵,那么每一行就有128/4=32个16进制数位 , 4096/32 刚好就等于128 ,没错,就是这样的!好了, 开干吧 。(关于走迷宫, 大可使用最简单的栈来求解, 方便好理解! 小编也是这样写的,上面运行的结果所使用的代码是任立翔大神的,他用双向链表实现的,也是很棒的方法,对于没有学过图的朋友,小编觉得这是很好的方法了。代码小编就不贴了, 大家可以用各种方法去解)

        字母矩阵图:

     

01矩阵图

走的路

key图:

key:

        终于得到KEY啦 ~~~是不是长长地舒一口气啊!!!这个路径应该是最短的啦,可能你走出来的路径和这个有点区别,那么对照一下01矩阵,优化一下自己的代码 ,就会得到这张图的一条最短路径啦 ~! 如果你学过BFS(广度优先搜索)或者DFS(深度优先搜索)那么,这道题一定对你来说是小菜,也可以使用这两种搜索算法解这道题,这两个搜索算法可是利器 ! 一定要会哦!  好了 , 你已经过了最难的一关了, 第五关就一定更不怕了 ! 来吧 ! 坚持最后一站 。但是最好还是先闭眼休息一会吧,因为这道题的信息量太大了
。 继续加油哦 ~~~

抱歉!评论已关闭.