答案和提示

  1. 找出最轻物件的最佳方法为:按顺序把每个物件都检查一遍,并记住到目前为止最轻的物件就可以了。也就是说,比较两个物件,并保留较轻的那个,再把被保留下来的物件和另一个物件比较,再次保留较轻的那个。一直重复上述动作,直到所有物件都被比较过了。

  2. 在天平上比较重量,这样可以简单地用三次比较,有时候甚至两次比较就可以——如果学生了解什么是比较的传递性(也就是A比B轻,而且B比C轻的话,那A就一定比C轻。)

高手挑战

有一条捷径可以把选择排序法执行的次数加总。

要找到两个物件中较轻的物件需要比较一次,三个需要两次,四个需要三次,以此类推。要排序八个物件,首先需要比较七次以找出最小物件,再来是花六次找出剩余七个物件中最轻的物件,以此类推。

最后我们就会得到排序总次数:

7+6+5+4+3+2+1 = 28 次比较。

n个物件就需要1+2+3+4+。。。+n-1次比较才能排序。

如果我们重新编组这些数字可以比较简单的得出相加结果。

例如,要运算1+2+3+。。。+20,就把它们重新编组成

(1+20)+(2+19)+(3+18)+(4+17)+(5+16)+(6+15)+(7+14)+(8+13)+(9+12)+(10+11)= 21 x 10 = 210

所以,1+2+3+4+。。。+n-1 = n x(n-1)÷ 2

results matching ""

    No results matching ""