圣诞娃娃

来自计算思维百科
跳转至: 导航搜索
圣诞娃娃.jpg

为了迎接圣诞节,圣诞老人决定向全世界最乖的10名小朋友赠送圣诞娃娃,所以来到了著名的玩具店“游乐场”。玩具店里,10个装有玩具娃娃的箱子摆成一排,每个箱子中有1个以上的玩具。店家为了方便订购,给每个箱子编上了0到9的序号,每个箱子里的娃娃数量见下表。订购时,只能订购连续编号的箱子。圣诞老人要将订购的娃娃平均分给10名小朋友,要如何订购?

箱子序号

0

1

2

3

4

5

6

7

8

9

娃娃数量

8

6

9

5

11

17

7

21

15

4

解决方案

圣诞老人订购的圣诞娃娃数量要是小朋友数量的倍数才能平均分给小朋友,所以圣诞老人需要计算哪些连续的箱子中圣诞娃娃的数量是10 的倍数。

方案一:蛮力法

观察上面箱子娃娃中的数量我们知道圣诞老人只订购一个箱子是不可能的,所以至少要订购2个箱子。

订购两个箱子有9种情况分别是:

0和1:14

1和2:15

2和3:14

3和4:16

4和5:28

5和6:24

6和7:28

7和8:36

8和9:19

订购三个箱子有8种情况:

0、1、2:23

1、2、3:20

2、3、4:25

3、4、5:33

4、5、6:35

5、6、7:45

6、7、8:43

7、8、9:40

订购四个箱子有7种情况:

……

运用的计算思维

蛮力法是我们最先最容易想到的方式,我们通过蛮力法来更加深入地理解问题,接着再试着使用其他简便方法,机械化的思维方式是解决问题最基本的方式。

方案二:部分和法

连续的n~m号箱子的娃娃总和等于m号箱子前(包括m)m+1个箱子的娃娃总和减去n号箱子前n个箱子娃娃的总和。例如,2到4号箱子娃娃的总和等于4号箱子前包括4号箱在内的所有箱子娃娃数量减去2号箱子前所有箱子中娃娃数量,即

箱子序号

0

1

2

3

4

5

6

7

8

9

娃娃数量

8

6

  9  

  5  

  11  

17

7

21

15

4

9+5+11=(8+6+9+5+11)-(8+6)

所以,我们第一步可以求出部分和:

前n个箱子

1

2

3

4

5

6

7

8

9

部分和

8

14

23

28

39

56

77

92

96

假设psum[k]表示前k个箱子娃娃数量部分和,圣诞老人要订购的n~m号箱子的娃娃数量要能够被10整除,也就是(psum[m]-psum[n-1]) mod 10 = 0,展开得到:

psum[m] mod 10= psum[n-1] mod 10,所以只要两个部分和分别除以10的余数相同,那么这两个部分和之间的箱子就符合要求。

前n个箱子

1

2

3

4

5

6

7

8

9

部分和

8

14

23

28

39

56

77

92

96

mod 10

8

4

3

8

9

  6  

7

2

  6  

所以,7、8、9三个箱子娃娃数量符合条件,与蛮力法解得的答案一致。

运用的计算思维

部分和法首先将表格数据进行了预处理,求出部分和,然后再对10求余,最后只需要找出相等的两个值就能找到一种解法。我们知道部分和法能够简化计算连续和,并且我们将其运用到实际问题中,体现了“启发式”的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015