Ⅰ. 系统生命周期 | SYSTEM LIFE CYCLE
0x00 需求
一组定义 Project 目的的规格；输入 / 输出。
0x01 分析
将问题分解为可管理的部分；自下而上 / 自上而下 的设计。
0x02 设计
抽象数据类型的创建；算法规范和算法设计策略的考虑（与语言无关）。
0x03 完善代码
对数据对象选择表示的方式，并为它们的每个操作编写算法。
数据对象的表示方法可以决定与之相关算法的效率。
0x04 检查
验证程序设计的正确性，利用各种测试用例来测试程序。
消除错误，性能分析（运行时间，所占内存）。
Ⅱ. 算法规范 | Algorithm Specification
0x00 介绍
定义：算法是一组有限的指令，如果遵循这些指令，可以完成特定的任务。
所有算法都必须满足以下标准：
（1）输入 （2）输出 （3）确定性 （4）有限性 （5）有效性
算法 / 程序（过程）
如何设计算法？ 自然语言 → 流程图 → 程序语言
0x01 例子 - 选择排序
Sorting a set of n≥1 integers
💬 从一组未排序的整数中找出最小的，并将其放在排序列表的下一个位置。
for (i = 0; i < n; i++) { 检查 list[i] 到 list[n-1] 并假设最小的整数在 list[min] 处; 交换 list[i] 和 list[min] 的值; }
📚 步骤：
Step1：找到最小的整数
Step2：交换
📜 函数版本：
void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } Swap(&a, &b);
📜 宏版本：
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))
📌 都准备好了，我们可以开始写选择排序了：
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t)) void Sort(int list[], int n) { int min = 0; int tmp = 0; int i = 0; int j = 0; for (i = 0; i < n - 1; i++) { min = i; for (j = i + 1; j < n; j++) { if (list[j] < list[min]) { min = j; } SWAP(list[i], list[min], tmp); } } }
🔑 解读：函数 Sort 对一个 n≥1 的整数数组进行排序，结果保留在 list[0]，... ，list[n-1] 中。最后达到要求 list[0]≤list[1]≤ . . . ≤list[n-1] 。
0x02 例子 - 二分查找
查找目标值是否在列表中，如果在，返回该整数的下标，否则返回 -1 （升序）
将列表的中间值和目标值进行对比，有三种情况：
① 目标值 ＜ 中间值
如果目标值存在且位置在 left 和 middle - 1 之间，将 right 设为 middle - 1 。
② 目标值 ＝ 中间值
找到了，返回 middle。
③ 目标值 ＞ 中间值
如果目标值存在且位置在 middle + 1 和 right 之间，将 left 设为 middle + 1 。
📜 分析：
循环（还有整数没检查完） { 中间值 = （左 + 右） / 2; 如果真（目标值 < list[中间值]） 右 = 中间值 - 1; 或者（目标值 == list[中间值]） 返回 中间值; 否则 左 = 中间值 + 1; }
📌 处理 return：
< -1
= return 0
> 1
📜 函数的方式实现：
int cmp(int x, int y) { if (x < y) { return -1; } else if (x == y) { return 0; } else { return 1; } }
📜 宏的方式实现：
# define CMP (x,y) ((x) < (y)) ? -1: ((x) == (y)) ? 0: 1)
💬 代码实现：
int BinarySearch(int list[],int targetNum, int left, int right) { int middle = 0; while (left <= right) { middle = (left + right) / 2; switch(Compare(list[middle], targetNum)) { case -1: left = middle + 1; break; case 0: return middle; break; case 1: right = middle - 1; break; } } return -1; }
0x03 递归算法 | Recursive Algorithms
【直接递归】
【间接递归】
📚 递归是一种通用的控制方案，通常递归函数相较于其迭代函数更容易理解，许多问题可以以自然的方式进行递归定义。
二项式系数：
可以通过以下公式递归计算：
比如阶乘、二分查找、斐波那契数列……
💬 排列组合：
我们可以通过打印来构建排列组合的集合。
(1) a后面是(b, c, d)的所有排列组合
(2) b后面是(a, c, d)的所有排列组合
(3) c后面是(a, b, d)的所有排列组合
(4) d后面是(a, b, c) 的所有排列组合
💬 我们先来看一下斐波拉契数列的迭代法实现：
int Fib(int n) { int a = 0; int b = 0; int c = 0; if (n > 1) { a = 0; b = 1; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } } else { c = n; } return c; }
💬 递归的方法实现斐波那契数列：
int rFib(int n) { if (n > 1) { return rFib(n - 1) + rFib(n - 2); } else { return n; } }
💬 递归版本的二分查找：
int BinarySearch(int list[],int targetNum, int left, int right) { int middle = 0; if (left <= right) { middle = (left + right) / 2; switch(Compare(list[middle], targetNum)) { case -1: return BinarySearch(list, targetNum, middle + 1, right); case 0: return middle; case 1: return BinarySearch(list, targetNum, left, middle - 1); } } return -1; }
💬 排列组合：
void perm(char *list, int i, int n) { /* 生成 list[i] 到 list[n] 的所有排列组合 */ int j, temp; if (i == n) { for (j=0; j<=n; j++) { printf("%c", list[j]); } printf(" "); } else { /* list[i] 到 list[n] 有一个以上的排列组合，递归生成这些排列组合 */ for (j=i; j<=n; j++) { SWAP(list[i], list[j], temp); perm(list, i+1, n); SWAP(list[i], list[j], temp); } } }
参考资料：
Fundamentals of Data Structures in C
本章完。
