排序问题的最佳整理方法_六年级-查字典奥数网
 
请输入您要查询的关键词

排序问题的最佳整理方法

2009-04-24 16:19:22     标签:工程问题

要把书架上的图书依序整理好是件繁琐的工作,因此图书馆管理员很想知道最有效率的做法。她发现将书按照顺序排列的最好方法就是每次调换两本书。也就是说,每次取下两本书,交换次序后再摆回书架。

她需要交换几次,才能将上图所示的整套百科全书排成123456789的次序?

如果书的次序是457681923,怎样做才是最有效率的?

请设计一套策略,不论百科全书的次序如何,都可以找出应该如何交换的最佳整理方法。

解答与分析

所需交换的次数,与书本次序的混乱程度有关,以下说明该如何系统地予以分析。首先,将书本要求的次序列在原有次序之上:

要求次序 1 2 3 4 5 6 7 8 9

原有次序 6 5 7 1 8 9 3 2 4

这样就可以清楚地看出3和7正好是在对方的位置,因此只要将两者调换,以(3 7)表示,就可以使它们各在其位。

其他的书就不是这样单纯的摆错位置。稍加观察,我们会发现:

6是在1的位置

1是在4的位置

4是在9的位置

9是在6的位置

因此这4本书只须彼此互换即可。它们的相对关系可以用(6 1 4 9)表示,最少需要3次交换,先是(4 9),之后(1 4),最后(6 1)。

同理,剩下的3本书的相对关系也可以用(5 2 8)表示,因为:

5是在2的位置

2是在8的位置

8是在5的位置

所以可以经过(2 8)之后再做(5 2)的交换,把书全都放回到正确位置。

因此,图上的百科全书可以经过以下的交换,恢复到正确的次序:

(3 7)(4 9)(1 4)(6 1)(2 8)(5 2)

这并不是唯一的答案,不过从原有的次序至少须经过6次交换才能完成整理工作。将同样的方法应用到第二种次序:

要求次序 2 3 4 5 6 7 8 9

原有次序 4 5 7 6 8 1 9 2 3

我们可以用

(4 1 6)(5 2 8)(7 3 9)

来描述原有次序的混乱程度。而这些相对关系可以经过下列的6次交换恢复到正确的次序:

(1 6)(4 1)(2 8)(5 2)(3 9)(7 3)

请找出需要几次交换才能把原有次序为2 3 5 9 4 1 8 6 7的书整理好。

点击显示
上一篇:运送汽油的证明
下一篇:楔而不舍的青蛙
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关文章
热门文章
最新文章
  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •   排序问题的最佳整理方法_六年级-查字典奥数网
     
    请输入您要查询的关键词

    排序问题的最佳整理方法

    2009-04-24 16:19:22     标签:工程问题

    要把书架上的图书依序整理好是件繁琐的工作,因此图书馆管理员很想知道最有效率的做法。她发现将书按照顺序排列的最好方法就是每次调换两本书。也就是说,每次取下两本书,交换次序后再摆回书架。

    她需要交换几次,才能将上图所示的整套百科全书排成123456789的次序?

    如果书的次序是457681923,怎样做才是最有效率的?

    请设计一套策略,不论百科全书的次序如何,都可以找出应该如何交换的最佳整理方法。

    解答与分析

    所需交换的次数,与书本次序的混乱程度有关,以下说明该如何系统地予以分析。首先,将书本要求的次序列在原有次序之上:

    要求次序 1 2 3 4 5 6 7 8 9

    原有次序 6 5 7 1 8 9 3 2 4

    这样就可以清楚地看出3和7正好是在对方的位置,因此只要将两者调换,以(3 7)表示,就可以使它们各在其位。

    其他的书就不是这样单纯的摆错位置。稍加观察,我们会发现:

    6是在1的位置

    1是在4的位置

    4是在9的位置

    9是在6的位置

    因此这4本书只须彼此互换即可。它们的相对关系可以用(6 1 4 9)表示,最少需要3次交换,先是(4 9),之后(1 4),最后(6 1)。

    同理,剩下的3本书的相对关系也可以用(5 2 8)表示,因为:

    5是在2的位置

    2是在8的位置

    8是在5的位置

    所以可以经过(2 8)之后再做(5 2)的交换,把书全都放回到正确位置。

    因此,图上的百科全书可以经过以下的交换,恢复到正确的次序:

    (3 7)(4 9)(1 4)(6 1)(2 8)(5 2)

    这并不是唯一的答案,不过从原有的次序至少须经过6次交换才能完成整理工作。将同样的方法应用到第二种次序:

    要求次序 2 3 4 5 6 7 8 9

    原有次序 4 5 7 6 8 1 9 2 3

    我们可以用

    (4 1 6)(5 2 8)(7 3 9)

    来描述原有次序的混乱程度。而这些相对关系可以经过下列的6次交换恢复到正确的次序:

    (1 6)(4 1)(2 8)(5 2)(3 9)(7 3)

    请找出需要几次交换才能把原有次序为2 3 5 9 4 1 8 6 7的书整理好。

    点击显示
    上一篇:运送汽油的证明
    下一篇:楔而不舍的青蛙
    推荐文章
    猜你喜欢
    附近的人在看
    推荐阅读
    拓展阅读
    相关文章
    热门文章
    最新文章
  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •