Menu Close

怎么样的解决问题方案才称为算法?算法基本结构图

1. 算法必须具备两个重要条件:

有效性:算法必须要为给定的任务给出正确的结果,即,有满足条件的输入值时,此算法一定要保证正常工作(返回正确的输出值)。表明算法有效性的方法之一就是断点。断点设置在算法的任意位置上,判断此位置是否满足给出的条件,即,程序是否正确运行。

终止性:算法中没有永远反复执行,即,没有无限循环,且不返回答案的情况。算法终止性可以用反复处理结束条件的判断变量,或经过有限次的反复一定能到达结束条件等方法证明。

 

2. 计算机算法类别

1.数值运算算法
2.非数值运算算法

3.怎样用流程图表示表示一个算法

算法如果用流程图符号表示,则直观,简单,易懂。共分为三类结构:

  1. 顺序结构
  2. 选择结构
  3. 循环结构

%title插图%num

4.算法有哪些例子?

给计算机编程带来方便的算法种类繁多,如技术计算(实现技术计算的算法,迪杰斯特拉法,素数,最大公约数)、排序(冒泡、选择、归并、希尔等)、查找(线性、二分法)、字符串模式匹配(KMP算法)本课程的目的是使同学知道怎样编写一个 C 程序,进行编写程序的初步训练,因此,只介绍算法的初步知识。简单来说,任何程序都可以用三种基本结构表示,其优点是结构清晰,易读,提高程序设计质量和效率。

5.三种基本结构图

  1. 顺序结构

%title插图%num

2. 选择结构

选择结构
选择结构

3. 循环结构

循环结构

 

6.三种基本结构的共同特点:

  • 只有一个入口;
  • 只有一个出口;
  • 结构内的每一部分都有机会被执行到;
  • *结构内不存在“死循环”

7.结构化程序设计

基本设计思路:*复杂问题分解成 几个最基本问题,再分别处理。采用的方法:

  • 自顶向下;
  • 逐步细化;
  • 模块化设计:复杂问题按功能分成多个子模块
  • 结构化编码:正确采用三种基本结构实现

 

简单算法举例

举例1: 求 1×2×3×4×5。

最原始方法:
步骤 1:先求 1×2,得到结果 2。
步骤 2:将步骤 1 得到的乘积 2 乘以 3,得到结果 6。
步骤 3:将 6 再乘以 4,得 24。
步骤 4:将 24 再乘以 5,得 120。
这样的算法虽然正确,但太繁。

 

阶乘算法
阶乘算法

改进的算法:
S1: 使 t=1
S2: 使 i=2
S3: 使 t×i, 乘积仍然放在在变量 t 中,可表示为 t×i→t
S4: 使 i 的值+1,即 i+1→i
S5: 如果 i≤5, 返回重新执行步骤 S3 以及其后的 S4 和 S5;否则,算法结束。

如果计算 100!只需将 S5:若 i≤5 改成 i≤100 即可。

如果该求 1×3×5×7×9×11,算法也只需做很少的改动:
S1: 1→t
S2: 3→i
S3: t×i→t
S4: i+2→t
S5:若 i≤11, 返回 S3,否则,结束。

该算法不仅正确,而且是计算机较好的算法,因为计算机是高速运算的自动机器,实现循环轻而易举。

 

例2:判定 2000 — 2500 年中的每一年是否闰年,将结果输出。

润年的条件:
1) 能被 4 整除,但不能被 100 整除的年份;
2) 能被 100 整除,又能被 400 整除的年份;

闰年算法
闰年算法

例3:判定 2000 — 2500 年中的每一年是否闰年,将结果输出

设 y 为被检测的年份,则算法可表示如下:
S1: 2000→y
S2:若 y 不能被 4 整除,则输出 y“不是闰年”,然后转到 S6
S3:若 y 能被 4 整除,不能被 100 整除,则输出 y“是闰年”,然后转到 S6
S4:若 y 能被 100 整除,又能被 400 整除,输出 y“是闰年” 否则输出 y“不是闰年”,然后转到 S6
S5:输出 y“不是闰年”。
S6:y+1→y
S7:当 y≤2500 时, 返回 S2 继续执行,否则,结束。

%title插图%num

用计算机语言表示算法

我们的任务是用计算机解题,就是用计算机实现算法;
用计算机语言表示算法必须严格遵循所用语言的语法规则。

例4. 求 1×2×3×4×5 用 C 语言表示。

main()
{
  int i,t;
  t=1;
  i=2;
  while(i<=5)
  {
    t=t*i;
    i=i+1;
  }
  printf(“%d”,t);
}

例 5 求级数的值。( 作业:同学们列出公式 和描述)

求: 1-1/2 +1/3-1/4…+1/99-1/100

main() 
{ 
    int sigh=1; 
   float deno=2.0,sum=1.0,term; 
   while(deno<=100) 
   { 
      sigh= -sigh; 
      term= sigh/ deno; 
      sum=sum+term; 
      deno=deno+1; 
    } 
    printf(“%f”,sum); 
}

算法的魅力

请你回答一下如何使用计算机C语言编程计算1到100的和(1+2+3+……+100),相信大多数人会直接给出以下答案:

%title插图%num

这几乎是计算机中最为简单的程序了,但是,这样去完成这个功能真的好么?

早在300年前的小学生高斯在课堂上被老师要求去计算这个结果,在同班同学还在手推写结果的时候,高斯早就已经做完了,他利用等差数列求和的算法,轻易打败了同班同学。他的算法很简单,(1+100)/  2 X 100 = 5050

例6. 算法魅力 1到100的加法

#include <stdio.h>
int main() {
int ans=(1+100)*100/2;
printf("%d",ans);
return 0;
}

 

%title插图%num
相比第一份答案,我们进行了100次的运算,才得出我们想要的结果,而对于第二份答案,我们仅进行了1次运算就得到了想要的结果,如果利用递归函数,也可以实现这个结果。

 

%title插图%num

递归函数运算:

int main()
{
    printf("sum of 1 to 100 =%d\n", add(1));
    system("pause");
    return 0;
}

int add(int n)
{
    if (n==100)
    {
        return n;
    }
    return n + add(n+1);

}

%title插图%num

相比第一份答案,我们进行了100次的运算,才得出我们想要的结果( 1+2+3+ … + 100);

而对于第二份答案,我们仅进行了1次运算就得到了想要的结果(高斯算法);

第三份答案中我们让递归函数跑了100次。

而在实际中计算机的计算远远不止这点计算量,以此如果我们去计算1到1000000的和呢?

使用了等差数列一步算好,是最好的解决方法。

如果运算到10万次,使用递归函数将会死机或直接出错。因为它占用太多的空间。

而这就是算法的魅力。

Posted in C语言

发表评论

相关链接