C语言课件 第19 20章.ppt

第19章 哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,第19章 哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,第19章 哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,第19章 哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,哥德巴赫猜想,从哥德巴赫猜想（gold bach conjecture）提出这个猜想至今，许多数学家都不断努力想攻克它，但都没有成功。本章将使用c语言从算法问题入手，并一步步实现一个验证“猜想”结论正确性的程序。,19.1 问题描述,哥德巴赫猜想大致可以分为以下两个猜想。 二重哥德巴赫猜想：每个不小于6的偶数都可以表示为两个奇素数之和，如下： 6=3+3；8=3+5；10=5+5 三重哥德巴赫猜想：每个不小于9的奇数都可以表示为三个奇素数的和，如下： 9=3+3+3；11=3+3+5；13=3+5+5 在这里，我们以二重哥德巴赫猜想作为研究对象，通过编写c语言程序，来验证“猜想”的正确性。,19.2 问题分析及实现,19.2.1 问题分析 19.2.2 问题实现 19.2.3 程序运行,19.2 问题分析及实现,拿到一个要求实现的算法问题，首先要看清、想明、把握每一个细节。只有这样，才可以顺利地将算法实现。由问题描述：“每个不小于6的偶数都可以表示为两个奇素数之和”，可知，我们要实现的是判断任何一个大于6的偶数都可以有两个素数相加。以下将仔细地分析问题并实现算法。,19.2.1 问题分析,而我们的将要编写的程序，就是为了验证哥德巴赫猜想中提到的任何一个偶数，对大于6的偶数n可以分解成两个素数的和，这个结论是否正确。所以，程序应该可以输入一个数，判断是否为偶数，将这个偶数分解成一个小素数和大素数。再分别判断小素数与大素数之合是否就等于这个偶数。而且，需要将结果打印输出。,19.2.1 问题分析,我们在编程之前，需要明确两个数学概念：素数和偶数。 素数就是质数，指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和数自身）的自然数即为素数。 偶数就是能被2整除的自然数，如2、4、6、8。 根据题目，要求是奇素数，即这个素数不可以是2，一定要大于2。我们需要划分以下两个子模块。 判断一个数是否为素数。 判断并分解大小素数的和是否等于需判断的偶数。,19.2.2 问题实现,1. 判断输入的数字是否是素数 对于一个任何自然数，如何判断他是素数呢？如果这个自然数n，它存在两个因数，乘积等于n，要么两个因数一个是小于 、 一个大于 ，要么两个因数都等于 。那么，根据这个思路，代码如下（代码19-1.txt）。,19.2.2 问题实现,01 /*测试n是否是素数。如果是，返回1，否则返回0 */ 02 int isprimer(unsigned long n) 03 04 unsigned long i; 05 unsigned long nqrt; 06 if (n = 2) 07 return 1; 08 if (n = 1 | n%2 = 0) 09 return 0; 10 /*如果它存在两个因数，乘积等于n，要么两个因数一定一个小于根号n，一个大于根号n要么两个因数都等于根号n*/ 11 nqrt = (unsigned long)sqrt(n); 12 for(i=2; i=nqrt; i+=1) 13 14 if (n%i = 0) 15 return 0; 16 17 return 1; 18 ,19.2.2 问题实现,2. 将数偶数分解成两个素数，并判断“猜想”结论是否成立。 取一个数i，从最小素数开始到这个偶数的一半大小进行判断，当i为素数同时n-i也是素数时，这时猜想结论成立，否则结论不成立。代码如下（代码19-2.txt）。,19.2.2 问题实现,01 int isright(unsigned long n, unsigned long *tmpnuma, unsigned long *tmpnumb) 02 03 unsigned long i; 04 unsigned long half; 05 half = n/2; 06 for (i=3; i=half; i+=2) 07 08 if (isprimer(i) 16 ,19.2.2 问题实现,3. 要求用户输入，判断，并输出结果。 在主程序中，要求用户输入一个大于6的偶数，调用判断函数，判断“猜想”是否成立，成立则输出等式，不成立则输出“猜想”错误。代码如下（代码19-3.txt）。,19.2.2 问题实现,01 int main(void) 02 03 unsigned long number; /*被验证的数*/ 04 unsigned long a, b; /*和为number的两个素数*/ 05 do 06 07 printf(“请输入要验证的大于等于6的偶数(输入0则退出)：“); 08 scanf(“%lu“, 24 ,19.2.3 程序运行,19.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 如果出现“warning c4013: sqrt undefined; assuming extern returning int”的编译警告，通常需要在程序开头添加数学函数头文件“#include ”。 此程序的难点之一是如何判断一个数为素数。这点在程序中已经给出一注释，希望读者细细体会。 此程序另一难点是分解成素数。其实就是从最小素数开始，将最小素数i作为素数a，将偶数减i作为素数b，在a、b都是素数的情况下，分解成功。,第20章 猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章 猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章 猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章 猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,猴子选大王游戏,猴子选大王（亚瑟夫环）是数据结构和算法中常见的一类问题。有人使用循环队列实现，有人使用链表实现。本章将使用数组的回溯算法实现选猴王的算法程序。,20.1 问题描述,有m只猴子围成一圈，每只各一个从1到m中的编号，打算从中选出一个大王；经过协商，决定出选大王的规则：从第一个开始循环报数，数到n的猴子出圈，最后剩下来的就是大王。 在本章，我们以此问题作为研究对象，通过编写程序，来输出站成一圈猴子的出圈顺序号。,20.2 问题分析及实现,20.2.1 问题分析 20.2.2 问题实现 20.2.3 程序运行,20.2 问题分析及实现,拿到这个算法问题，首先想到的前面提到的要领：看清、想明、把握每一个细节。 根据问题描述可知，我们要实现的是输出猴子出圈的顺序。简单举例：9个猴子数到3出圈，则应打印：3，6，9，以下将仔细地分析问题并实现算法。,20.2.1 问题分析,而我们的将要开发的程序，就是为了使这些猴子最后留下大王，每个淘汰出圈的猴子。这里将猴子进行顺序编号。 假设猴子编号从1开始至30，则以数到3为例，从1开始数猴子，至第三只猴子时，出圈，此时，圈子应该有1，2，4，5，630，则继续从第4只从头数起，将第4只猴子做为第1号，依此类推，这样，就产生了出圈的顺序号：3，6，9，12，1529，那么最后出圈的猴子即为猴王。,20.2.2 问题实现,本小节就通过编程来实现此问题，实现的代码如下。 1. 让猴子站成一圈 如何让猴子站成一圈呢？根据问题分析结果，采用整型一维数组中保存猴子顺序号，即表示站成一排。代码如下（代码20-1.txt）。,20.2.2 问题实现,01 #include 02 #include 03 #define max 30 /*定义猴子总数为30*/ 04 int i,j,k,temp; 05 int monkeymax,s; 06 void init() 07 08 for(i=0;imax;i+) 09 monkeyi=i+1; 10 for(i=0;imax;i+) 11 printf(“%d “,monkeyi); /*让猴子站成一圈*/ 12 printf(“n“); 13 ,20.2.2 问题实现,2. 将结果输出 将回溯结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf，将结果回显。代码如下（代码20-2.txt）,20.2.2 问题实现,01 void output() 02 03 printf(“猴子淘汰出圈的顺序是:nr“); 04 for(i=max-1;i=0;i-) 05 printf(“第 %3d 只猴子出圈!nr“,monkeyi); /*输出结果*/ 06 printf(“猴王是:第 %d 只猴子nr“,monkeyi+1); /*输出结果*/ 07 ,20.2.2 问题实现,3. 回溯法求猴子出圈顺序 在主程序中，要求用户输入出队序数，即数到s，就让序号是s的猴子出队。回溯法是：将猴子总个数循环，第一次循环都是将当前需要出圈的猴子排到数组末尾。这样，当全部猴子循环一遍后，数组头的猴子即为猴王。从数组尾开始向头循环输出，即为猴子出圈序列。代码如下（代码20-3.txt）,20.2.2 问题实现,01 void main() 02 03 init(); 04 printf(“请输入出队的序数：“); 05 scanf(“%d“, 20 ,20.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入出队的序数，即数到几就出列，按【enter】键，输出结果如下。,20.3 开