终于考完两种英语等级考试了，有大把的时间来填坑了~

本文属于自用笔记，假如对于你有帮助的话，鄙人万分荣幸。若有补充，请在评论区留言~

第二章 算法

1、简单的算法举例

【例2.1】求1×2×3×4×5

算法步骤

1. 令p=1，或写成1=>p(表示将1存放在变量p中)
2. 令i=2，或写成2=>i(表示将2存放在变量i中)
3. 使p与i相乘，乘积仍放在变量p中，可表示为: p*i=>p
4. 使i的值加1，即i+1=>i
5. 如果i不大于5，返回重新执行3及其后的步骤4和5；否则，算法结束。最后得到p的值就是5!的值

若题目改为: 求1×3×5×7×9×11

算法步骤

1. 令p=1，或写成1=>p(表示将1存放在变量p中)
2. 令i=3，或写成3=>i(表示将3存放在变量i中)
3. 使p与i相乘，乘积仍放在变量p中，可表示为: p*i=>p
4. 使i的值加2，即i+2=>i
5. 如果i≤11，返回3；否则，结束。或者 若i＞11，结束；否则，返回3

【例2.2】有50个学生，要求输出成绩在80分以上的学生的学号和成绩

n：表示学生学号

下标i：表示第几个学生

n1：表示第一个学生的学号

ni：表示第i个学生的学号

g：表示学生的成绩

g1：表示第一个学生的成绩

gi：表示第i个学生的成绩

算法步骤

1. 1=>i
2. 如果gi≥80，则输出ni和gi，否则不输出
3. i+1=>i
4. 如果i≤50，返回到2，继续执行，否则，算法结束

【例2.3】判定2000—2500年中的每一年是否为闰年，并将结果输出

解题思路

算法步骤

1. 2000=>year
2. 若year不能被4整除，则输出year 的值和“不是闰年”。然后转到6，检查下一个年份
3. 若year能被4整除，不能被100整除，则输出year的值和“是闰年”。然后转到6
4. 若year能被400整除，输出year的值和“是闰年” ，然后转到6
5. 输出year的值和“不是闰年”
6. year+1=>year
7. 当year≤2500时，转2继续执行，否则算法停止

【例2.4】求 1- 1/2 + 1/3 - 1/4 + ⋯ + 1/99 - 1/100

sign：表示当前项的数值符号

term：表示当前项的值

sum：表示当前项的累加和

deno：表示当前项的分母

算法步骤

1. x graph TD;​A([开始])​B[问题分析]​C[设计算法]​D[编写程序]​E[对源程序进行编辑, 编译和连接]​F[运行程序分析结果]​G[编写程序文档]​H([结束])​A –> B –> C –> D –> E –> F –> G –> Hmermaid
2. sum=1
3. deno=2
4. sign=(-1)^sign
5. term=sign^(1/deno)
6. sum=sum+term
7. deno=deno+1
8. 若deno≤100返回4；否则算法结束

【例2.5】给出一个大于或等于3的正整数，判断它是不是一个素数

解题思路

所谓素数，是指除了1和该数本身之外，不能被其他任何整数整除的数。

算法步骤

1. 输入n的值

2. i=2（i作为除数）

3. n被i除，得余数r

4. 如果r=0，表示n能被i整除，则输出n“不是素数”，算法结束；否则执行5

5. i+1=>i

6. 如果i≤√𝑛，返回3；否则输出n的值以及“是素数”，然后结束

实际上，n不必被2 ~ (n-1)之间的整数除，只须被2 ~ n/2间整数除即可，甚至只须被2~√𝑛
之间的整数除即可。

2、算法的特性

• 有穷性：一个算法应包含有限的操作步骤，而不能是无限的
• 确定性：算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的
• 有零个或多个输入：所谓输入是指在执行算法时需要从外界取得必要的信息
• 有一个或多个输出：算法的目的是为了求解，“解” 就是输出
• 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果

3、怎么表示一个算法

用流程图表示算法

【例2.6】将例2.1的算法用流程图表示。求1×2×3×4×5。

graph TD;

A([开始])

B[1=>p]

C[2=>i]

D[p*i=>p]

E[i+1=>i]

F{i>5}

G[/输出p/]

H([结束])

A --> B --> C --> D --> E --> F --Y--> G --> H ; F --N--> D

传统流程图的弊端

看图就完事了，一团乱麻

流程图三种基本结构

顺序结构

graph TD;
A-->B

选择结构

graph TD;
A{P}--真-->B[A];A--假-->C[B];

循环结构

graph TD;
A{P}--真-->B[A];B-->A;A--假-->C[B]

用N-S流程图表示算法

用伪代码表示算法

【例2.7】求5!，用伪代码表示。

1
2
3
4
5
6
7
8
9

begin	(算法开始)
    1=>p
    2=>I
    while i≤5
    {    p*i=>p
         i+1=>I
    }
    print p
end	(算法结束)

【例2.8】求 1−1/2+1/3−1/4+⋯+1/99−1/100，用伪代码表示。

1
2
3
4
5
6
7
8
9
10
11
12

begin	(算法开始)
    1=>sign
    1=>sum
    2=>deno
    while deno≤100
    {    (-1)*sign=>sign
         sign*(1/deno)=>term
         sum+term=>sum
         deno+1=>deno
    }
    print sum
end	(算法结束)

用计算机语言表示算法

【例2.9】将例2.7表示的算法（求5!）用C语言表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <stdio.h>
int main()
{
	int i,p;
	p=1;
	i=2;
	while(i<=5)
		{
			p=p*i;
			i=i+1;
		}
	printf(″%d\n″,p);
	return 0;
}

【例2.10】将例2.8表示的算法求1-1/2+1/3-1/4+⋯+1/99-1/100的值用C语言表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <stdio.h>
int main()
{
	int sign=1;
	double deno=2.0,sum=1.0,term;
	while(deno<=100)
		{
			sign=-sign;
			term=sign/deno;
			sum=sum+term;
			deno=deno+1;
		}
	printf(″%f\n″,sum);
	return 0;
}

4、总结

1. 算法 + 数据结构 = 程序。程序设计有4个要素：算法是灵魂，数据结构是加工对象，语言是工具，编程采用结构化程序设计方法。算法是解题方法的精确描述。
2. 表述算法可以用：自然语言、传统流程图、结构化流程图、伪代码和计算机语言等工具。
3. 结构化程序的三种基本结构是：顺序结构、选择结构和循环结构。由三种基本结构可以构成一个结构化程序。
4. 写出程序只是用计算机语言表示了算法，只有运行程序才是实现了算法。
5. 对于规模较大任务，应当采取结构化程序设计方法，其要要点是：自顶向下，逐步细化。在编程时还要注意用模块化设计和结构化编程。