《计算机是怎么跑起来的》第五章读后小结

Lihua奏

发布于 2026-06-23 20:27:55

890

《计算机是怎么跑起来的》第五章读后小结

什么是算法

这章讲的是算法

那么什么是算法呢?用通俗一点的话来说,就是“把解决问题的步骤无一遗漏地用文字或者图表描述出来”。在这里,也可以理解成“用编程语言描述出来”,而且有个前提,步骤必须明确,并且步骤数有限。

最大公约数

比如,求出 12 和 42 的最大公约数,按照平时的想法,就是不断地寻找两个数字都能被除以的数

这能算作算法吗?不能！这更像是我们人类的思考方式。计算机只是一个严格按照规则执行的执行者,上面的解决办法步骤还不够明确,因为你并不知道下一个能被除以的数具体是多少。

那么具体怎么解决？用辗转相除法

代码:

a = 12
b = 42
while a != b:
 if a > b:
  a -= b
 else:
  b -= a
print(f"最大公约数是{a}。")

判断素数

那么再看一题,91是否是素数(除了1和它本身可以被除尽,其他数都不行)

一般正常的想法,就是从2开始,除不尽就+1再去除,一次次去试。这在我们的视角来看很麻烦,但对于计算机来说却很快。

a = 91
ans = "是素数。"
n = 2
n_max = a - 1
while n <= n_max:
 if a % n == 0:
  ans = "不是素数。"
  break
 n += 1
print(f"{a}{ans}")

所以,在设计算法的时候可以记住一件事:可以利用计算机的处理速度来解决问题。

同一个问题的不同算法

解决同一问题的算法未必只有一种。一般来说,执行时间越短、占用内存越少的算法就更优。(这还涉及到“时间换空间,空间换时间”,这里不讲)

举个常见例子: 从 1 加到 100

//正常思路
int num = 0
for(int i = 1; i <= 100 ; i++) {
 num += i
}

//公式
int i = 100
int num = (i + 1) * i/2

第一个要循环100次,第二个只执行一次,谁优谁劣,一看便知。

哨兵

最后一个是哨兵，这个技巧多用于顺序查找。

举例:假设有编号为1～100的100只箱子，每只箱子中都装着一个写有数字的纸条。现在我们要从这100只箱子当中找出写有特定数字的纸条

先是不用哨兵的流程图

使用哨兵的流程图

光看图可能还不太好理解,来看代码。

int target = 81;
int[] box = new int[101]; 
boolean found = false;
int i = 1;
while (i <= 100) {
    if (box[i] == target) {
        found = true;
        break;
    }
    i++;
}
if (found) {
    System.out.println("找到了，位置是 " + i);
} else {
    System.out.println("没找到");
}

int target = 81;

int[] box = new int[102];

box[101] = target; // 哨兵放在末尾

int i = 1;
while (box[i] != target) {
    i++;
}
// 退出循环时，要么 i<=100 且真找到，要么 i==101 表示没找到
if (i == 101) {
    System.out.println("没找到");
} else {
    System.out.println("找到了，位置是 " + i);
}