思考的乐趣:UyHiP趣题之用最少的块移动实现逆序操作

    Michael BrandUsing your Head is Permitted是我最喜欢的谜题挑战网站,很多题目相当精彩。我已经多次翻译了那上面的谜题(点击这里看看)。不过,以往我都是静候月底释出答案,从来没有想过参与挑战。这个月的题相当诱人,只看题目描述的最后一句话我就知道这绝对是我喜欢的类型,于是我有了向本月题目发起挑战的冲动。印象中我真的是很久很久没有像这样疯狂地思考一个问题了。然后呢,我非常得意地告诉大家,哈哈~~~经过昨天一整夜的思考,我终于把它解决了!!于是赶忙写下我的解答过程,再三检查后发到了Michael Brand的邮箱。今天起床时收到了Michael Brand热情洋溢的回信,List of solvers也写上了我的名字,我很是兴奋。自我感觉这是一道非常好的题目,题目简洁有趣而有挑战性,解答本身并不难但也不太好想,很适合大家花一整天的时间仔细琢磨;因此这里也推荐给大家来挑战一下。解答不要发到下面的评论里,也不用发给我,直接发过去好了。期待过几天在List of solvers里看到大家的名字。

    在这里简单翻译一下题目。对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方(说穿了就是一次选择剪切粘贴的操作)。例如,数列1,4,5,6,2,3,7可以通过一次块移动完成排序(把456挪到3后面)。那么,想要让一个1到n的逆序排列n, n-1, …, 3, 2, 1变为顺序排列,最少需要多少次块移动?给出你的算法,并证明这个移动数目不能再少了。

Update: 为防止进一步讨论,我把评论禁了…

7 条评论

  • sqybi

    沙发
    感觉是n-1 orz

  • Googol

    logn?和排序有关吧?

  • BIRAN007

    想到前两天做的一道排家具的题目
    我觉得可以这样排:
    找出最小的数,然后从那个数开始往后,取数字连续的递增的最大的块,把这块移动到最左边,将此块删除,算移动一次。重复此操作,全部删除为止
    证明大概可以用数学归纳法……还在想……

  • Demx

    可以再加上两问:
    1. 条件换成一个被打乱的1至n数列,请给出一种方法判断继续将之“块移动”至顺序排列所需的最小步数。
    2. 条件换成一个打乱且每个数均可以多次出现的1-n数列,回答上问。

    那么这就是个蛮有阶梯的赛题了。

  • sdyy1990

    求解。。。希望您能告诉我……

Comments are closed.