计算机科学典型问题示例

《计算机科学典型问题示例》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学典型问题示例计算机科学典型问题示例哥尼斯堡七桥问题寻找走遍这7座桥且只许走过每座桥一次，最后又回到原出发点的路径计算机科学典型问题示例哥尼斯堡七桥问题两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，把它们看作是4个点；7座桥是7条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，任意画7条线来表示它们。欧拉将七桥问题抽象成了一个“一笔画”问题。怎样不重复地通过7座桥，变成了怎样不重复地画出一个几何图形的问题。原先，人们是要求找出一条不重复的路线，欧拉接下来着手判断：这种不重复的路线究竟存在不存在？

2、由于这么改变了一下提问的角度，欧拉抓住了问题的实质。欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：每当你用笔画一条线进入中间的一个点时，你还必须画一条线离开这个点。否则，整个图形就不可能用一笔画出。也就是说，单独考察图中的任何一个点（除起点和终点外），它都应该与偶数条线相连；如果起点与终点重合，那么，连这个点也应该与偶数条线相连。计算机科学典型问题示例哥尼斯堡七桥问题计算机科学典型问题示例哥尼斯堡七桥问题结论（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的；（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路

3、线；（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。汉诺塔问题1）每次只能移动一个盘子；2）盘子只能在三根柱子上来回移动不能放在他处；3）在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。用计算机求解一个实

4、际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，经过调试和运行，从而完成该问题的求解。从实际问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题主要的、本质的内容，最终实现对该问题的正确认识。汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算机学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。根据递归方法，我们可以将64个盘子的汉诺塔问题转化为求解63个盘子的汉诺塔问题，如果63个盘子的汉诺塔问

5、题能够解决，则可以将63个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将63个盘子从第二个柱子移动到第三个柱子上。汉诺塔问题示意图63个盘子的汉诺塔求解问题可以转化为62个盘子的汉诺塔求解问题，62个盘子的汉诺塔求解问题又可以转化为61个盘子的汉诺塔求解问题，直到1个盘子的汉诺塔求解问题。再由1个盘子的汉诺塔的解求出2个盘子的汉诺塔，直到解出64个盘子的汉诺塔问题。按照上面的算法，n个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺塔问题需要移动的盘子数的2倍加1。于是h(n)=2h(n-1)+1=2(2h(n-

6、2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1=……=2nh(0)+2n-1+…+22+2+1=2n-1+…+22+2+1=2n-1因此，要完成汉诺塔的搬迁，需要移动盘子的次数为：264-1=18446744073709551615如果每秒移动一次，一年有31536000秒，则僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。证比求易算法问题算法分析是计算机科学的一项主要工作。为了进行算法比较，我们必须给出算法效率的某种衡量标准。很

7、久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有名的数学家孔唤石当宰相。邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，便亲自登门求婚。公主说：“你如果向我求婚，请你先求出48770428433377171的一个真因子，一天之内交卷。”艾述听罢，心中暗喜，心想：我从2开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？艾述国王十分精于计算，他一秒钟就算完一个数。可是，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223092827是它的一个真因子。国王很快就验证了这

8、个数确能除尽48770428433377171。公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了”。国王