2014保送生上课讲义

《2014保送生上课讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章算法和算法的描述1．1用计算机解决问题的过程1742年6月7日，德国数学家哥德巴赫（C.Goldbach）提出了一个大胆的数学猜想：任何一个偶数（≥6）均可表示两个素数（质数）之和，简称：“l＋1”，这一猜想这就是数学史上著名的“哥德巴赫猜想”。两百多年来，“哥德巴赫猜想”吸引了世界上众多的数学家研究，但始终没有结果，它已成为世界数学界一大悬案。目前的最佳结果是中国数学家陈景润于1966年的证明。他运用新的方法，在一间六平方米的小屋里，借助一盏昏暗的煤油灯，用一支笔，耗去了几麻袋的草稿纸，攻克了世界著

2、名数学难题“哥德巴赫猜想”中的“1+2”，即证明了“任何一个充分大的偶数都是一个素数及一个不超过两个素数的乘积之和”，称为陈氏定理(Chen‘sTheorem)。他创造了距摘取这颗数论皇冠上的明珠“1+1”只是一步之遥的辉煌，在“哥德巴赫猜想”的研究上居世界领先地位。在数学课程中已经学习素数就是满足这样条件的整数：它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，如果来判断123456791是否为素数？就需要验证从2到123456790之中是否有123456791的约数，如果没有，

3、则为素数，反之则为合数，相信这是一件十分繁琐的工作。而如果使用算法与程序设计的知识，设计出解决此问题的算法并编制好程序，那么此项工作将会变得十分容易。运行程序后输入相应数据，立即就能得出结果。一般来说，使用计算机来解决问题经过以下几个步骤：一、分析问题分析问题阶段的目的是确定用计算机“做什么”。在日常生活中会遇到各种各样的问题，许多问题可以使用计算机来解决，例如，编制一份小报、统计比赛成绩、“沉鱼落雁闭月羞花”是形容我国古代哪四位美女、求解一元二次方程ax2+bx+c=0的实数根、公交换乘等问题，但是还存在

4、另外一些问题是无法用计算机来解决的，如：求解哥德巴赫猜想、求证3x+1问题等。对于上述例子，可以分析得出：判断一个整数Ｎ是否为素数的问题就是要去寻找除了1和它自己之外，还是否存在其它因子，如果不存在，那么它就是素数，反之，它就是合数。二、确定算法在这个阶段的目的是解决计算机“怎么做”的问题，也就是算法。计算机在人类智慧指引下，能够解决的问题可以分为三类：使用现有工具软件可以解决的问题。例如编制一份小报可以用Word软件、统计比赛成绩可以用Excel软件、可以利用网络搜索寻找“沉鱼落雁闭月羞花”的答案等；现有

5、工具软件不能直接解决，需要编写程序就可以解决的问题。例如求解一元二次方程ax2+bx+c=0的实数根、判断一个整数是否为质数等；现有工具软件不能直接解决，通过编写程序，也不能直接解决的问题。例如天气预报、机器翻译、博弈问题等。对于上述例子，通过分析可以得到：判断一个整数N是否为素数的方法就是对从2～之间的整数逐一进行判断，判断是否为整数Ｎ的因子。如果一个也不存在，则整数Ｎ就是素数，否则就是合数。因为根据合数的条件可以知道，整数Ｎ可以分解因子A×B，则Ａ，Ｂ中必有一个满足条件小于等于。三、设计步骤根据找到的方

6、法，需要设计更详细的步骤，以便根据这些步骤能够方便编写程序。下面采用自然语言的方法来描述判断一个整数Ｎ是否为素数的详细步骤：1）输入整数Ｎ的值；2）将Ａ的值置为２；363）将Ｂ的值置为；4）判断Ａ≤Ｂ?，条件成立执行下一步，否则搜索结束跳转至第７步；5）判断Ｎ能否整除Ａ，若能整除，即找到因子，跳转第７步；6）Ａ的值增加１，跳转至第4步；7）判断Ａ>Ｂ?，条件成立输出结果“是素数”，否则输出结果是“合数”。四、编程求解在确定好算法后，就可以选择一种程序设计语言来实现。将算法表示成程序，得出最终结果就是程序设计

7、的过程。课堂实践1．运行判断素数的程序。2．一个农夫带着一条狼、一头山羊和一篮蔬菜要过河，但只有一条小船。乘船时，农夫只能带一样东西，当农夫在场时，这三样东西相安无事，一旦农夫不在，狼会吃羊，羊会吃菜。请列出一种方法，使农夫能安全地将这三样东西带过河。运行“农夫过河”程序，并尝试写出解决问题的步骤。3．传教士与野人过河问题。有3个野人和3个传教士分别在河的两岸，需要过河。现在有一艘小船，最多能容两人，在渡河时，无论是在左岸还是右岸，如果野人的数目超过传教士的数目，野人就会吃掉传教士。问怎样才能安全渡河？运行

8、“传教士与野人过河”程序，并尝试写出解决问题的步骤。1．2算法和算法的描述在数学课上，小明遇到了这样一个问题：“有一根长度为L厘米的铜丝，制作一个面积为S平方厘米的矩形框，请问矩形框的长H和宽W分别是多少？”这是一个一元二次方程的应用问题。根据已知条件可以写出式子：L=2(H+W)…………………………①S=H×W……………………………②由①②式子可得S=H×(-H),即H2-H+S=0，然后使用消元法求得H，再求