计算思维与问题求解

“四色定理”与计算机

    现代计算机工作原理是通过程序存储和程序控制来完成计算工作的，也就是说，计算机只能够对可计算的问题进行计算。对于一些复杂的重复计算问题，由于计算工作量十分惊人，人类是难以完成的。如著名的四色定理100多年后借助于计算机才得以证明。

       1852年，毕业于伦敦大学的格斯里（FrancisGuthrie）来到一家科研单位搞地图着色工作时，发现每幅地图都可以只用四种颜色着色，如图1-25。这个现象能不能从数学上加以严格证明呢？许多数学家和科学家经过了100多年的努力，最后终无法得到满意的结果。

       高速数字计算机的发明，促使更多数学家对“四色问题”的研究。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。就在1976年6月，在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿个判断，结果没有一张地图是需要五色的，最终证明了四色定理，轰动了世界。它不仅解决了一个历时100多年的难题，而且成为了数学史上一系列新思维的起点

问题求解中的计算思维

        0计算思维是指人借助于计算机，通过建立数学模型和数据结构，采用相应的计算方法以及编制计算机程序，让计算机按照人们给出的计算步骤来完成原本无法由人类独立完成的复杂问题求解和系统设计。

       由此可以看出，用计算思维求解问题的过程涉及到：人的思维、计算机、数学模型、数据结构、计算方法和程序设计等环节。它把人类求解问题的过程描述为一个可计算的问题，然后编写成相应的计算程序，用计算机来完成。因此，要用计算机求解问题就必须用计算思维的理念来描述该问题，这就是用计算思维求解问题的基本思想。

计算思维问题求解案例

1. 梵塔问题     

       据说在东方的古国印度有一座神庙，庙里有一块黄铜板，板上插着三根细细的、镶上宝石的细针，在其中一根针上从下到上放了半径由大到小的64片圆形金片环，如图1-26。 

       天神梵天要这庙的僧侣，把这些金片全部由一根针移到另外一根指定的针上，一次只能移一片，不管在什么情况下，金片环的大小次序不能变更，即小金片环永远只能放在大金片环上面。只要有一天这64片的金环能从指定的针上完全转移到另外指定的针上，世界末日就来到。

    19 世纪的法国大数学家鲁卡斯曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金片环的总次数为264 -1 = 18446744073709551615。 假设僧侣们个个身强力壮，每天24 小时不知疲倦地不停工作，而且动作敏捷快速，1 秒钟就能移动1个金片环，那么，完成这个任务也得花5800 亿年！

2. 求解过程描述

     假设有3个柱子(1，2，3)和3个不同尺寸的金片环(A，B，C)。最初，全部3个金片环都堆在柱子1上：最大的金片环C在底部，最小的金片环A在顶部。要求把所有金片环都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的金片环，还不许把尺寸较大的金片环堆放在尺寸较小的金片环上。

对于3个金片环的移动过程如图1-27所示，需要移动7次才能完成。同理，4个金片环的移动次数等于把前3个金片环重复一遍，有增加了一次，需要移动15次才能完成。如此下去，N个金片环的移动次数为2n-1。

        显然，当N较大时，靠人工完成是不可能。问题是能不能用计算机解决呢？这就需要将问题转换为一个可计算的问题。