百科生活 投稿
关于【算法分析与设计】，什么是算法分析与设计，今天小编给您分享一下，如果对您有所帮助别忘了关注本站哦。
- 内容导航：
- 1、信息学例题讲解-验证哥德巴赫猜的逻辑分析和算法设计
- 2、什么是算法分析与设计
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语言程序，来验证“猜想”的正确性
问题分析：
拿到一个要求实现的算法问题，首先要看清、想明、把握每一个细节。只有这样，才可以顺利地将算法实现。由问题描述：“每个不小于6的偶数都可以表示为两个奇素数之和”，可知，我们要实现的是判断任何一个大于6的偶数都可以有两个素数相加。以下将仔细地分析问题并实现算法。
而我们的将要编写的程序，就是为了验证哥德巴赫猜想中提到的任何一个偶数，对大于6的偶数n可以分解成两个素数的和，这个结论是否正确。所以，程序应该可以输入一个数，判断是否为偶数，将这个偶数分解成一个小素数和大素数。再分别判断小素数与大素数之合是否就等于这个偶数。而且，需要将结果打印输出。
我们在编程之前，需要明确两个数学概念：素数和偶数。
⑴ 素数就是质数，指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和数自身）的自然数即为素数。
⑵ 偶数就是能被2整除的自然数，如2、4、6、8……。
根据题目，要求是奇素数，即这个素数不可以是2，一定要大于2。我们需要划分以下两个子模块。
⑴ 判断一个数是否为素数。
⑵ 判断并分解大小素数的和是否等于需判断的偶数。
编程实现：
1、判断输入的数字是否是偶数
对于一个任何自然数，如何判断他是素数呢？如果这个自然数n，它能被 2 整除，那么它就是偶数，否则就是一个奇数，能被整除，说明这个数除以2的余数是 0,我们可以用 求模(%)运算。那么，根据这个思路，代码如下
int isEven(int num) {if(num % 2 == 0){return 1;}else{return 0;}}
2、判断输入的数字是否是素数
对于一个任何自然数，如何判断他是素数呢？对于一个自然数n，如果不存在一个大于1小于n且能被n整除的数，那么这个数就是一个偶数。那么，根据这个思路，代码如下
编程实现： 问题要求用户输入，判断，并输出结果。 因此在主程序中，要求用户输入一个大于6的偶数，调用判断函数，判断“猜想”是否成立，成立则输出等式，不成立则输出“猜想”错误。代码如下 1、此程序的难点之一是如何判断一个数为素数。 2、此程序另一难点是分解成素数。其实就是从最小素数开始，将最小素数i作为素数A，将偶数减i作为素数B，在A、B都是素数的情况下，分解成功 拓展： 以上是验证一个二重哥德巴赫猜想的程序，根据此解题思路，修改该程序，实验对三重哥德巴赫的验证！ 2.算法正确性名词解释：对每一个输入实例算法都能终止，并给出正确输出。 算法正确性有两个要素；1是能够终止。2是结果正确。 算法设计和分析的步骤可概括: 问题的陈述模型的选择算法的设计算法的程序实现算法分析。 算法具有以下五大特性 确定性有穷性可行性输入输出。 循环不变式具有以下三个性质名词解释： 初始名词解释：在循环的第一次迭代之前，循环不变式为真。 维持名词解释：如果在循环的某次迭代之前循环不变式为真，那么在下一次迭代之前，循环不变式仍然为真。 终止名词解释：当循环终止时，循环不变式给出有用性质，这个性质可以用于证明算法的正确性 3.算法分析名词解释：是指对一个算法所需要的计算机资源进行预测。 考虑算法的好坏主要有以下几点名词解释：执行算法所耗费的时间。执行算法所耗费的存储空间，其中主要考虑辅助存储空间。算法应易于理解，易于编码，易于调试等。 最重要的计算资源是时间和空间资源(存储器) 输入规模是输入元素的个数、用二进制表示的输入的总位数、和用图中顶点数和边数表示输入。4.运行时间名词解释：是指在某个输入时，算法执行操作的次数或者步数。 影响程序运行时间的主要因素 名词解释：程序的输入由编译系统所产生的代码程序的质量执行程序的计算机机器指令的性能与速度程序所依据的算法的时间复杂度。5.最坏情况名词解释：是指算法的运行时间是任一输入运行时间的上界。 算法最坏情况下的运行时间，即对于规模n的任何输入，算法运行最长的时间。之所以这样，是由于以下三个原因名词解释：1、算法的最坏情况运行时间是任一输入运行时间的上界 2、对于某些算法，最坏情况经常出现 3、算法的“平均情况”性能常常与最坏情况大致相同。 6.渐进表示名词解释：是方便地表示算法的最坏情况下，计算的复杂度。 算法的复杂性测度主要有两个方面名词解释：(1) 空间复杂度 (2) 时间复杂度 7.递归名词解释：对自己的调用。 8.动态名词解释：是所作的决策可能依赖当前状态，而此前所作的决策无。 9.规划名词解释：意味着一系列的决策。 动态规划算法的研制可由4步组成名词解释：(1)刻画最优解的结构(2)递归定义最优解的值(3)以自底向上(或自顶向下)的方式计算最优解的值(4)根据计算的结果，构造问题最优解。 10.前缀码名词解释：如果我们只用0／1对字符进行编码，并限定任一字符的编码都不是另一个字符编码的前缀，则称这样的编码为前缀码 11.哈夫曼编码名词解释：哈夫曼提出的贪心算法可以构造最优前缀编码，这样产生的编码称为哈夫曼编码。 12.最优子结构:如果问题的最优解包含子问题的最优解，则问题展示了最优子结构。 13.贪心选择的性质:通过局部最优选择(贪心)，可以得到问题的全局最优解。 14．在矩阵链乘问题中，能对矩阵进行分割的叫非平凡矩阵链乘。 15．在矩阵链乘问题中，不能对矩阵进行分割的叫平凡矩阵链乘。 16．动态规划算法的运行时间取决于两个因素的乘积: 17．特点名词解释：此方法的主要特点是通过采用表格技术。计算所有子问题的解。计算的过程从小问题到大问题，并将计算结果存储在一张表中。 18．优点名词解释：一旦一个子问题被解决，就存储其结果，此后遇到同样的子问题，就不再重复计算。用多项式算法代替指数算法。 19．应用名词解释：动态规划典型的应用领域是组合优化问题。 本文关键词：什么叫算法设计，什么是算法分析与设计分析，什么是算法分析与设计，《算法设计与分析》，算法和算法分析。这就是关于《算法分析与设计，什么是算法分析与设计（信息学例题讲解-验证哥德巴赫猜的逻辑分析和算法设计）》的所有内容，希望对您能有所帮助！int isPrime(int num) { if(num == 2){ return 0; } for(int i=2;iint main(){ int num; do{ printf("请输入一个大于 6 的偶数："); scanf("%d",&num); }while(num < 6 || !isEven(num)); for(int i=3;i2、什么是算法分析与设计
是将转入转换成输出的计算步骤所组成的序列或描述输入输出关系的特定计算过程。
- 最近发表