C程序应用实例.ppt

11.1抽奖程序 一个抽奖程序要求能够首先输入抽奖者的个人信息，个人信息包括手机号码和姓名等。开始抽奖时，屏幕上快速闪动参与者的手机号码，按任意键停止闪动，把中奖人的信息用显示在屏幕上，可反复抽出一、二、三等奖若干名。 1. 程序实现以下功能 录入：输入抽奖者的信息； 抽奖： a. 抽出一等奖 1 名，如果抽过就不能再抽； b. 抽出二等奖 2 名，如果抽完就不能再抽； c. 抽出三等奖 5 名，如果抽完就不能再抽； 显示：显示所有中奖者的信息； 退出程序。 2. 算法思路 抽奖者信息存储在结构体数组中； 抽奖过程有两个难点： 为保证抽奖的公正性，要使用随机函数生成获奖者。 抽奖者不能重复获奖。在抽奖者信息结构体中增加一个标记变量winning，来记录其是否抽中过。 获奖者的信息存入相关数据，抽奖结束后，利用循环语句分别输出。 11.2求解“四色问题” 著名的“四色问题”又称四色猜想，是世界近代三大数学难题之一，与拓扑学发展有密切关系。 1．“四色问题”的提出 四色问题的提出来自英国，1852年毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”?。数学家德·摩根（Augustus De Morgan）在1852年10月23日致数学家哈密尔顿的一封信中提供了有关四色问题来源的最原始的记载。他在信中简述了自己证明四色问题的设想与感受。一百多年来，数学家们为证明这条定理绞尽脑汁，所采用的概念与方法推动了拓扑学与图论的生长、发展。 四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。” 2.“四色定理”的机器证明 1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken） 在伊利诺斯大学的两台不同的电子计算机上，使用穷举法对1936种地图模型试着色，用了1200个小时，作了100亿次判断，终于完成了四色定理的证明，轰动了世界，为用计算机证明数学定理开拓了前景。 3. 地图自动着色程序（参见教材） 本例给出对地图自动着色的程序，只用四种颜色对给定的地图着色。地图的数据结构采用邻接表结构。 11.3高精度计算圆周率 圆周率，一般以π来表示，是一个在数学及物理学普遍存在的数学常数。它定义为圆形的周长与直径之比。它也等于圆形的面积与半径平方之比。是精确计算圆周长、圆面积、球体积等几何形状的关键。 常用的 π 近以值包括疏率: 22/7 及密率: 355/113。这两项均由祖冲之给出。 在历史上，有不少数学家都对圆周率进行过研究，提出了各自不同的计算方法，当中著名的有阿基米德（Archimedes of Syracuse）、托勒密（Claudius Ptolemy）、张衡、祖冲之等。 1. 计算圆周率的记录 1950年，美国科学家里特韦斯纳、冯纽曼和梅卓普利斯利用世界上首台计算机ENIAC，计算出π的2037个小数位。这台计算机只用了70小时就完成了这项工作，扣除插入打孔卡所花的时间，等于平均两分钟算出一位数。 圆周率的必威体育精装版计算记录是2010年1月法国软件工程师布里斯·贝拉德（Fabrice Bellard）公布的2.7万亿位。读者可到贝拉德的个人网站()下载详细的技术报告。完成这次计算的计算机价格不到5千美元，配置为：2.93GHz Core i7处理器，内存6GB，硬盘7.5TB。该项记录打破了由日本筑波大学的T2K Open超级计算机（当时世界排名第4247位，造价数百万美元）2009年8月17日创造的2.577万亿位的记录。 贝拉德实现的方案中二进制计算时间为103天，验证花费13天，转换为十进制并验证又花费15天，总共时间为131天。二进制计算使用的是乌克兰Chudnovsky兄弟提出的公式： 其中 AB=545140134，C=640320。 2. 利用高斯公式计算圆周率 这里提出一个利用反正切函数级数展开求值的方法。利用高斯（Gauss）公式求π值精度比较高，公式如下： π= 48 * arctan(1/18) + 32 * arctan(1/57) - 20 * arctan(1/239) 上式中，关键要计算几个反正切函数的值，arctanx计算方法为： 为提高程序的交互性，本例中程序使用带参数的主函数，在命令行不加参数执行该程序则使用高斯公式计算前1000位圆周率的值，如果带一个命令行参数，则该值为要计算的位数。如果还有第二个命令行参数，则使用斯图摩（Stomer）公式重新计算π，