Menu Close

程序设计和算法

程序是一组计算机能够识别的指令。每一条指令使计算机执行特定的操作,只要执行这个操作,计算机就会“自动”的完成其它指令。使其成为你要实现的功能! 一个特定的指令序列用来完成一定的功能。程序设计是给出解决特定问题程序的过程,是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具,给出这种语言下的程序。程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。

一个程序应包括:

  • 对数据的描述。在程序中要指定数据的类型和数据的组织形式,即数据结构(data structure)。
  • 对操作的描述。即操作步骤,也就是算法(algorithm)。

我们学习计算机软件的学生,特别是网站设计的学生,都应该知道google的算法。这个算法始终在世界算法的前沿。

谷歌算法
谷歌算法

谷歌算法从所有链接都考虑,到相关链接,当地相关和质量链接,社区网站,FAQs, 相互交流,手机网站,SSL安全链接,用户行为,到人工智能自然匹配算法。还有谷歌的alpha狗算法逐渐应用于军事领域。

程序设计步骤

1. 分析问题
对于接受的任务要进行认真的分析,研究所给定的条件,分析最后应达到的目标,找出解决问题的规律,选择解题的方法,完成实际问题。
2.设计算法
即设计出解题的方法和具体步骤。
3.编写程序
将算法翻译成计算机程序设计语言,对源程序进行编辑、编译和连接。
4.运行程序,分析结果
运行可执行程序,得到运行结果。能得到运行结果并不意味着程序正确,要对结果进行分析,看它是否合理。不合理要对程序进行调试,即通过上机发现和排除程序中的故障的过程。
5.编写程序文档
许多程序是提供给别人使用的,如同正式的产品应当提供产品说明书一样,正式提供给用户使用的程序,必须向用户提供程序说明书。内容应包括:程序名称、程序功能、运行环境、程序的装入和启动、需要输入的数据,以及使用注意事项等。

软件开发生命周期 (System Development Life Cycle, SDLC)

软件开发生命周期,SDLC 是的缩写形式。这是一个定义良好的结构化的软件工程预定的产品软件开发中的阶段序列.

SDLC活动

软件开发生命周期提供了一系列的步骤,为设计和开发一个软件产品有效地要遵循。SDLC 框架包括以下步骤:

%title插图%num

通信

这是的第一步在哪里用户启动的请求所需的软件产品。他联系服务提供商,并试图通过谈判条款。他提交请求给服务提供商.

要求收集

这一步将进行软件开发团队。团队从问题域持有与各利益攸关者进行讨论,并试图带出尽可能多的信息可能对他们的要求。要求都是设想和隔离到用户需求、 系统需求和功能需求。下列是使用的一些做法 –

  • 研究现有的或已过时的系统和软件,
  • 对用户和开发人员,进行面谈,
  • 指的数据库或
  • 收集的问卷中回答了

可行性研究

需求收集后,球队又发表了软件过程的一个粗略的计划。在此步骤中该球队的分析,如果软件可以制成以满足用户的所有要求,并且如果存在的软件是没有更多的有用的任何可能性。据发现,如果该项目在财务上,实际上和技术上可行的组织以。有很多算法可用,这有助于开发人员得出结论:一个软件项目的可行性.

系统分析

在这一步的开发者决定他们计划的路线图,并尝试提出适合该项目的最好的软件模型。系统的分析包括了解软件产品的限制,学习系统相关的问题或变化将在现有的系统中之前进行,识别并解决项目对组织人事等团队项目的影响分析项目的范围,并计划进度和相应的资源。.

软件设计

下一步是关闭的要求,整个知识和分析的桌子上,设计出的软件产品。从用户和信息聚集在需求收集阶段的输入是该步骤的输入。该步骤的输出可以有两种设计形式;逻辑设计和物理设计。工程师产生的元数据和数据字典,逻辑图,数据流图并在某些情况下伪码.

编码

这个步骤也被称为编程阶段。软件设计的执行开始在写程序代码中的适当的编程语言和有效显影无差错的可执行程序的条款.

测试

估计说,整个软件开发过程中的50%应被测试。错误可能会毁了从关键级软件自身删除。软件测试是同时由开发商编码和全面的测试由测试专家在不同级别的代码,如模块测试,程序测试,产品测试,内部测试和测试产品在用户端进行完成的。早期发现的错误和他们的补救措施是关键可靠的软件.

整合

软件可能需要使用的库,数据库和其它程序(次)进行集成。 SDLC的这个阶段是参与的软件与外部世界的实体的结合.

实施

这意味着安装在用户机器上的软件。有时,软件需要在用户端安装后的配置。软件的可移植性和适应性和整合有关问题的测试在实施过程中得到解决.

操作和维护

此阶段确认了软件的操作中的更高的效率和更低的错误条件。如果需要,用户进行培训,或者资助对如何操作软件,以及如何保持软件业务的文档。该软件被维持及时通过根据发生在用户端的环境或技术的变化更新的代码。这个阶段可能会面临来自隐藏的bug和现实世界的挑战.

处置

随着时间的经过,该软件可以拒绝对性能前方。它可能会完全过时或可能需要强烈了层次。因此,迫切需要消除系统的主要部分就产生了。这个阶段包括数据归档和必要的软件组件,逼抢系统,规划配置的活动,并在终端系统的适当时间终止系统.

算法(algorithm)是程序设计的灵魂

算法是利用计算机解决问题的处理步骤,简而言之,算法就是解决问题的步骤。算法不仅仅用于计算机的数据处理,现实世界中的各种问题也需要结合算法的概念来解决。算法可以有多种,一般采用简单和运算步骤少的。准确、高效

%title插图%num

为什么要学习算法?

学习算法的同时能提高自己的编程能力。一个好的算法是编写程序的模型,因为它能创造计算机程序,其中还包含了程序的精髓。学过算法的人写出的程序和没学过算法的人写出的程序有明显的差距。要写出既能正确执行又能提高效率的好程序,算法的学习是不可或缺的。

算法的学习类似于学习游戏攻略,有了攻略就能轻松取得游戏的成功。

算法的特性

1) 输入输出

算法具有零个或者多个输入,同时,算法具有至少一个的输出。对于在屏幕上打印”Hello World”一样,你可以不需要有任何的输入,直接输出得到结果即可,而对于一个没有输出的算法,没有任何意义。

2) 确定性

算法的每一步都具有确定的含义,无二义性。任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得到相同的输出。

请注意,如果算法的目的是产生一个随机数字,每一次运行产生了不同的结果,看上去好像违反了算法确定性原则,但计算机产生随机数亦是使用一种(或多种)算法解决,以线性同余产生随机数为例,其利用了CPU时间的不同产生的不同的结果,当CPU的时间完全一样的时候依旧会产生相同结果,只不过人类无法察觉到如此精确的时间区别。

3)有穷性

一个算法总是需要(输入合法的情况下)在有限的步骤结束,即每个算法需要在有穷的时间内完成。

这是算法与程序的最主要的区别,程序可以无限制循环的执行下去。对于此,你可以理解为一个算法必须要有一个”边界“,即使一个算法需要计算机连续运算50年,但依旧是有穷的,只不过这个算法意义已经不是很大了。

4)可行性

一个算法是可以被执行的,即算法中的每个操作都可以通过已经实现的基本运算执行有限的次数完成。尽管在目前计算机解存在着没有实现成功的极为复杂的算法,但是并不能说的上是无法实现,只不过是受到现在的工具和人类的大脑限制了,这属于理论研究的范围。

%title插图%num

算法设计要求

1) 正确性

正确性(Correctness)指的是该算法能够满足预先指定的功能与性能的需求,即能够得到正确答案。其大致可以分为以下四点:

a)该算法中不含任何语法错误。

b)程序对于几组输入数据能够得到满足需求的结果。

c)程序对于非法的输入也能够得到满足需求说明的结果(如抛出异常)。

d)程序对于精心挑选的严苛数据依旧能够产生满足需求的结果。

2)健壮性

健壮性(Robustness)指的是当输入数据不合法时,算法也能做出相关的处理,而不是产生不可预计的效果。

3)可读性

可读性(Readability)指的是算法是可以阅读,理解和交流的。

4)耗时低,占用空间少

运行时间(Running time)与占用空间(Storage space)概念,在设计算法时,我们总是希望能够更少的使用时间和空间达成我们的目标。我们算法与数据结构的研究的重点就是为了让程序运行块,占用空间低。

 

怎么样的解决问题方案才称为算法?

一 、 算法必须具备两个重要条件:

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

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

 

二、 计算机算法类别

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

 

三、 怎样用流程图表示表示一个算法

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

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

%title插图%num

四、算法有哪些例子?

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

 

 

五、三种基本结构图

  1. 顺序结构

%title插图%num

2. 选择结构

选择结构
选择结构

3. 循环结构

循环结构

 

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

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

结构化程序设计

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

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

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

简单算法举例

举例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 整除的年份;

闰年算法
闰年算法

判定 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

 

算法的魅力

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

%title插图%num

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

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

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

%title插图%num
相比第一份答案,我们进行了100次的运算,才得出我们想要的结果,而对于第二份答案,我们仅进行了1次运算就得到了想要的结果,而在实际中计算机的计算远远不止这点计算量,以此如果我们去计算1到1000000的和呢?使用了等差数列还是一步算好,而这就是算法的魅力。

什么是好的算法?

%title插图%num

如下算法用for LOOp或递归函数打印出1到N的全部整数,如果在100个以内,没有任何问题。但是当需要打印出一万个甚至十万个以上的整数时,递归函数的算法直接罢工。

因为它占用太多的空间。

%title插图%num

Posted in C语言, C语言

1 Comment

发表评论

相关链接