L3_04 算法与描述

一、枚举法

1.1 概念

枚举法是一种逐一尝试所有可能解的算法。

1.2 适用场景

• 问题的解空间有限
• 需要找到所有可能的解

1.3 示例：查找数组中的最大值

#include <iostream>
using namespace std;

int findMax(int arr[], int size) {
    int max_val = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }
    return max_val;
}

int main() {
    int arr[] = {3, 7, 2, 9, 5};
    cout << "最大值: " << findMax(arr, 5) << endl;
    return 0;
}

---

二、模拟法

2.1 概念

模拟法是通过模拟实际过程来解决问题的方法。

2.2 适用场景

• 需要模拟真实世界的过程
• 问题可以通过逐步模拟解决

2.3 示例：模拟掷骰子

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0));
    
    int count[7] = {0};  // 统计每个点数出现的次数
    
    for (int i = 0; i < 1000; i++) {
        int dice = rand() % 6 + 1;
        count[dice]++;
    }
    
    for (int i = 1; i <= 6; i++) {
        cout << "点数 " << i << ": " << count[i] << " 次" << endl;
    }
    
    return 0;
}

---

三、自然语言描述

3.1 定义

用人类语言描述算法的步骤。

3.2 示例

算法：计算数组元素之和
1. 初始化一个变量 sum，值为 0
2. 遍历数组中的每个元素
3. 将当前元素的值加到 sum 中
4. 遍历结束后，sum 即为数组元素之和

---

四、流程图描述

4.1 定义

用图形符号表示算法的逻辑流程。

4.2 示例：计算阶乘

开始 → 输入 n → 初始化 factorial = 1, i = 1
       ↓
    判断 i ≤ n？
       ├─ 是 → factorial = factorial × i → i = i + 1 → 返回判断
       └─ 否 → 输出 factorial → 结束

---

五、伪代码描述

5.1 定义

用类似编程语言的结构描述算法，但不依赖具体语法。

5.2 示例：冒泡排序

算法：冒泡排序
输入：数组 arr，长度 n
输出：排序后的数组

FOR i FROM 0 TO n-2
    FOR j FROM 0 TO n-2-i
        IF arr[j] > arr[j+1]
            SWAP arr[j] AND arr[j+1]
        END IF
    END FOR
END FOR

RETURN arr

---

六、算法复杂度分析

6.1 时间复杂度

• O(1)：常数时间
• O(n)：线性时间
• O(n²)：平方时间
• O(log n)：对数时间

6.2 空间复杂度

• O(1)：常数空间
• O(n)：线性空间

6.3 示例分析

// O(n) 时间复杂度
int sum(int arr[], int n) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += arr[i];
    }
    return s;
}

---

七、示例程序：猜数字游戏

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0));
    int secret = rand() % 100 + 1;
    int guess;
    int attempts = 0;
    
    cout << "猜数字游戏！" << endl;
    
    do {
        cout << "请输入猜测的数字 (1-100): ";
        cin >> guess;
        attempts++;
        
        if (guess < secret) {
            cout << "太小了！" << endl;
        } else if (guess > secret) {
            cout << "太大了！" << endl;
        } else {
            cout << "恭喜猜对了！用了 " << attempts << " 次" << endl;
        }
    } while (guess != secret);
    
    return 0;
}