幸运的同学

来自计算思维百科
跳转至: 导航搜索
幸运的同学.jpg

有10名同学在运动会中的成绩都是满分,但是奖杯只有一个,所以大家决定用报数的方式来确定奖杯归谁。于是这10名同学站成一排,然后从头器 ,“12,12”地报数,凡是报出“1”的都可以离开,最后剩下的那个就可以拥有奖杯。那么,几号是最幸运的同学呢?

解决方案

方案一:蛮力法

根据题意我们把每一步的人数情况都列出来,如下:编号代表所站的位置

 

1

2

3

4

5

6

7

8

9

10

第一轮

1

2

1

2

1

2

1

2

1

2

新位置

 

1

 

2

 

3

 

4

 

 

第二轮报数

 

1

 

2

 

1

 

2

 

1

 

 

 

 

1

 

 

 

2

 

 

第三轮报数

 

 

 

1

 

 

 

2

 

 

 

 

 

 

 

 

 

 

留下

 

 

可以看到经过3轮报数,8号获得了奖杯。

这是在只有8个人的情况下我们可以较快地利用蛮力法找到答案,可是人数较多的话显然我们要耗费更多的 时间和精力才能找到答案。

运用的计算思维

从上述解法中我们可以看到蛮力法的解法对于小规模数据时可以高效求解,可是当数据规模变大时,显然这种方法的代价极大。在计算思维中的机械式思维就是如此,根据问题按部就班地求解。当规模较大时我们就应该寻求是否存在更高效地方法。

方案二:递推关系解法

这个问题实际上存在着一个递推关系。我们可以发现每次都是奇数位置上的同学离开了,而每一次剩下的偶数号位置上的同学位置编号也发生了变动,每一轮对应的位置是上一轮的1/2,所以得到这样的递推式,J(2K)=2J(K);利用数学公式我们可以计算出J(2k+i)= 2k.则有

J(10)=J(23+2)=23=8.

因此第8个人获得奖杯。

运用的计算思维

在这个问题中,每一次问题的规模都减半,减半后的解决步骤都是一样的,利用这个特点就可以推出相应的关系式,减少了相当一部分的工作量,在计算思维中对应着约简的思想,被广泛用于各类问题求解中。

参考文献

[1] 《数学趣味游戏》 网上资源