C语言课件 第19 20章.ppt

上传人:文库蛋蛋多 文档编号:2338628 上传时间:2023-02-13 格式:PPT 页数:35 大小:217KB
返回 下载 相关 举报
C语言课件 第19 20章.ppt_第1页
第1页 / 共35页
C语言课件 第19 20章.ppt_第2页
第2页 / 共35页
C语言课件 第19 20章.ppt_第3页
第3页 / 共35页
C语言课件 第19 20章.ppt_第4页
第4页 / 共35页
C语言课件 第19 20章.ppt_第5页
第5页 / 共35页
点击查看更多>>
资源描述

《C语言课件 第19 20章.ppt》由会员分享,可在线阅读,更多相关《C语言课件 第19 20章.ppt(35页珍藏版)》请在三一办公上搜索。

1、第19章哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,第19章哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,第19章哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,第19章哥德巴赫猜想,问题描述 问题分析及实现 开发过程常见问题及解决,哥德巴赫猜想,从哥德巴赫猜想(Gold Bach Conjecture)提出这个猜想至今,许多数学家都不断努力想攻克它,但都没有成功。本章将使用C语言从算法问题入手,并一步步实现一个验证“猜想”结论正确性的程序。,19.1 问题描述,哥德巴赫猜想大致可以分为以下两个猜想。二重哥德巴赫猜想:每个不小于6的偶数都可

2、以表示为两个奇素数之和,如下: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的偶数

3、都可以有两个素数相加。以下将仔细地分析问题并实现算法。,19.2.1 问题分析,而我们的将要编写的程序,就是为了验证哥德巴赫猜想中提到的任何一个偶数,对大于6的偶数n可以分解成两个素数的和,这个结论是否正确。所以,程序应该可以输入一个数,判断是否为偶数,将这个偶数分解成一个小素数和大素数。再分别判断小素数与大素数之合是否就等于这个偶数。而且,需要将结果打印输出。,19.2.1 问题分析,我们在编程之前,需要明确两个数学概念:素数和偶数。素数就是质数,指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和数自身)的自然数即为素数。偶数就是能被2整

4、除的自然数,如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 unsig

5、ned 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,从最小素数开始到这个偶数的一半

6、大小进行判断,当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的偶数,调用

7、判断函数,判断“猜想”是否成立,成立则输出等式,不成立则输出“猜想”错误。代码如下(代码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 undefin

8、ed;assuming extern returning int”的编译警告,通常需要在程序开头添加数学函数头文件“#include”。此程序的难点之一是如何判断一个数为素数。这点在程序中已经给出一注释,希望读者细细体会。此程序另一难点是分解成素数。其实就是从最小素数开始,将最小素数i作为素数A,将偶数减i作为素数B,在A、B都是素数的情况下,分解成功。,第20章猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章猴子选大王游

9、戏,问题描述 问题分析及实现 开发过程常见问题及解决,猴子选大王游戏,猴子选大王(亚瑟夫环)是数据结构和算法中常见的一类问题。有人使用循环队列实现,有人使用链表实现。本章将使用数组的回溯算法实现选猴王的算法程序。,20.1 问题描述,有M只猴子围成一圈,每只各一个从1到M中的编号,打算从中选出一个大王;经过协商,决定出选大王的规则:从第一个开始循环报数,数到N的猴子出圈,最后剩下来的就是大王。在本章,我们以此问题作为研究对象,通过编写程序,来输出站成一圈猴子的出圈顺序号。,20.2 问题分析及实现,20.2.1 问题分析20.2.2 问题实现20.2.3 程序运行,20.2 问题分析及实现,拿

10、到这个算法问题,首先想到的前面提到的要领:看清、想明、把握每一个细节。根据问题描述可知,我们要实现的是输出猴子出圈的顺序。简单举例:9个猴子数到3出圈,则应打印:3,6,9,以下将仔细地分析问题并实现算法。,20.2.1 问题分析,而我们的将要开发的程序,就是为了使这些猴子最后留下大王,每个淘汰出圈的猴子。这里将猴子进行顺序编号。假设猴子编号从1开始至30,则以数到3为例,从1开始数猴子,至第三只猴子时,出圈,此时,圈子应该有1,2,4,5,630,则继续从第4只从头数起,将第4只猴子做为第1号,依此类推,这样,就产生了出圈的顺序号:3,6,9,12,15.29,那么最后出圈的猴子即为猴王。,

11、20.2.2 问题实现,本小节就通过编程来实现此问题,实现的代码如下。1.让猴子站成一圈如何让猴子站成一圈呢?根据问题分析结果,采用整型一维数组中保存猴子顺序号,即表示站成一排。代码如下(代码20-1.txt)。,20.2.2 问题实现,01#include02#include03#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、猴子站成一圈*/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.回溯法求猴子出圈顺序在主程序中,要求

13、用户输入出队序数,即数到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 开发过程常见问题及解决,开发过程常见问题及解决办法如下,仅供参考。有时,如果程序修改后,查看不到结果的变化,需要仔细阅读程序,看是否有地方修改错误。此程序的难点之一是如何正确理解回溯算法,这是程序设计中的一个难点。本章的算法,类似于堆栈的概念,要从这个方面理解会容易的多,通过回溯求解,把数组看作是后进先出的堆栈,将求出的第一个解放置到数据最末,即“栈”底部,最后一个解放置到“栈”顶,但输出结果时,从“栈”底输入。,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 建筑/施工/环境 > 项目建议


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号