欢迎来到奇葩栖息地!欢迎加入Discord服务器:XfrfHCzfbW本站借助问谛居的服务器搭建,感谢倾情援助。本站处于基础建设阶段,欢迎参与建设工作。不会编辑?请至这里学习Wikitext语法。

算法的基本结构

来自奇葩栖息地
此页面使用了SimpleMathJax扩展渲染的TEX公式。

这些公式被包含在<math><chem>标签中,请稍等片刻等待前端渲染。

算法有三大基本结构:顺序结构分支结构循环结构

顺序结构

顺序结构

顺序结构是一种最简单,最基本的控制结构。我们做一件事情,通常都是按部就班,一步一步来。程序做事也是这么个思路,一个用于特定问题的算法往往有明显的固定流程,计算机从前往后,依次执行所有的操作步骤,不遗漏,不重复。

来看一个例子:读入两个整数a和b,输出a+b的值。

这是一个典型的顺序结构应用。题目怎么说,程序就怎么做。

我们就不分析算法了,看程序理解吧。

1#include <cstdio>
2int a, b;
3int main()
4{
5    scanf("%d%d", &a, &b);
6    int c = a + b;
7    printf("%d\n", c);
8    return 0;
9}

暂时不去探究每行代码的具体含义,我们只需要知道这个代码首先读入了a和b,然后命名了一个变量c并将其赋值为a与b的和,然后输出c,就完成了这一任务。

与此相类似,给出半径计算圆的周长和面积,输入两个数交换他们的值然后输出,都是最基本的顺序结构应用。

分支结构

分支结构

我们生活中难免遇到选择。计算机生活中也难免遇到选择。选择有简单的比如淮安中考数学选择题第一题,也有难的比如选择这里要举什么事例

人类的选择有时要从感性、理性、人际、市场、期望、实用程度等方面综合评判,计算机的选择则明了得多,只要给出条件它便能自动选择最合适的一条路当然也可以用随机来让计算机变得多愁善感

还是看一个简单的例子:读入两个整数a和b,输出a和b中的较大值。

这里的条件很明晰:即判断“a是否大于b”,若判断为“是(true)”则输出a,若判断为“否(false)”则输出b。

 1#include <cstdio>
 2int a, b;
 3int main()
 4{
 5    scanf("%d%d", &a, &b);
 6    if (a > b)
 7        printf("%d\n", a);
 8    else
 9        printf("%d\n", b);
10    printf("%d\n", c);
11    return 0;
12}

可以看到,这个程序中使用了if else语句,这是C++中最基本的分支语句。

类似的,计算机也能处理按成绩打等第、绝对值的计算等问题。

循环结构

循环结构

大部分人类讨厌循环,因为他们觉得很枯燥。但计算机不会觉得枯燥,因为普通计算机1秒能处理几千万次循环

计算机做的大部分任务需要重复多次,这时就要用到循环结构。

依然举个例子:计算1+2+3+...+100(或者说得高大上点,[math]\displaystyle{ \sum_{i=1}^{100} i }[/math])。

因为你没有高斯聪明,所以你不被允许使用公式。[注 1]

这就需要我们从1一直循环到100来计算这一和式的结果。

1#include <cstdio>
2int main()
3{
4    int sum = 0;
5    for (int i = 1; i <= 100; ++i)
6        sum += i;
7    printf("%d\n", sum);
8    return 0;
9}

这个程序中则使用了for语句,也称“直到”型循环,用来表示有固定上下界的循环。(更复杂的程序中for语句的边界也可能随时改变)

但是如果不知道明确的上下界呢?

比如这个例子:求出[math]\displaystyle{ 2^x\ge 100 }[/math]这个不等式中x的最小整数值。

这样我们就要用到while语句,也称“当”型循环,工作原理是给出一个条件,根据条件的真假来判断是否结束循环。

1#include <cstdio>
2int main()
3{
4    int sum = 1, ans = 0;
5    while (sum < 100)
6        sum *= 2, ans++;
7    printf("%d\n", ans);
8    return 0;
9}

当“sum < 100”成立的时候,程序就不断增大指数,直到该条件不成立,也即[math]\displaystyle{ 2^x\ge 100 }[/math]时结束循环,这样即可得到x的最小整数值。

注释

  1. 引用自洛谷P5722题目描述。