贪心算法实战：用C语言解决田忌赛马问题（附完整代码）

在算法设计的浩瀚海洋中，贪心算法以其简洁高效的特性脱颖而出。它就像一位精明的商人，总是在每一步选择中寻求局部最优解，最终期望达到全局最优。今天，我们就以经典的田忌赛马问题为例，深入探讨如何用C语言实现贪心算法，解决这个流传千年的智慧博弈。

田忌赛马的故事大家耳熟能详：田忌与齐王各有上中下三等马匹，通过巧妙安排出场顺序，田忌以弱胜强。将这个策略抽象为算法问题，就变成了如何在双方马匹速度已知的情况下，为田忌设计最优的对阵策略，使其赢得最多银两。

1. 问题建模与算法分析

首先我们需要将问题转化为数学模型。假设田忌和齐王各有n匹马，每匹马的速度已知且各不相同。比赛规则如下：

• 每场比赛双方各派出一匹马，速度快的获胜
• 田忌赢一场得200两，输一场扣200两
• 齐王的马匹按速度从高到低固定出场顺序
• 田忌可以自由安排马匹出场顺序

贪心算法的核心策略可以总结为：

1. 优先用田忌最快的马与齐王最快的马比较
2. 当田忌最快的马不如齐王最快时，用最慢的马去消耗齐王最快的马
3. 速度相等时，比较双方最慢的马

这种策略之所以有效，是因为它总能最大化每场比赛的"收益期望"。下面我们通过一个具体例子来说明：

假设双方各有4匹马，速度如下：

田忌的马速	齐王的马速
10	9
8	7
5	6
2	3

按照贪心策略的对阵顺序应该是：

1. 田忌10 vs 齐王9 → 田忌胜
2. 田忌8 vs 齐王7 → 田忌胜
3. 田忌5 vs 齐王6 → 齐王胜
4. 田忌2 vs 齐王3 → 齐王胜

最终田忌净收益：2002 - 2002 = 0两。虽然看似没有盈利，但这已经是所有可能对阵中最优的结果。

2. C语言实现详解

现在让我们看看如何用C语言实现这个算法。完整的代码实现需要考虑输入处理、核心算法逻辑和结果输出三个部分。

#include <stdio.h>
#include <stdlib.h>

void sort_descending(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] < arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int n;
    printf("请输入马的数量: ");
    scanf("%d", &n);
    
    int tianji[n], qiwang[n];
    
    printf("请输入田忌%d匹马的速度(从快到慢): ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &tianji[i]);
    }
    
    printf("请输入齐王%d匹马的速度(从快到慢): ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &qiwang[i]);
    }
    
    // 确保输入是降序排列
    sort_descending(tianji, n);
    sort_descending(qiwang, n);
    
    int tianji_fast = 0, tianji_slow = n-1;
    int qiwang_fast = 0, qiwang_slow = n-1;
    int money = 0;
    
    while (tianji_fast <= tianji_slow) {
        if (tianji[tianji_fast] > qiwang[qiwang_fast]) {
            // 田忌最快的马比齐王最快的马快
            money += 200;
            tianji_fast++;
            qiwang_fast++;
            printf("田忌%d vs 齐王%d → 田忌胜\n", 
                   tianji[tianji_fast-1], qiwang[qiwang_fast-1]);
        } else if (tianji[tianji_fast] < qiwang[qiwang_fast]) {
            // 田忌最快的马比齐王最快的马慢
            money -= 200;
            tianji_slow--;
            qiwang_fast++;
            printf("田忌%d vs 齐王%d → 齐王胜\n", 
                   tianji[tianji_slow+1], qiwang[qiwang_fast-1]);
        } else {
            // 最快的马速度相等，比较最慢的马
            if (tianji[tianji_slow] > qiwang[qiwang_slow]) {
                money += 200;
                tianji_slow--;
                qiwang_slow--;
                printf("田忌%d vs 齐王%d → 田忌胜\n", 
                       tianji[tianji_slow+1], qiwang[qiwang_slow+1]);
            } else {
                money -= 200;
                tianji_slow--;
                qiwang_fast++;
                printf("田忌%d vs 齐王%d → 齐王胜\n", 
                       tianji[tianji_slow+1], qiwang[qiwang_fast-1]);
            }
        }
    }
    
    printf("\n最终收益: %d两\n", money);
    return 0;
}

这段代码的几个关键点：

1. 输入处理：我们要求用户输入马匹数量，然后分别输入田忌和齐王马匹的速度。为了确保算法正确性，我们添加了一个降序排序函数sort_descending。

2. 指针控制：使用四个指针tianji_fast、tianji_slow、qiwang_fast、qiwang_slow来跟踪当前可用的最快和最慢马匹。

3. 核心逻辑：按照前述的贪心策略进行比赛安排，并根据比赛结果调整银两总数。

4. 详细输出：每一步都打印对战情况和结果，方便调试和理解算法执行过程。

3. 算法优化与边界处理

在实际应用中，我们需要考虑一些边界情况和可能的优化：

输入验证：

• 确保马匹数量n在合理范围内（如1 ≤ n ≤ 100）
• 验证所有马匹速度是否互不相同
• 检查输入是否确实按降序排列

性能优化：

• 使用更高效的排序算法（如快速排序）处理大规模输入
• 可以省略排序步骤，如果输入保证有序
• 添加提前终止条件，当剩余比赛无法改变最终结果时

特殊情况处理：

1. 所有马匹速度相同：

   • 这种情况下无论怎么安排，田忌都无法盈利
   • 最优策略是随意安排，最终收益为0

2. 田忌所有马都比齐王慢：

   • 无论如何安排都会输掉所有比赛
   • 最小化损失的方法是让最快的马尽可能多比赛

3. 田忌所有马都比齐王快：

   • 直接按顺序对阵即可获得最大收益
   • 这种情况收益固定为200*n

我们可以通过添加以下代码来处理这些特殊情况：

// 检查是否所有马匹速度相同
int all_equal = 1;
for (int i = 1; i < n; i++) {
    if (tianji[i] != tianji[0] || qiwang[i] != qiwang[0]) {
        all_equal = 0;
        break;
    }
}
if (all_equal) {
    printf("所有马匹速度相同，无法盈利\n");
    printf("最终收益: 0两\n");
    return 0;
}

// 检查田忌是否全部快于齐王
int all_faster = 1;
for (int i = 0; i < n; i++) {
    if (tianji[i] <= qiwang[i]) {
        all_faster = 0;
        break;
    }
}
if (all_faster) {
    printf("田忌所有马都比齐王快，直接顺序对战\n");
    printf("最终收益: %d两\n", 200 * n);
    return 0;
}

// 检查田忌是否全部慢于齐王
int all_slower = 1;
for (int i = 0; i < n; i++) {
    if (tianji[i] >= qiwang[i]) {
        all_slower = 0;
        break;
    }
}
if (all_slower) {
    printf("田忌所有马都比齐王慢，最小化损失\n");
    printf("最终收益: %d两\n", -200 * n);
    return 0;
}

4. 贪心算法的正确性证明

为什么这种贪心策略能得到最优解？我们可以从以下几个方面来理解：

1. 局部最优导致全局最优：

   • 每次选择都尽可能获得最大收益或最小化损失
   • 这种局部最优的累积最终导致全局最优

2. 无后效性：

   • 当前决策不会影响后续决策的最优性
   • 对阵顺序的安排是独立的

3. 最优子结构：

   • 问题的最优解包含子问题的最优解
   • 剩余马匹的对阵策略不受已经比赛过马匹的影响

我们可以用数学归纳法来严格证明：

基础情况：当n=1时，显然选择唯一马匹对阵是最优的。

归纳假设：假设对于n=k匹马，贪心算法能得到最优解。

归纳步骤：对于n=k+1匹马，考虑第一场比赛的选择：

• 如果田忌最快的马比齐王最快的马快，那么用它对阵显然最优
• 如果田忌最快的马比齐王最快的马慢，用最慢的马去消耗齐王最快的马是最佳策略
• 如果速度相等，比较最慢的马来决定策略

无论哪种情况，剩余k匹马的对阵都可以用归纳假设得到最优解。因此贪心算法对n=k+1也成立。

5. 实际应用与扩展思考

贪心算法在田忌赛马问题中的应用展示了它在资源分配和竞争策略中的强大能力。类似的场景在实际中比比皆是：

1. 任务调度：在多处理器系统中分配任务以最小化完成时间
2. 投资组合：在有限资金下选择投资项目以最大化收益
3. 广告竞价：在预算限制下选择最优广告投放策略

对于田忌赛马问题，我们还可以考虑以下扩展：

变种1：平局情况

• 如果允许速度相同的马匹比赛结果为平局
• 需要修改策略，可能保留快马应对后续比赛

变种2：多轮比赛

• 比赛进行多轮，马匹有体力限制
• 需要考虑长期策略而非单轮最优

变种3：不完全信息

• 齐王的马匹速度不完全已知
• 需要引入概率和期望收益的概念

// 变种1的代码修改示例：处理平局情况
if (tianji[tianji_fast] > qiwang[qiwang_fast]) {
    money += 200;
    // ...原有代码
} else if (tianji[tianji_fast] < qiwang[qiwang_fast]) {
    money -= 200;
    // ...原有代码
} else {
    // 速度相等，可以选择平局或消耗最慢的马
    if (tianji[tianji_slow] > qiwang[qiwang_slow]) {
        money += 200;
        // ...原有代码
    } else if (tianji[tianji_slow] < qiwang[qiwang_slow]) {
        money -= 200;
        // ...原有代码
    } else {
        // 最慢的马也相等，选择平局
        printf("田忌%d vs 齐王%d → 平局\n", 
               tianji[tianji_fast], qiwang[qiwang_fast]);
        tianji_fast++;
        qiwang_fast++;
    }
}

贪心算法虽然强大，但并非万能。它适用于具有贪心选择性质的问题，即局部最优能导致全局最优。对于不具备这种性质的问题，如背包问题，贪心算法可能无法得到最优解。因此在实际应用中，我们需要仔细分析问题特性，选择合适的算法策略。