背诵圆周率

来自计算思维百科
跳转至: 导航搜索
背诵圆周率1.jpg

偶尔能在电视上看到一些被称作“神童”的孩子们背诵小数点以后的几万位的圆周率。背诵这么长的数字,可利用分割数字的方法。我们用这种方式将数字按照位数不等的大小分割后再背诵,而且一般会按照像5555或者123等容易记住的形式分割。

给出一定位数的圆周率时,以33786789为例,按3到5位数字分割,使其难度之和变为最小,如何计算该最小难度值?各个分割块的难度按照以下形式分类。

情况

示例

难度

所有数字都相同

333、5555

1

数字逐个单调递增或递减

23456、3210

2

两个数字交替出现

3232、545

4

等差数列

147、8642

5

其他

17912、331

10

解决方案

方案一:蛮力法

蛮力法的做法是计算数串所有分割方式对应的难度值,最后选择出最小值。对于3378656789而言,按3到5位数字分割,有以下分割方式:

337865| 6789  难度值10+10+2=22

3378656| 789  难度值10+10+2=22

3378| 656| 789  难度值10+4+2=16

3378656789    难度值10+2=12

因此,按照3378656789来分割使得背诵难度最小。

运用的计算思维

蛮力法适用于解决数串长度短的问题,运用了机械化的计算思维。

方案二:动态规划法

对于数串3378656789的第一个分割块有三种情况:

(1)337

(2)3378

(3)33786

那么,整个数串的最小难度就取对应的下列三种情况中的最小值:

(1)337的难度+去掉337后剩余数串的最小难度

(2)3378的难度+去掉3378后剩余数串的最小难度

(3)33786的难度+去掉33786后剩余数串的最小难度

对于每一种情况下的剩余字符串依然采取同样的方式进行计算,最后就能得到原数串的最小难度。

背诵圆周率2.png

运用的计算思维

动态规划法通常先把问题分割成若干子问题,然后求出子问题答案,最后再利用这些答案得出整个问题的最终答案。与分治法不同的是,动态规划中有些子问题的计算结果会用于多个问题的解题过程,需要重复利用,例如上述337的难度值就在两种情况下用到。动态规划法的实现是基于“规约”以及“分解”的计算思维。

参考文献

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