《C程序应用实例》PPT课件.ppt

计算机程序设计基础（C语言）,第11章 C程序应用实例,计算机程序设计基础（C语言）,11.1抽奖程序,一个抽奖程序要求能够首先输入抽奖者的个人信息，个人信息包括手机号码和姓名等。开始抽奖时，屏幕上快速闪动参与者的手机号码，按任意键停止闪动，把中奖人的信息用显示在屏幕上，可反复抽出一、二、三等奖若干名。 1. 程序实现以下功能 录入：输入抽奖者的信息； 抽奖： a. 抽出一等奖 1 名，如果抽过就不能再抽； b. 抽出二等奖 2 名，如果抽完就不能再抽； c. 抽出三等奖 5 名，如果抽完就不能再抽； 显示：显示所有中奖者的信息； 退出程序。 2. 算法思路 抽奖者信息存储在结构体数组中； 抽奖过程有两个难点： 为保证抽奖的公正性，要使用随机函数生成获奖者。 抽奖者不能重复获奖。在抽奖者信息结构体中增加一个标记变量winning，来记录其是否抽中过。 获奖者的信息存入相关数据，抽奖结束后，利用循环语句分别输出。,计算机程序设计基础（C语言）,3. 随机函数介绍 (1) rand()函数 原型: int rand(void) 功能: 产生从0到RAND_MAX(0x7fff）之间的随机数。 头文件: stdlib.h 示例: #include #include int main() int k; k = rand(); printf(“%dn“, k); return 0; 编译运行上述程序，结果的确产生随机数了，但是，每次运行程序产生的随机数都是一样的，为什么呢？因为在缺省情况下，每次随机数的初始种子是相同的，C语言中会生成固定序列，所以每次执行所得到的是同一个数。那么如何写一个程序，让它每次运行时产生的随机数都不一样呢？需要学习下面的函数。,计算机程序设计基础（C语言）,(2)srand()函数: 原型: void srand(unsigned seed) 功能: 产生随机数的起始发生数据，和rand函数配合使用 头文件: stdlib.h time.h 示例: #include #include #include int main(void) int i; time_t t; srand(unsigned) time( 运行程序，会发现每次产生的随机数都不一样。这是因为这里采用了系统当前时间作为初始种子，而时间在每时每刻都不相同，所以就产生了“随机”的随机数了。所以，要想每次产生不同的随机数，在使用rand之前需要先调用srand。,计算机程序设计基础（C语言）,(3)产生一个X到Y的随机数 由于rand产生的随机数从0到rand_max，而rand_max是一个很大的数，那么如何产生从XY的数呢？ 只要使用下面的语句： k=rand()%(Y-X+1)+X; 这样就可以产生想要的指定范围内的随机数了。 例如：k=rand()%(100-1+1)+1; 可以得到1,100以内的随机数。,4. 本例的程序清单参见教材,计算机程序设计基础（C语言）,11.2求解“四色问题”,著名的“四色问题”又称四色猜想，是世界近代三大数学难题之一，与拓扑学发展有密切关系。 1“四色问题”的提出 四色问题的提出来自英国，1852年毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。” 。数学家德摩根（Augustus De Morgan）在1852年10月23日致数学家哈密尔顿的一封信中提供了有关四色问题来源的最原始的记载。他在信中简述了自己证明四色问题的设想与感受。一百多年来，数学家们为证明这条定理绞尽脑汁，所采用的概念与方法推动了拓扑学与图论的生长、发展。,计算机程序设计基础（C语言）,四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”,计算机程序设计基础（C语言）,2.“四色定理”的机器证明 1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken） 在伊利诺斯大学的两台不同的电子计算机上，使用穷举法对1936种地图模型试着色，用了1200个小时，作了100亿次判断，终于完成了四色定理的证明，轰动了世界，为用计算机证明数学定理开拓了前景。 3. 地图自动着色程序（参见教材） 本例给出对地图自动着色的程序，只用四种颜色对给定的地图着色。地图的数据结构采用邻接表结构。,计算机程序设计基础（C语言）,11.3高精度计算圆周率,圆周率，一般以来表示，是一个在数学及物理学普遍存在的数学常数。它定义为圆形的周长与直径之比。它也等于圆形的面积与半径平方之比。是精确计算圆周长、圆面积、球体积等几何形状的关键。 常用的 近以值包括疏率: 22/7 及密率: 355/113。这两项均由祖冲之给出。 在历史上，有不少数学家都对圆周率进行过研究，提出了各自不同的计算方法，当中著名的有阿基米德（Archimedes of Syracuse）、托勒密（Claudius Ptolemy）、张衡、祖冲之等。,计算机程序设计基础（C语言）,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万亿位的记录。,计算机程序设计基础（C语言）,贝拉德实现的方案中二进制计算时间为103天，验证花费13天，转换为十进制并验证又花费15天，总共时间为131天。二进制计算使用的是乌克兰Chudnovsky兄弟提出的公式： 其中 A=13591409，B=545140134，C=640320。,计算机程序设计基础（C语言）,2. 利用高斯公式计算圆周率,这里提出一个利用反正切函数级数展开求值的方法。利用高斯（Gauss）公式求值精度比较高，公式如下： = 48 * arctan(1/18) + 32 * arctan(1/57) - 20 * arctan(1/239) 上式中，关键要计算几个反正切函数的值，arctanx计算方法为： 为提高程序的交互性，本例中程序使用带参数的主函数，在命令行不加参数执行该程序则使用高斯公式计算前1000位圆周率的值，如果带一个命令行参数，则该值为要计算的位数。如果还有第二个命令行参数，则使用斯图摩（Stomer）公式重新计算，用于对比验证结果的正确性。斯图摩公式如下： = 24 * arctan(1/8) + 8 * arctan(1/57) + 4 * arctan(1/239) 示例程序参见教材,计算机程序设计基础（C语言）,11.4 C语言与汇编语言的混合编程,汇编语言是直接操纵硬件的，是除了机器语言以外最高效的计算机语言，在某些方面汇编语言仍然具有强大的生命力，但用汇编语言开发程序，开发周期长，容易出错且不易调试。 要想既利用汇编语言代码短、执行速度快的特性，又能快速的开发出实用的应用程序，就需要汇编语言与高级语言混合编程。 由于C语言独特的优点和其应用的广泛性，使其与汇编语言的混合编程有实际意义。,计算机程序设计基础（C语言）,汇编语言和C语言的混合编程可以分为三种： 汇编语言程序调用C函数 C程序调用汇编语言函数 C程序内嵌汇编指令 前两种要求C程序与汇编程序之间必须符合函数变量引用的规则，并且随着汇编程序和C程序内存模式的不同，规则也相应的变化。 这里只介绍第三种：C程序内嵌汇编指令。一般在C程序中想直接控制硬件或加快运行速度，用高效的汇编程序实现时，可以采用这种方法。,计算机程序设计基础（C语言）,汇编语言与VC+6.0的混合编程,VC+6.0是微软公司为开发32何应用程序而推出的基于CC+的集成开发环境。它的强大功能使它成为最优秀的开发工具之一。它同样也支持内嵌汇编指令的混合编程，并且VC+6.0的编译器中已经集成了汇编指令编译器，使得编译连接非常方便，它的实现是： VC+ 6.0内部支持的微软版本的CC+，与ANSI C有细微区别，在VC+中嵌入汇编语句的关键字是_asm而不是asm。 asm不能单独出现，后面必须有汇编指令或者是由大括号括起来的多条指令。 _asm 所带的一组汇编指令中可以有标号，C语言中的goto语句和汇编指令的跳转语句可以跳到汇编指令组中的标号处，也可以跳转到汇编指令组外的标号处,计算机程序设计基础（C语言）,3. 程序实例 下面是进行十亿次减法运算，用汇编与C语言进行的比较。用C语言进行10亿次减法运算的循环如下： void main() long n1=10000； long n2=100000； while(1) if(n2=0) bre